blog.joa-ebert.com – Blog of Joa Ebert

For the hell of it I wanted to implement the fast inverse square-root that has been flying around in the Quake3 source-code for instance. Fantastic game by the way. There has been quiet a lot of talk about this algorithm. So can we do that with Flash? No we can not. It would be nice but it is simply not possible because you can not just map a Number into an int. With languages like C++ you can. So first of all: I found already an approach that is very fast but not as nearly as good as the original algorithm. It is also not the same “magic”. It is just some newton iterations and faster but worse then 1/Math.sqrt(x).

So what do you need to implement the original inverse square root algorithm? A way to convert any number to its four byte representation aka the way it is stored in memory. The original algorithm is freakin fast because it does not have to calculate the four bytes. It can just juggle with them. Since we have to insert some heavy math here our approach will always be slower but it helped me understanding IEEE single precision numbers a lot. Maybe anyone has a use for this?

Remember the isqrt function is WAY slower than doing 1/Math.sqrt(x)!

[as]private function isqrt( x: Number ): Number
{
var xhalf: Number = x * 0.5;
var i: int = toFloat( x );
i = 0×5f3759df – ( i >> 1 ); // the magic first guess
x = toNumber( uint(i) );
x = x * ( 1.5 – xhalf * x * x );
return x;
}

private function toNumber( x: uint ): Number
{
//– precheck here
if ( 0xffc00000 == x )
{
return NaN;
}
else
if ( 0×7f800000 == x )
{
return Number.POSITIVE_INFINITY;
}
else
if ( 0xff800000 == x )
{
return Number.NEGATIVE_INFINITY;
}

//– can not shift because flash doesnt like it…
var v: Boolean = uint( x & uint(0×80000000) ) == uint(0×80000000);
var e: int = ( uint( x >> uint(23) ) & 0xff ) – 127;
var m: int = x & 0×7fffff;
var n: Number;

//– if e > 0 we can do 2^e very easy by shifting it
//– otherwise we do 1/(2^e) and 2^e can be achieved by shifting it
if ( e > 0 )
{
n = ( 1 + m / ( 1 << 23 ) ) * ( 1 << e );
}
else
{
n = ( 1 + m / ( 1 << 23 ) ) * ( 1 / ( 1 << -e ) );
}

if ( v )
{
return -n;
}

return n;
}

private function toFloat( x: Number ): uint
{
//-- do a quick precheck
if ( Number.POSITIVE_INFINITY == x )
{
return 0x7f800000;
}
else
if ( Number.NEGATIVE_INFINITY == x )
{
return 0xff800000;
}
else
if ( isNaN( x ) )
{
return 0xffc00000;
}

//-- calculate ieee single precision
var v: Boolean, e0: int, e1: int, m: int;
var f: Boolean = x > 0;

if ( x > 0 )
{
e0 = int( Math.log( x ) / Math.LN2 );
m = ( ( x / ( 1 << e0 ) ) – 1 ) * ( 1 << 23 );
}
else
{
v = true;
e0 = int( Math.log( -x ) / Math.LN2 );
m = ( ( -x / ( 1 << e0 ) ) – 1 ) * ( 1 << 23 );
}

e1 = e0 + 127;

//– usually here would go the test for e1 = 0×00 or e1 = 0xff
//– BUT we tested already and that’s why we do not do it here

//– be save
e1 &= 0xff;
m &= 0×7fffff;

//– merge into 4bytes
var float: uint;

if ( v )
{
float = 0×80000000;
}

float |= e1 << 23;
float |= m;

return float;
}[/as]