Pre-calculation is a very useful and neat programming trick that will allow you to “squeeze” more processing power out of your hardware.

In its simplest form, it involves only three easy steps :

• Step 1: do often-used and/or complex computations only once per run (for example, during application start-up)
• Step 2: keep the results of the computations in memory
• Step 3: from that point on, wherever needed, use these results instead of re-doing the computations

In this tutorial I will show you how to effectively use pre-calculation to considerably speed up your code.

Right. Ready? Set? Go!

Trigonometric functions have a wide variety of uses, both in real-life and in computer science. In fact, they are so widely used that even a limited platform such as J2ME has them built-in: all we have to do to get the cosine of an angle is call Math.cos(). This is very convenient and works just fine most of the time. However, if our code uses Math.cos() a lot, all the function calls and behind-the-scenes math will slow our application down quite a bit. If that happens, we can use pre-calculation to speed things up by :

1. using an array to store the values returned by Math.cos() and then,
2. replacing calls to Math.cos() with references to the array above.

In other words, we will change our code from

result = 12345 * Math.cos ( 24 )

to

result = 12345 * precalculated_cosine_array[24]

Looks easy enough, doesn’t it?

Now, in order to use pre-calculation like described above, we must first decide the interval for which to pre-calculate the values of Math.cos() . In an ideal world we would pre-calculate ALL the values of Math.cos(), but since this would require an infinite amount of time and memory, we must settle on a smaller subset. Since the cosine function is a periodic one, and since the value of an angle can be expressed in both radians and degrees, we are left with two obvious choices :

1. the interval 0 .. pi radians
2. the interval 0 .. 360 degrees

In day-to-day math, both are equally good. However, since this is computer math, we will go with the second option, as it is integer-based. This means you can easily use an array to store the results (for example, Math.cos(1 degree) will be stored in array_cos[1] ), something which is harder to do with non-integer-based intervals (where will Math.cos(pi/2) be stored ?).

SIDENOTE: In real life, where the functions used are much more complex than the simple cosine function, properly choosing the pre-calculation interval is sometimes a more difficult decision to make. You must take into consideration a multitude of factors, from the amount of available memory to the to actual usage scenarios (for example, there’s no point in calculating the value of a function for all numbers, even and odd, if you only need the results for even numbers).

After we’ve picked an interval, we need to decide what data type to use for the array. The obvious choice for storing the values of Math.cos() is double, since cosines are floating-point numbers. However, this means using floating-point math everywhere cosines are needed, and in J2ME floating-point math is painfully slow. To avoid this, let’s use a little trick: let’s store the results in an array of integers. Of course, storing floating-point numbers in an array of integers is not directly possible, but we can use a neat trick to bend the rules a little. Here’s the original algorithm :

1. for every angle between 0 and 360 degrees, calculate Math.cos() as a double,
2. store the result in an array of doubles
3. use that array instead of Math.cos()

By multiplying by 1024 (and there’s a reason we chose this number instead 1000 – read on), we can store a floating-point number in an integer and keep the first three decimals intact, which is more than enough precision for most practical purposes.

For example, let’s calculate cos(24 degrees) * 123. First, the classical way of doing things :

Math.cos (24 degrees ) = 0.913
Math.cos(24 degrees) * 123 = 112.366 .

Next, the clever way :

array_cos[24]=int(1024*Math.cos(24 degrees))=int(1024*0.913)=int(934.912)=935
(  array_cos[24] * 123 ) / 1024 = 115 005 / 1024 = 112

which is pretty close to the actual floating-point result, with the added twist that it involves absolutely no floating-point math whatsoever (except in the pre-calculation part, but obviously that doesn’t count since you only do it once for the entire application) .

Furthermore, since dividing integers by 1024 is the same as shifting right by 10 bits ( 1024 = 2 to the power 10 ), we can take advantage of this to make things even faster by replacing the division with a bit shift.

OK, enough talk, let’s see some code! First, the pre-calculation part :

int [] COS = new int[361] ;
for (int i = 0; i < 361; i++)
{
  COS[i] = (int) ( Math.cos( Math.toRadians(i) ) * 1024 );
}

Next, an actual usage example :

int someResult = ( COS[23]  * 3.141 ) >> 10 ; // Calculates cos(23 degrees) * PI
System.out.println( "The result is " + someResult ) ;

And we’re done! Very simple, very easy to use and very effective, like all good programming tricks should be. Of course, this method is not without its flaws, but the benefits of using it greatly offset its disadvantages. I use it all the time when absolute precision is not required, and it’s never failed me, not even once. And, best of all, you can easily adapt it to suit your computational needs: just replace Math.cos() with the function of your choice, and then modify the pre-calculation interval accordingly.

Thanks for reading!