Sin/Cos look-up table

From Processing

Jump to: navigation, search
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:

  1. 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).
  2. 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

Retrieved from "http://wiki.processing.org/w/Sin/Cos_look-up_table"
Personal tools