Sin/Cos look-up table
From Processing
Versions: | 1.0+ |
Contributors: | MY Name |
Started: | YYYY-MM-DD |
When it comes to interactivity slow code can drastically reduce the emotional impact of your work. Also a complex generative animation will be more effective if it runs more smoothly. So it's important that once your code is stable but sluggish you start looking for ways to improve the perceived and actual speed of your piece.
Space-time trade off
One of those ways could be employing a so called Space-time_tradeoff, also often called “look-up tables”. This technique has been around since the early days of computers, often even just to simulate non-existing functionality on limited hardware, for example calculating sine/cosine values. Incidentally those trigonometric functions are generic and “expensive”) and periodic enough to be great candidates for being converted into look-up tables in order to speed up their use.
In principle look-up tables work like that:
- Pre-compute a complex function over a certain interval before the actual process starts. This could be at the start of your programme or even before writing (created by a separate programme whose output is hardcoded into your source code).
- Use the look-up table with already existing results at each point in your programme this function is required instead of calling the function itself
Look-up tables are not just handy for complex mathematical functions, but can also be used to encode logic, handle cases of symmetry and collapse large numbers of conditionals in your code.
Transforming sin/cos
Since sin() and cos() are periodic functions we only need to compute them for the interval of one period:
0 <= x <= 2*PI
On the other hand our tables will be implemented as array and so need an integer number as index. We can't use PI as array index, but we can say we'll base our tables on degrees and use the interval:
0 <=x <= 360 degrees
Using such a table would give us a sin() and cos() function with a precision of 1 degree only. You'd have to resort to rounding your input values if you wanted to compute angles such as sin(90.25deg)…
Limited precision and rounding are permanent issues to keep in mind when employing look-up tables and also reason why the technique is called a “trade-off”. In order to improve performance something else has to give. In many case though, this doesn't prove to be a serious problem in practice and the source code below shows a possible workaround for the lack of precision.
Source Code
This is an easy to digest example demonstrating the creation and use of a sin/cos look-up table. It doesn't structurally justify the use of such tables. You'll only benefit and should employ this technique if you make excessive use of trigonometric functions.
/** sincoslookup taken from http://wiki.processing.org/index.php/Sin/Cos_look-up_table @author toxi (http://www.processinghacks.com/user/toxi) */ // declare arrays and params for storing sin/cos values float sinLUT[]; float cosLUT[]; // set table precision to 0.5 degrees float SC_PRECISION = 0.5f; // caculate reciprocal for conversions float SC_INV_PREC = 1/SC_PRECISION; // compute required table length int SC_PERIOD = (int) (360f * SC_INV_PREC); // init sin/cos tables with values // should be called from setup() void initSinCos() { sinLUT = new float[SC_PERIOD]; cosLUT = new float[SC_PERIOD]; for (int i = 0; i < SC_PERIOD; i++) { sinLUT[i] = (float) Math.sin(i * DEG_TO_RAD * SC_PRECISION); cosLUT[i] = (float) Math.cos(i * DEG_TO_RAD * SC_PRECISION); } } // circle radius used for example float radius; void setup() { size(200,200); initSinCos(); // important call to initialize lookup tables } void draw() { background(255); // modulate the current radius radius=50+50*sinLUT[millis()%SC_PERIOD]; // draw a circle made of points (every 5 degrees) for(int i=0; i<360; i+=5) { // convert degrees into array index: // the modulo operator (%) ensures periodicity int theta=(int)((i*SC_INV_PREC) % SC_PERIOD); // draw the circle around mouse pos point( mouseX+radius*cosLUT[theta], mouseY+radius*sinLUT[theta] ); } }
Downloads
Related Links
- http://toxi.co.uk/p5/xsphere/ uses LUT for storing sphere vertex coordinates
- http://toxi.co.uk/p5/levels/ uses LUT for keeping track of colour level transformations
- http://toxi.co.uk/base26/ LUT used as cache and to optimize marching squares contour rendering