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:
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,
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(); }
Leave a Reply