Trigonometry functions like Math.sin and Math.cos are widely used in AS3 games and other apps that make intensive use of graphics, sound, or physics. Today’s article shows you a way to trade a little bit of memory for much faster trigonometry computations, which can seriously speed up any app that makes heavy use of Math.sin, Math.cos, and the like. Keep reading for the class that’ll help you do this, a demo app, performance testing, analysis, and more. (UPDATE: optimized thanks to skyboy)

Lookup tables are a common technique in programming. They involve doing expensive computations once, storing them in a table, and accessing them later. In AS3, the idea is that accessing the values stored in a Vector table is faster than computing the value and therefore you get a speed boost.

For such a widely-used technique, it doesn’t seem to be getting much usage in the AS3 world. I found a test on actionscript.org that uses lookup tables for Math.sin and shows a performance boost, but the lookup table can only be used with radians that happen to be whole numbers (integers) and is therefore not very useful and an unfair comparison to the robust Math.sin function. There is also an article on polygonal.de discussing the subject, but it doesn’t provide full source, uses the relatively-slow Array because it was written before Vector debuted in Flash Player 10, and doesn’t say specifically if lookup tables are used to achieve the alleged 14x performance boost. It does, however, have a cool demo app that inspired my demo app below.

Due to this lack of existing lookup table work, I decided to make my own lookup table for trig functions: any function like Math.sin and Math.cos that takes parameters in the range [0,2pi). Here is the basic usage:

// Make a lookup table for Math.sin with 2 decimal places of precision
var sineLUT:TrigLUT = new TrigLUT(2, Math.sin);
 
// Query with arbitrary radians, just like the original Math.sin
result = sineLUT.val(-45.123);

If you don’t need to pass an arbitrary radians value, there are even faster functions that work as long as you can guarantee limits:

// Radians >= 0
result = sineLUT.valPositive(45.123);
 
// Radians on (-2pi,2pi)
result = sineLUT.valNormalized(-4.123);
 
// Radians on [0,2pi)
result = sineLUT.valNormalizedPositive(4.123);

The lookup table and precision variable are public, so you can avoid the slow function call by inlining them. The functions are small, so it won’t bloat up your code or be too messy:

// Inline version of TrigLUT.valNormalizedPositive
result = sineLUT.table[int(4.123*sineLUT.pow)];

For the ultimate speed boost when you’re doing lots of lookups in one function, cache the lookup table and precision variable as local variables:

var sineTable:Vector.<Number> = sineLUT.table;
var sinePow:Number = sineLUT.pow;
result = sineTable[int(4.123*sinePow)];

You can even make a lookup table for arbitrary functions. Here’s one for the square of Math.sin with 2 decimal places of precision:

var sineSquaredLUT:TrigLUT = new TrigLUT(
	2,
	function(r:Number):Number{r = Math.sin(r); return r*r;}
);

Use this lookup table the same exact way you used the Math.sin lookup table:

sineSquaredLUT.val(-45.123);

Now that you know how to use it, here is the source code for TrigLUT (Trigonometry LookUp Table):

/*
The MIT License
 
Copyright (c) 2011 Jackson Dunstan
 
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
 
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/
package
{
	/**
	*   A lookup table for trig values (e.g. sine, cosine) to improve on the
	*   performance of the static functions found in the Math class
	*   @author Jackson Dunstan
	*/
	public class TrigLUT
	{
		/** 2 * PI, the number of radians in a circle*/
		public static const TWO_PI:Number = 2.0 * Math.PI;
 
		/** The static TWO_PI cached as a non-static field*/
		private const TWO_PI:Number = TrigLUT.TWO_PI;
 
		/** Table of trig function values*/
		public var table:Vector.<Number>;
 
		/** 10^decimals of precision*/
		public var pow:Number;
 
		/**
		*   Make the look up table
		*   @param numDigits Number of digits places of precision
		*   @param mathFunc Math function to call to generate stored values.
		*                   Must be valid on [0,2pi).
		*   @throws Error If mathFunc is null or invalid on [0,2pi)
		*/
		public function TrigLUT(numDigits:uint, mathFunc:Function)
		{
			var pow:Number = this.pow = Math.pow(10, numDigits);
			var round:Number = 1.0 / pow;
			var len:uint = 1 + this.TWO_PI*pow;
			var table:Vector.<Number> = this.table = new Vector.<Number>(len);
 
			var theta:Number = 0;
			for (var i:uint = 0; i < len; ++i)
			{
				table[i] = mathFunc(theta);
				theta += round;
			}
		}
 
		/**
		*   Look up the value of the given number of radians
		*   @param radians Radians to look up the value of
		*   @return The value of the given number of radians
		*/
		public function val(radians:Number): Number
		{
			return radians >= 0
				? this.table[int((radians%this.TWO_PI)*this.pow)]
				: this.table[int((TWO_PI+radians%this.TWO_PI)*this.pow)];
		}
 
		/**
		*   Look up the value of the given number of radians
		*   @param radians Radians to look up the value of. Must be positive.
		*   @return The sine of the given number of radians
		*   @throws RangeError If radians is not positive
		*/
		public function valPositive(radians:Number): Number
		{
			return this.table[int((radians%this.TWO_PI)*this.pow)];
		}
 
		/**
		*   Look up the value of the given number of radians
		*   @param radians Radians to look up the value of. Must be on (-2pi,2pi).
		*   @return The value of the given number of radians
		*   @throws RangeError If radians is not on (-2pi,2pi)
		*/
		public function valNormalized(radians:Number): Number
		{
			return radians >= 0
				? this.table[int(radians*this.pow)]
				: this.table[int((this.TWO_PI+radians)*this.pow)];
		}
 
		/**
		*   Look up the value of the given number of radians
		*   @param radians Radians to look up the value of. Must be on [0,2pi).
		*   @return The value of the given number of radians
		*   @throws RangeError If radians is not on [0,2pi)
		*/
		public function valNormalizedPositive(radians:Number): Number
		{
			return this.table[int(radians*this.pow)];
		}
	}
}

Since the whole point of this exercise is to get a performance boost, let’s do some performance testing! Here is an app that compares the performance of Math.sin and Math.cos to TrigLUT:

/*
The MIT License
 
Copyright (c) 2011 Jackson Dunstan
 
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
 
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/
package
{
	import flash.display.*;
	import flash.utils.*;
	import flash.text.*;
 
	/**
	*   Performance test app for TrigLUT, the trig function lookup table
	*   @author Jackson Dunstan
	*/
	public class TrigLUTTest extends Sprite
	{
		private var __logger:TextField = new TextField();
		private function log(msg:*): void { __logger.appendText(msg + "\n"); }
 
		public function TrigLUTTest()
		{
			__logger.autoSize = TextFieldAutoSize.LEFT;
			addChild(__logger);
 
			const DIGITS:uint = 2;
			const STEP:Number = 0.05;
			var beforeTime:int;
			var afterTime:int;
			var lut:TrigLUT = new TrigLUT(DIGITS, Math.sin);
			var lutTable:Vector.<Number> = lut.table;
			var lutPow:Number = lut.pow;
			const REPS:int = 100000;
			const NUM:int = int(TrigLUT.TWO_PI / STEP);
			var theta:Number;
			var i:int;
			var j:int;
			var result:Number;
			const TWO_PI:Number = TrigLUT.TWO_PI;
 
			log("Function,Time");
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				theta = 0;
				for (j = 0; j < NUM; ++j)
				{
					result = Math.sin(theta);
					theta += STEP;
				}
			}
			afterTime = getTimer();
			log("Math.sin," + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				theta = 0;
				for (j = 0; j < NUM; ++j)
				{
					result = Math.cos(theta);
					theta += STEP;
				}
			}
			afterTime = getTimer();
			log("Math.cos," + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				theta = 0;
				for (j = 0; j < NUM; ++j)
				{
					result = lut.val(theta);
					theta += STEP;
				}
			}
			afterTime = getTimer();
			log("TrigLUT.val," + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				theta = 0;
				for (j = 0; j < NUM; ++j)
				{
					result = lut.valPositive(theta);
					theta += STEP;
				}
			}
			afterTime = getTimer();
			log("TrigLUT.valPositive," + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				theta = 0;
				for (j = 0; j < NUM; ++j)
				{
					result = lut.valNormalized(theta);
					theta += STEP;
				}
			}
			afterTime = getTimer();
			log("TrigLUT.valNormalized," + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				theta = 0;
				for (j = 0; j < NUM; ++j)
				{
					result = lut.valNormalizedPositive(theta);
					theta += STEP;
				}
			}
			afterTime = getTimer();
			log("TrigLUT.valNormalizedPositive," + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				theta = 0;
				for (j = 0; j < NUM; ++j)
				{
					result = theta >= 0
						? lutTable[int((theta%TWO_PI)*lutPow)]
						: lutTable[int((TWO_PI+theta%TWO_PI)*lutPow)];
					theta += STEP;
				}
			}
			afterTime = getTimer();
			log("inline val," + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				theta = 0;
				for (j = 0; j < NUM; ++j)
				{
					result = lutTable[int((theta%TWO_PI)*lutPow)];
					theta += STEP;
				}
			}
			afterTime = getTimer();
			log("inline valPositive," + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				theta = 0;
				for (j = 0; j < NUM; ++j)
				{
					result = theta >= 0
						? lutTable[int(theta*lutPow)]
						: lutTable[int((TWO_PI+theta)*lutPow)];
					theta += STEP;
				}
			}
			afterTime = getTimer();
			log("inline valNormalized," + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				theta = 0;
				for (j = 0; j < NUM; ++j)
				{
					result = lutTable[int(theta*lutPow)];
					theta += STEP;
				}
			}
			afterTime = getTimer();
			log("inline valNormalizedPositive," + (afterTime-beforeTime));
		}
	}
}

Here is the test environment I ran this app on:

  • Flex SDK (MXMLC) 4.1.0.16076, compiling in release mode (no debugging or verbose stack traces)
  • Release version of Flash Player 10.3.181.14
  • 2.4 Ghz Intel Core i5
  • Mac OS X 10.6.7

And here are the results I got:

Function Time
Math.sin 509
Math.cos 509
TrigLUT.val 464
TrigLUT.valPositive 447
TrigLUT.valNormalized 253
TrigLUT.valNormalizedPositive 214
inline val 336
inline valPositive 329
inline valNormalized 145
inline valNormalizedPositive 133

Here are the same results in graph form:

Performance Chart

These results clearly show the performance benefits of TrigLUT:

  • TrigLUT is always faster than Math.sin and Math.cos
  • Reducing the acceptable radian values helps performance a lot, especially guaranteeing positive values
  • Inlining lookups results in maximum performance
  • In the best case, TrigLUT beats the Math class functions by almost 5x!

With such compelling results, we should make sure that they are still accurate. and not wildly different than the results we would normally get from the Math class functions. TrigLUT allows you to set the number of digits of precision you’d like. The more digits you want, the bigger and more accurate the lookup table gets. It’s important to remember though that increasing precision does not slow down TrigLUT. Usually, I find that two digits of precision (a lookup table with 628 Numbers = 4.9KB of memory) is enough for most uses, but I leave the precision up to each user of TrigLUT to determine their own needs. Here is the source code for a small demo app that simply draws a sine or cosine curve using the Math class functions and the approximation via TrigLUT over the top. A live demo follows.

/*
The MIT License
 
Copyright (c) 2011 Jackson Dunstan
 
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
 
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/
package
{
	import flash.display.*;
	import flash.events.*;
	import flash.text.*;
	import flash.geom.*;
 
	/**
	*   Demonstration app for TrigLUT, the trig function lookup table
	*   @author Jackson Dunstan
	*/
	[SWF(width=640,height=480,backgroundColor=0xEEEAD9)]
	public class TrigLUTDemo extends Sprite
	{
		private static const TEXT_FORMAT:TextFormat = new TextFormat("_sans", 11);
 
		private var bmd:BitmapData;
		private var bmdRect:Rectangle;
		private var mathFuncName:String;
		private var digits:uint;
		private var mathFuncFrame:Sprite;
		private var digitsFrame:Sprite;
 
		public function TrigLUTDemo()
		{
			stage.scaleMode = StageScaleMode.NO_SCALE;
			stage.align = StageAlign.TOP_LEFT;
 
			this.bmd = new BitmapData(stage.stageWidth, stage.stageHeight, false, 0xffffffff);
			addChild(new Bitmap(bmd));
			this.bmdRect = new Rectangle(0, 0, this.bmd.width, this.bmd.height);
 
			this.mathFuncFrame = addChoices(
				"Math function: ",
				onMathFuncButton,
				0,
				["sin","cos"]
			);
 
			this.digitsFrame = addChoices(
				"Digits of precision: ",
				onPrecisionButton,
				this.mathFuncFrame.height,
				["0","1", "2", "3", "4", "5"]
			);
 
			this.digits = 2;
			this.mathFuncName = "sin";
			redraw();
 
			var about:TextField = new TextField();
			about.defaultTextFormat = TEXT_FORMAT;
			about.y = this.digitsFrame.y + this.digitsFrame.height;
			about.htmlText = "TrigLUT Demo by <font color=\"#0071BB\"><a href=\""
				+ "http://jacksondunstan.com/articles/1190"
				+ "\">JacksonDunstan.com</a></font>\n"
				+ "Black line: trig function\n"
				+ "Red line: lookup table";
			about.autoSize = TextFieldAutoSize.LEFT;
			about.selectable = false;
			addChild(about);
		}
 
		private function addChoices(
			promptStr:String,
			callback:Function,
			y:Number,
			choices:Array
		): Sprite
		{
			var prompt:TextField = new TextField();
			prompt.defaultTextFormat = TEXT_FORMAT;
			prompt.text = promptStr;
			prompt.autoSize = TextFieldAutoSize.LEFT;
			prompt.selectable = false;
			addChild(prompt);
 
			var x:Number = prompt.width;
			const PAD:Number = 3;
			for each (var choiceName:String in choices)
			{
				var tf:TextField = new TextField();			
				tf.defaultTextFormat = TEXT_FORMAT;
				tf.name = "label";
				tf.text = choiceName;
				tf.autoSize = TextFieldAutoSize.LEFT;
				tf.selectable = false;
				tf.x = tf.y = PAD;
 
				var button:Sprite = new Sprite();
				button.name = choiceName;
				button.graphics.beginFill(0xE6E2D1);
				button.graphics.drawRect(0, 0, tf.width+PAD*2, tf.height+PAD*2);
				button.graphics.endFill();
				button.addChild(tf);
				button.addEventListener(
					MouseEvent.CLICK,
					function(ev:MouseEvent): void
					{
						var button:Sprite = ev.currentTarget as Sprite;
						var label:TextField = button.getChildByName("label") as TextField;
						callback(label.text);
					}
				);
				button.x = x;
				button.y = y;
 
				addChild(button);
				x += button.width + PAD;
			}
 
			prompt.y = y + (button.height - prompt.height) / 2;
 
			var frame:Sprite = new Sprite();
			frame.graphics.lineStyle(1);
			frame.graphics.drawRect(0, 0, tf.width+PAD*2, tf.height+PAD*2);
			addChild(frame);
 
			return frame;
		}
 
		private function onMathFuncButton(label:String): void
		{
			this.mathFuncName = label;
			redraw();
		}
 
		private function onPrecisionButton(label:String): void
		{
			this.digits = int(label);
			redraw();
		}
 
		private function redraw(): void
		{
			var mathFuncButton:Sprite = getChildByName(this.mathFuncName) as Sprite;
			this.mathFuncFrame.x = mathFuncButton.x;
			this.mathFuncFrame.y = mathFuncButton.y;
 
			var digitsButton:Sprite = getChildByName(String(this.digits)) as Sprite;
			this.digitsFrame.x = digitsButton.x;
			this.digitsFrame.y = digitsButton.y;
 
			var mathFunc:Function = Math[this.mathFuncName];
			var lut:TrigLUT = new TrigLUT(this.digits, mathFunc);
 
			var bmd:BitmapData = this.bmd;
 
			bmd.lock();
			var w:int = bmd.width;
			var h:int = bmd.height;
			bmd.fillRect(this.bmdRect, 0xEEEAD9);
			var halfH:int = h / 2;
			var stepTheta:Number = TrigLUT.TWO_PI / w;
			var theta:Number = 0;
			for (var x:int = 0; x < w; ++x)
			{
				for (var y:int = 0; y < h; ++y)
				{
					bmd.setPixel(
						x,
						halfH + mathFunc(theta)*halfH,
						0xff000000
					);
					bmd.setPixel(
						x,
						halfH + lut.valNormalizedPositive(theta)*halfH,
						0xffff0000
					);
				}
				theta += stepTheta;
			}
			bmd.unlock();
		}
	}
}

Here is a live version of the demo. Make sure you have JavaScript turned on and click “Show Demo”.

In short, TrigLUT offers improved performance for trig functions like Math.sin and Math.cos by using lookup tables. If anyone has any suggestions for improving TrigLUT or alternatives to lookup tables entirely, feel free to join in the discussion below in the comments. To get the performance test, demo app, and TrigLUT class all in one convenient ZIP, you can download TrigLUT here.