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