As3 code tricks, optimizations, and small discoveries

Log10(a) , Faster !

Jul 07, 2013 ~ 1 Comment ~ Written by benjamin guihaire

Here we are going to try to write a faster integer Log10(a) function.

Few methods are described on this website

But in this post, I am going to introduce a new method.

The simple way is to call :

var mylog10:int = Math.log(i) * ooLOG_10;

with ooLOG_10 pre initialized to:

const ooLOG_10:Number = 1/Math.log(10);

But I am discarding this method, as it produce incorrect answers due to rounding errors
I also tried Math.log(i)/Math.log(10) , which also produce rounding problems results.

The obvious way is to do:

var mylog10:int
(i >= 1000000000) ? 9 :
(i >= 100000000) ? 8 :
(i >= 10000000) ? 7 :
(i >= 1000000) ? 6 :
(i >= 100000) ? 5 :
(i >= 10000) ? 4 :
(i >= 1000) ? 3 :
(i >= 100) ? 2 :
(i >= 10) ? 1 : 0;

This works perfectly, and produce really good performances.
Lets try to be faster !
Instead of the ternary ?: operator, we can use the faster || operator.
and get the sign bit with proper masking to get the proper 1,2,3,4,5,6,7,8,9 results:
by using >>>31

we cal also take advantage of

>>>29 which produce 7 for negative integers
>>>30 which produce 3 for negative integers
>>>31 which produce 1 for negative integers

which gives:

var mylog10:int =
(((999999999-i)>>31)&9)||
((((99999999-i)>>31)&8)||
(((9999999-i)>>>29)||//7
((((999999-i)>>31)&6)||
((((99999-i)>>31)&5)||
((((9999-i)>>31)&4)||
(((999-i)>>>30)||//3
((((99-i)>>31)&2)||
(((9-i)>>>31)))))))));//1

here the profiles:

log10

note that the new method produce good results when the distribution of the queried numbers is in ^10
but also produce faster results for a linear distribution.

*** UPDATE ***
I just tried it on a MacbookPro with flash11.7, and the results were different, and the if( ) version was faster with a linear distribution
but,
log10_mac
When doing the test, I also noticed my mac was really slow, so I closed some of the applications again, and now the profiling is similar to the one I got on my PC, so when testing, make sure your computer “runs” normally.

What do you get ?

here the code:

	protected function log_10():void
		{
			var i:uint = 0;
			var a:int;			
			var b:int = Math.random();			
			var val:Number;
			var inc:int = 1;
			var max:int = 10;
			
			
			var REPS:int = 100000000;
			const ooLOG_10:Number = 1/Math.log(10);			
			
			for(var k:int=0;k<32;k++)
			{
				trace("-2>>k:",int(-2)>>k);
				trace("-2>>>k:",int(-2)>>>k);				
			}
				
	
			
			var valuesToTry:Array = [1,2,3,4,5,6,7,8,9,10,11,
						   55,99,100,101,
						   555,999,1000,1001,
						   5555,9999,10000,10001,
						   55555,99999,100000,100001,
						   555555,999999,1000000,1000001,
						   5555555,9999999,10000000,10000001,
						   55555555,99999999,100000000,100000001,
						   555555555,999999999,1000000000,1000000001]
			for(var ii:int=0;ii<valuesToTry.length;ii++)
			{
				i=valuesToTry[ii];
				var absInt1:int = Math.log(i) * ooLOG_10;
				
				var absInt2:int= (i >= 1000000000) ? 9 : (i >= 100000000) ? 8 : (i >= 10000000) ? 7 : 
					(i >= 1000000) ? 6 : (i >= 100000) ? 5 : (i >= 10000) ? 4 : 
					(i >= 1000) ? 3 : (i >= 100) ? 2 : (i >= 10) ? 1 : 0;
							
				var absInt3:int =(((999999999-i)>>31)&9)||
								((((99999999-i)>>31)&8)||
								(((9999999-i)>>>29)||//7
								((((999999-i)>>31)&6)||
								((((99999-i)>>31)&5)||
								((((9999-i)>>31)&4)||
								(((999-i)>>>30)||//3
								((((99-i)>>31)&2)||
								(((9-i)>>>31)))))))));//1
				
				var absInt4:int =Memory.readUnsignedByte(((999999999-i)>>>31)||
					(((99999999-i)>>>30)||
						(((9999999-i)>>>29)||//7
							(((999999-i)>>>28)||
								(((99999-i)>>>27)||
									(((9999-i)>>>26)||
										(((999-i)>>>25)||//3
											(((99-i)>>>24)||
												((9-i)>>>23)))))))));//1
		
				if(absInt2!=absInt3)|| (absInt4!=absInt2))
				{
					throw("problem");
				}				
			}

			var time1:uint = getTimer();
			for(i=0;i<REPS;i++)
			{
				absInt1 = Math.log(i) * ooLOG_10;
			}			

			var time2:uint = getTimer();
			for(i=0;i<REPS;i++)
			{
				absInt2 = (i >= 1000000000) ? 9 : (i >= 100000000) ? 8 : (i >= 10000000) ? 7 : 
					(i >= 1000000) ? 6 : (i >= 100000) ? 5 : (i >= 10000) ? 4 : 
					(i >= 1000) ? 3 : (i >= 100) ? 2 : (i >= 10) ? 1 : 0;
			}
			var time3:uint = getTimer();
			for(i=0;i<REPS;i++)
			{
				absInt3 =(((999999999-i)>>31)&9)||
						 ((((99999999-i)>>31)&8)||
						 (((9999999-i)>>>29)||//7
						 ((((999999-i)>>31)&6)||
						 ((((99999-i)>>31)&5)||
						 ((((9999-i)>>31)&4)||
						 (((999-i)>>>30)||//3
						 ((((99-i)>>31)&2)||
						 (((9-i)>>>31)))))))));//1
				
			}					
			var time4:uint = getTimer();
			for(i=0;i<REPS;i++)
			{
				absInt4 =Memory.readUnsignedByte(((999999999-i)>>>31)||//9
					(((99999999-i)>>>30)||//8
					(((9999999-i)>>>29)||//7
					(((999999-i)>>>28)||//6
					(((99999-i)>>>27)||//5
					(((9999-i)>>>26)||//4
					(((999-i)>>>25)||//3
					(((99-i)>>>24)||//2
					((9-i)>>>23)))))))));//1				
				
			}					

			
			var time5:uint = getTimer();
			var AGAIN:int = 1000000;//1million
			var j:int;
			for(j=0;j<AGAIN;j++)
			{
				inc=1;max=10;
				for(i=0;i<REPS;)
				{
					absInt2 = (i >= 1000000000) ? 9 : (i >= 100000000) ? 8 : (i >= 10000000) ? 7 : 
						(i >= 1000000) ? 6 : (i >= 100000) ? 5 : (i >= 10000) ? 4 : 
						(i >= 1000) ? 3 : (i >= 100) ? 2 : (i >= 10) ? 1 : 0;
					if(i>=max)
					{	max*=10;
						inc*=10;
					}
					i+=inc;
				}
			}
			var time6:uint = getTimer();
			for(j=0;j<AGAIN;j++)
			{
				inc=1;max=10;
				for(i=0;i<REPS;)
				{
					absInt3 =(((999999999-i)>>31)&9)||
							((((99999999-i)>>31)&8)||
							(((9999999-i)>>>29)||//7
							((((999999-i)>>31)&6)||
							((((99999-i)>>31)&5)||
							((((9999-i)>>31)&4)||
							(((999-i)>>>30)||//3
							((((99-i)>>31)&2)||
							(((9-i)>>>31)))))))));//1
					
					if(i>=max)
					{	max*=10;
						inc*=10;
					}
					i+=inc;
				}					
			}
			var time7:uint = getTimer();
			for(j=0;j<AGAIN;j++)
			{
				inc=1;max=10;
				for(i=0;i<REPS;)
				{
					absInt4 =Memory.readUnsignedByte(((999999999-i)>>>31)||//9
						(((99999999-i)>>>30)||//8
							(((9999999-i)>>>29)||//7
								(((999999-i)>>>28)||//6
									(((99999-i)>>>27)||//5
										(((9999-i)>>>26)||//4
											(((999-i)>>>25)||//3
												(((99-i)>>>24)||//2
													((9-i)>>>23)))))))));//1				
					
					if(i>=max)
					{	max*=10;
						inc*=10;
					}
					i+=inc;
				}
			}
	
			var time8:uint = getTimer();
			
			
			startTest();
			setTest( "a=Math.logN(val)*ooLog_10;"   , "Log10", time2-time1 );
			setTest( "a=obvious if log10;"     		, "LinearDistribution Log10", time3-time2  );
			setTest( "a=ben log10;"     			, "LinearDistribution Log10", time4-time3  );
			setTest( "a=ben log10_2;"     			, "LinearDistribution Log10", time5-time4  );
			setTest( "a=obvious if log10;"     		, "LogDistribution Log10", time6-time5  );
			setTest( "a=ben log10;"     			, "LogDistribution Log10", time7-time6  );
			setTest( "a=ben log10_2;"     			, "LogDistribution Log10", time8-time7  );

			endTest();					
			
			
		}
Posted in bit twiddling, Math
Similar posts

Leave a Reply

Your email address will not be published. Required fields are marked *

Recent Posts

Recent Comments

Archives