gistfile1.pde

// benchmark different sqrt implementations


void setup ()
{
    int runs = 100000;
    
    long ts = System.currentTimeMillis();
    for ( int i=0; i < runs; i++ )
    {
        fsqrt( random( 1000 ) );
    }
    long ts1 = System.currentTimeMillis() - ts;
    
    ts = System.currentTimeMillis();
    for ( int i=0; i < runs; i++ )
    {
        ffsqrt( random( 1000 ) );
    }
    long ts2 = System.currentTimeMillis() - ts;
    
    ts = System.currentTimeMillis();
    for ( int i=0; i < runs; i++ )
    {
        fastSqrt( random( 1000 ) );
    }
    long ts3 = System.currentTimeMillis() - ts;
    
    ts = System.currentTimeMillis();
    for ( int i=0; i < runs; i++ )
    {
        Math.sqrt( random( 1000 ) );
    }
    long ts4 = System.currentTimeMillis() - ts;
    
    ts = System.currentTimeMillis();
    for ( int i=0; i < runs; i++ )
    {
        invSqrt( random( 1000 ) );
    }
    long ts5 = System.currentTimeMillis() - ts;
    
    println( "fsqrt:\t\t"+     (ts1/(double)1000) );
    println( "ffsqrt:\t\t"+    (ts2/(double)1000) );
    println( "fastSqrt:\t\t"+  (ts3/(double)1000) );
    println( "Math.sqrt:\t\t"+ (ts4/(double)1000) );
    println( "invSqrt:\t\t"+   (ts5/(double)1000) );
}
 
// http://forum.java.sun.com/thread.jspa?threadID=580870&messageID=9478082
public static float fsqrt(float x)
{
    if (x ==0) return 0;
 
    float root = x / 2;
    for (int k = 0; k < 10; k++)   // adjust k for accurancy
	root = (root + (x / root)) / 2;
    return root;
}

// http://forum.java.sun.com/thread.jspa?threadID=580870&messageID=2944247
public static float ffsqrt(float n)
{
    if(n==0) return 0;
    if(n==1) return 1;
 
    float guess = n/2.0;
    float oldguess = 0;
    while(guess!=oldguess)
    { 
        oldguess=guess;
        guess = (guess+n/guess)/2.0;
    }
    return guess;
}

// http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
public static float fastSqrt (float val)
{ 
    int tmp = Float.floatToIntBits(val);
    tmp -= 1<<23;     /* Remove last bit to not let it go to mantissa */
                      /* tmp is now an approximation to logbase2(val) */
    tmp = tmp >> 1;   /* divide by 2 */
    tmp += 1<<29;     /* add 64 to exponent: (e+127)/2 =(e/2)+63, */
                      /* that represents (e/2)-64 but we want e/2 */
    return Float.intBitsToFloat(tmp);
}

// sorry, can't remember where this came from .. any pointers?
public static float invSqrt(float x)
{
     float xhalf = 0.5f*x;
     int i = Float.floatToIntBits(x);
     i = 0x5f3759df - (i >> 1);
     x = Float.intBitsToFloat(i);
     x = x * (1.5f - xhalf * x * x);
     return 1.0f/x;
}