Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Inspired by Write a code golf problem in which script languages are at a major disadvantage question on meta, I've decided to make a question which could be problematic for scripting languages.

The goal is to calculate fast inverse square root, just like it was done in Quake III Arena. You will get the floating point number as first argument after program name and you should implement it. Simply doing ** -0.5 is disallowed as it doesn't implement the algorithm.

Your program will be called like this. The 12.34 could be other value.

$ interpreter program 12.34 # for interpreted languages
$ ./a.out 12.34 # for compiled languages

For comparison, this is original Quake III Arena implementation.

float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;                       // evil floating point bit level hacking
        i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//      y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

        return y;
}

You have to do just one iteration because the second was commented out.

Winning condition: Shortest code.

share|improve this question
    
can you clarify what is meant by You will get the floating point number as first argument after program name and you should implement it. ? –  ardnew Nov 19 '12 at 22:52
    
What is 0x5f3759df supposed to be in decimal? –  beary605 Nov 20 '12 at 1:27
    
@beary605: the value is discussed pretty extensively on the wikipedia article –  ardnew Nov 20 '12 at 2:34
    
@ardnew: Clarified that by examples of calling the program. –  xfix Nov 20 '12 at 5:12

4 Answers 4

up vote 2 down vote accepted

Perl, 89 85 chars

includes the necessary symbols for declaring and implementing a function

edit: standalone program. receives input parameter as command line argument

$_=unpack'f',pack'i',0x5f3759df-unpack('i',pack'f',$n=shift)/2;
print$_*1.5-$n/2*$_**3
share|improve this answer

vba, 171

Type x
q As Long
End Type
Type z
w As Single
End Type
Function q(n)
Dim i As x,y As z
x=n/2
y.w=n
LSet i=y
i.q=&H5F3759DF-i.q/2
LSet y=i
q=y.w*(1.5-x*y.w*y.w)
End Function

finding a way to do the pointer cast was the hardest part. unfortunately, as there is no real direct way, I had to define my own type, which added to the length of the program

call from the immediate window with ?q(number)

result:

?2^-0.5
0.707106781186548
?q(2)
0.706930038698333

share|improve this answer
2  
+1 for the ridiculosity of using a BASIC dialect to golf a performance-related problem. –  leftaroundabout Nov 22 '12 at 20:14
    
Smaller solution: Type x:q&:End Type:Type z:w As Single:End Type:Function q(n):Dim i As x,y As z:x=n/2:y.w=n:LSet i=y:i.q=&H5F3759DF-i.q/2:LSet y=i:q=y.w*(1.5-x*y.w*y.w):End Function –  toothbrush Feb 22 at 14:20

C#, 157 chars

Horrible for golfing, but why not...

class C{unsafe static void Main(string[]a){var n=float.Parse(a[0]);var i=*(int*)&n/-2+0x5f3759df;var y=*(float*)&i;System.Console.Write(y*1.5f-y*n/2f*y*y);}}

Readable version:

class C
{
    unsafe static void Main( string[] a )
    {
        var n = float.Parse( a[0] );
        var i = *(int*) &n / -2 + 0x5f3759df;
        var y = *(float*) &i;
        System.Console.Write( y * 1.5f - y * n / 2f * y * y );
    }
}
share|improve this answer

C, 173 chars

Might as well put code golfed version of example above. Could be less if I would ignore portability.

#include<stdio.h>
#include<stdint.h>
main(int _,char**a){float n,g;sscanf(a[1],"%f",&n);int32_t o=0x5f3759df-(*(long*)&n>>1);g=*(float*)&o;printf("%g\n",g*(1.5-(n/2*g*g)));}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.