Sine and Cosine lookup tables

Sometimes speed is essential.  So recently for one of my projects that called Math.sin and Math.cos 1000 each every frame, I decided to create a lookup table.  Now that I’ve finally had some time too, I got a chance to test what I though was a clear speed difference and I found some very surprising results.

My thinking was basically that if I precomputed all the possible values I would need for sine and cosines I could avoid computing them thousands of times each frame.  Interestingly,  it turned out quite a bit differently than I thought.

First here’s my LookupTable class:
For now, ignore the granularity option as we’ll work with just whole numbers so as to make this demonstration more clear.  Also, it’s important not to perform int->Number or Number->int conversion.

package com.pj_co.math
{
        /**
        * Generates a sine or cosine curve based on max and min values.  These values are inteperated
        * as 0 and 90 degrees on a graph respectively. This allows for returning a single curve.
        * The equations used are:  Math.sin ( i / maxVal  * PI )  and  Math.cos ( i / maxVal  * PI )
        *
        * @author Patrick Cousins
        */
        public class LookupTable
        {
                public static const SINE     : String = "sine";
                public static const COSINE   : String = "cosine";
                public static const BOTH     : String = "both";

                private var sinTable         : Array;
                private var cosTable         : Array;
                private var maxVal           : Number;

                public function LookupTable (   type         : String,
                                                minVal       : Number,
                                                maxVal       : Number,
                                                granularity  : Number    = 1     )
                {

                        this.minVal = minVal;
                        this.maxVal = maxVal;

                        switch ( type )
                        {
                                case SINE :
                                generateSineTable ( minVal, maxVal, granularity);
                                break;

                                case COSINE :
                                generateCoSineTable ( minVal, maxVal, granularity);
                                break;

                                case BOTH :
                                generateCoSineTable ( minVal, maxVal, granularity);
                                generateSineTable ( minVal, maxVal, granularity);
                                break;
                        }
                }

                //-------------------------------------------------------
                // Public API
                //-------------------------------------------------------
                

                public function getCosine( val : Number ) : Number
                {
                        return cosTable[val];
                }

                public function getSine( val : int ) : Number
                {
                        return sinTable[val];
                }

                public function getSineArray(  ) : Array
                {
                        return sinTable;
                }

                //-------------------------------------------------------
                // Private methods
                //-------------------------------------------------------
                

                private function generateCoSineTable (  minVal      : Number,
                                                        maxVal      : Number,
                                                        granularity : Number    ) : void
                {

                        cosTable = new Array();

                        var PI :Number = 3.1415927;

                        for (var i : Number = minVal; i <= maxVal; i += granularity)
                        {
                                cosTable [i] = ( Math.cos( i / maxVal  * PI ) );
                        }

                }

                private function generateSineTable (    minVal      : Number,
                                                        maxVal      : Number,
                                                        granularity : Number   ) : void
                {

                        sinTable = new Array();
                        var PI :Number = 3.1415927;

                        for (var i : Number = minVal; i <= maxVal; i ++ )
                        {
                                sinTable.push ( Math.sin( i / maxVal  * PI ));
                        }

                }

        }
}

And now for some code to speed test with:

ar lookupTable : LookupTable = new LookupTable ( LookupTable.SINE, 0, 500, 1 );
var sineTable:Array = lookupTable .getSineArray();

//set a time point
var now : Date = new Date();

for (var i : Number = 0 ; i < 999999 ; i++ )
{
        var realSine : Number = Math.sin ( i / 500  * Math.PI );
}

//set a second time point
var after : Date = new Date();

for (var j : int = 0 ; j < 999999 ; j++ )
{
        var localArraySine : Number = sineTable[j];
}

//set a third time point
var after2 : Date = new Date();

for (var k : int = 0 ; k < 999999 ; k++ )
{
        var computedSine : Number = lookupTable.getSine(k);
}

//set a fourth time point
var after3 : Date = new Date();

//calculate the time differences
var diffSeconds1 = after.getSeconds() - now.getSeconds();
var diffMiliseconds1 = after.getMilliseconds() - now.getMilliseconds();

if ( diffMiliseconds1 < 0 )
{
        diffSeconds1 --;
        diffMiliseconds1 += 1000;
}

var diffSeconds2 = after2.getSeconds() - after.getSeconds();
var diffMiliseconds2 = after2.getMilliseconds() - after.getMilliseconds();

if ( diffMiliseconds2 < 0 )
{
        diffSeconds2 --;
        diffMiliseconds2 += 1000;
}

var diffSeconds3 = after3.getSeconds() - after2.getSeconds();
var diffMiliseconds3 = after3.getMilliseconds() - after2.getMilliseconds();

if ( diffMiliseconds3 < 0 )
{
    diffSeconds3 --;
    diffMiliseconds3 += 1000;
}

trace("1st for loop (Math.Sin) :",
       diffSeconds1,
       "seconds ",
       diffMiliseconds1,
       "milliseconds" );

trace("2nd for loop (local pre-computed array) :",
       diffSeconds2,
       "seconds ",
       diffMiliseconds2,
       "milliseconds" );

trace("3rd for loop (precomputed from lookuptable getter method ) :",
        diffSeconds3,
       "seconds ",
       diffMiliseconds3,
       "milliseconds" );

So after nearly a million iterations in each for loop, the results were :

1st for loop (Math.Sin) : 0 seconds 281 milliseconds
2nd for loop (local, pre-computed array) : 0 seconds 141 milliseconds
3rd for loop (precomputed sine retrieved from lookuptable getter method ) : 0 seconds 281 milliseconds

Not a huge speed difference really.  The local array wins by a mere 140 milliseconds.  But it seems more than anything, object access slows things down a teeny bit more than Math.sin.

filed under: Interesting stuff, Math, Misc, Scripts | permalink

2 Responses to “Sine and Cosine lookup tables”

1. pajamacode » Blog Archive » Sine and Cosine lookup tables — Some Random Dude Says:
   March 27th, 2009 at 11:50 am

   [...] pajamacode » Blog Archive » Sine and Cosine lookup tables [...]

2. Daniello Says:
   January 26th, 2010 at 10:39 am

   Use Vector. instead Array and magic happened

   My results:

   1st for loop (Math.Sin) : 0 seconds 196 milliseconds
   2nd for loop (local pre-computed array) : 0 seconds 74 milliseconds
   3rd for loop (precomputed from lookuptable getter method ) : 0 seconds 239 milliseconds

Leave a Reply

You must be logged in to post a comment.