Uint( Math.sqrt(i) )

1

For those interested in performance benchmarks the following tests the performance of an integer square root algorithm (coded in Actionscript) against the equivalent Actionscript call:

uint(Math.sqrt(i))


//-------------------------------------------------------------------------------------------------
// Test an alternative to uint( Math.sqrt() )  
//-------------------------------------------------------------------------------------------------

var i:uint;
var t1:Number;
var t2:Number;
var t3:Number;
var temp:uint; 
var val:uint;
var g:uint=0; 
var b:uint = 0x8000; 
var bshft:uint = 15;
var same:Boolean;

trace("");
trace("Accuracy and performance test of an integer sqrt function.");
trace("----------------------------------------------------------");

//-------------------------------------------------------------------------------------------------
// demonstrate julery_isqrt(i) == uint(Math.sqrt(i)
//-------------------------------------------------------------------------------------------------
trace("");
trace(" Are the return values of both sqrt functions the same? "); 

// propose that both results are the same
same = true;
// attempt to falsify this proposition
for(i=0;i<1000000;i++){
    if( julery_isqrt(i) != uint( Math.sqrt(i)) ) same=false;
}
if(same) trace(" Yes they are.");
else trace("  No they're not.");

//-------------------------------------------------------------------------------------------------
// use getTime to record the number of cycles spent by each algorithm for a million square roots
//-------------------------------------------------------------------------------------------------

//-------------------------------
t1= getTimer();
//-------------------------------
for(i=0;i<1000000;i++) 
{
    [COLOR=Blue]uint(Math.sqrt(i)) ;[/COLOR]
}
//-------------------------------
t2= getTimer();
//-------------------------------
for(i=0;i<1000000;i++) 
{
    [COLOR=Blue]val = i; do { if (val >= (temp = (((g << 1) + b) << bshft-- ))) { g += b; val -= temp; } } while (b >>= 1); [/COLOR]   
}
//-------------------------------
t3= getTimer();
//-------------------------------

trace("");
trace(" Function             Execution time" );
trace(" --------             --------------");
trace(" uint(Math.sqrt(i))   " + String (t2-t1) + " ms " );
trace(" julery_isqrt(i)      " + String (t3-t2) + " ms " );

//-------------------------------------------------------------------------------------------------
//  Jim Ulery's algorithm as a function call (function calls are less efficient than inline code
//-------------------------------------------------------------------------------------------------

function julery_isqrt(val:uint):uint 
{
   /* by Jim Ulery */
   
        var temp:uint; 
        var g:uint=0; 
        var b:uint = 0x8000; 
        var bshft:uint = 15;
        
        do 
        {
            if (val >= (temp = (((g << 1) + b) << bshft-- ))) 
            {
               g += b;
               val -= temp;
            }
        } 
        while (b >>= 1);
        return g;
}

And the results:


Accuracy and performance test of an integer sqrt function.
----------------------------------------------------------

 Are the return values of both sqrt functions the same? 
 Yes they are.

 Function             Execution time
 --------             --------------
 uint(Math.sqrt(i))   313 ms 
 julery_isqrt(i)      219 ms