3 ms·
lookup tables and lerp are the most common solution I've seen (for a wide range of functions). You can also memorize with an LRU cache.
by dekhn 5y ago
lookup tables and lerp are the most common solution I've seen (for a wide range of functions). You can also memorize with an LRU cache.
- phkahler 5y ago>> lookup tables and lerp are the most common solution I've seen The author missed one nice table method. When you need sin() and cos() split the angle into a coarse and fine angle. Coarse might be 1/256 of a circle and fine would be 1/65536 of a circle (whatever that angle is). You look up the sin/cos of the coarse angle in a 256 entry table. Then you rotate that by the fine angle which uses another 256 sin * cos entries. The rotation between coarse values is more accurate than linear interpolation and give almost the same accuracy as a 65536 entry table using only 768 entries. You can use larger tables or even another rotation by finer angle steps to get more accuracy.
- LeifCarrotson 5y ago> Then you rotate that by the fine angle Explain? Are you trying to reduce the error in the linear interpolation by describing the convex curve between the endpoints? The derivative of the cosine is the sine, and the derivative of the sine is the cosine...so I'd expect the required output of the fine angle table to interpolate 0.15 between 0.1 and 0.2 and the required output to interpolate 45.15 between 45.1 and 45.2 degrees will be very different.
- marginalia_nu 5y agoRemember that cos(a+b)=cos(a)cos(b)-sin(a)sin(b)
- LeifCarrotson 5y agoAh, now it makes sense. Thanks for the reminder of 8th grade trig...it's been a while!
- phkahler 5y ago>> Explain? Yeah I thought that might not be clear enough. Let's say you want 0.1 degree accuracy but don't want a 3600 entry table. Make one table for every 1 degree. You get to use the same table for sin and cos by changing the index. That is the coarse table with 360 entries. Then make another table with sin and cos values for every 0.1 degrees, or specifically 0.1*n for n going from 0-9. This is another 20 values, 10 sin and 10 cos for small angles. Take your input angle and split it into a coarse (integer degrees) and fine (fractional degrees) angle. Now take the (sin(x),cos(x)) from the coarse table as a vector and rotate it using the sin & cos values of the fine angle using a standard 2x2 rotation matrix. You can size these tables however you need. I would not use 360 and 10 for their sizes, but maybe 256 and 256. This can also be repeated with a 3rd table for "extra fine" angles.
- marginalia_nu 5y ago> You can also memorize with an LRU cache. That's probably not going to perform well for an operation this fast. The computation is faster than main memory read.
- munificent 5y agoYeah, lerping into a lookup table is common in audio and (old school) games. A common trick to make that faster is to not use doubles and radians to represent the phase. Instead, represent phase using an integer in some power-of-two range. That lets you truncate the phase to fit in a single period using a bit mask instead of the relatively slow modulo.
- spacechild1 5y agoOr use some evil bit hackery :-) https://github.com/pure-data/pure-data/blob/18c9695ba4de543c51c2c013b45b99b8f1c35a19/src/d_osc.c#L263-L319 https://github.com/pure-data/pure-data/blob/18c9695ba4de543c...