6 ms·
Nice. Reminds me of an optimisation trick from a while ago: I remember being bottlenecked by one of these trigonometric functions years ago when working with a
by drej 5y ago
Nice. Reminds me of an optimisation trick from a while ago: I remember being bottlenecked by one of these trigonometric functions years ago when working with a probabilistic data structure... then I figured the input domain was pretty small (a couple dozen values), so I precomputed those and used an array lookup instead. A huge win in terms of perf, obviously only applicable in these extreme cases.
- tantalor 5y agohttps://en.wikipedia.org/wiki/Memoization https://en.wikipedia.org/wiki/Memoization
- bluedino 5y agoTechnically it's a lookup table if you pre-compute them. Memoization would just be caching them as you do them.
- tantalor 5y agoNot necessarily, you could "cache" them in a compilation step and then use the table at runtime.
- bruce343434 5y agoTangential at best, but why was the 'r' dropped from that term? Or why not call it caching? Why the weird "memo-ization"? It makes me think of a mass extinction event where everything is turned into a memo.
- franciscop 5y agoIt's explained right in the linked Wikipedia page: > The term "memoization" was coined by Donald Michie in 1968[3] and is derived from the Latin word "memorandum" ("to be remembered"), usually truncated as "memo" in American English, and thus carries the meaning of "turning [the results of] a function into something to be remembered". While "memoization" might be confused with "memorization" (because they are etymological cognates), "memoization" has a specialized meaning in computing.
- wongarsu 5y agoThe term memoization likely precedes the word caching (as related to computing, obviously weapon caches are far older). Memoization was coined in 1968. CPU caches only came about in the 80s as registers became significantly faster than main memory. As wikipedia outlines, the r was dropped because of the memo. It's derived from the latin word memorandum that does contain the r, just like memory, but apparently it was more meant as an analogy to written memos.
- ThePadawan 5y agoOne of the things I recently learned that sounded the most "that can't possibly work well enough" is an optimization for sin(x): If abs(x) < 0.1, "sin(x)" is approximated really well by "x". That's it. For small x, just return x. (Obviously, there is some error involved, but for the speedup gained, it's a very good compromise)
- sharikone 5y agoI think that you will find that for subnormal numbers any math library will use the identity function for sin(x) and 1 for cos(x)
- ThePadawan 5y agoRight, but the largest subnormal number in single-precision floats is ~ 10^-38. That the sin(x) approximation still works well for 10^-1 (with an error of ~0.01%) is the really cool thing!
- chriswarbo 5y agoThis is a very common assumption in Physics, e.g. https://en.wikipedia.org/wiki/Pendulum_(mathematics)#Small-angle_approximation https://en.wikipedia.org/wiki/Pendulum_(mathematics)#Small-a... Whether it's appropriate in a numerical calculation obviously depends on the possible inputs and the acceptable error bars :)
- quietbritishjim 5y agoThat is precisely the technique discussed in the article: it's the first term of the Taylor expansion. Except that the article used more terms of the expansion, and also used very slightly "wrong" coefficients to improve the overall accuracy within the small region.
- Bostonian 5y agoWhy wouldn't you at least include the x^3 term in the Taylor series for abs(x) < 0.1?
- 5y ago
- mooman219 5y agoThis would be a decent lookup for the atan2 function: https://gist.github.com/mooman219/19b18ff07bb9d609a103ef0cd059422c https://gist.github.com/mooman219/19b18ff07bb9d609a103ef0cd0...