7 people like it.
Like the snippet!

Fast inverse square root

This is an implementation of the famous 'magic number' method of rapidly calculating (inverse) square roots. (See http://en.wikipedia.org/wiki/Fast_inverse_square_root.) In practice, this version is no faster in F# than using 1./sqrt(x). I've posted it as an example of how you can get down-and-dirty with the bits in F# if you need to.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34:

// For comparison, the original-ish C code is this:
//
//    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 f***?
//            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;
//    }
//
let fastInvSqrt (n : float32) : float32 =
    let MAGIC_NUMBER : int32 = 0x5f3759df 
    let THREE_HALVES = 1.5f
    let x2 = n * 0.5f
    let i = MAGIC_NUMBER - (System.BitConverter.ToInt32(System.BitConverter.GetBytes(n), 0) >>> 1)
    let y = System.BitConverter.ToSingle(System.BitConverter.GetBytes(i), 0)
    y * (THREE_HALVES - (x2 * y * y))

// Examples:

let x = fastInvSqrt 4.0f
// Output: val x : float32 = 0.499153584f

let x' = 1. / sqrt(4.0)
// Output: val x' : float = 0.5

val fastInvSqrt : n:float32 -> float32

Full name: Script.fastInvSqrt

val n : float32

Multiple items
val float32 : value:'T -> float32 (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float32

--------------------
type float32 = System.Single

Full name: Microsoft.FSharp.Core.float32

--------------------
type float32<'Measure> = float32

Full name: Microsoft.FSharp.Core.float32<_>

val MAGIC_NUMBER : int32

Multiple items
val int32 : value:'T -> int32 (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int32

--------------------
type int32 = System.Int32

Full name: Microsoft.FSharp.Core.int32

val THREE_HALVES : float32

val x2 : float32

val i : int32

namespace System

type BitConverter =
  static val IsLittleEndian : bool
  static member DoubleToInt64Bits : value:float -> int64
  static member GetBytes : value:bool -> byte[] + 9 overloads
  static member Int64BitsToDouble : value:int64 -> float
  static member ToBoolean : value:byte[] * startIndex:int -> bool
  static member ToChar : value:byte[] * startIndex:int -> char
  static member ToDouble : value:byte[] * startIndex:int -> float
  static member ToInt16 : value:byte[] * startIndex:int -> int16
  static member ToInt32 : value:byte[] * startIndex:int -> int
  static member ToInt64 : value:byte[] * startIndex:int -> int64
  ...

Full name: System.BitConverter

System.BitConverter.ToInt32(value: byte [], startIndex: int) : int

System.BitConverter.GetBytes(value: float) : byte []
System.BitConverter.GetBytes(value: float32) : byte []
System.BitConverter.GetBytes(value: uint64) : byte []
System.BitConverter.GetBytes(value: uint32) : byte []
System.BitConverter.GetBytes(value: uint16) : byte []
System.BitConverter.GetBytes(value: int64) : byte []
System.BitConverter.GetBytes(value: int) : byte []
System.BitConverter.GetBytes(value: int16) : byte []
System.BitConverter.GetBytes(value: char) : byte []
System.BitConverter.GetBytes(value: bool) : byte []

val y : float32

System.BitConverter.ToSingle(value: byte [], startIndex: int) : float32

val x : float32

Full name: Script.x

val x' : float

Full name: Script.x'

val sqrt : value:'T -> 'U (requires member Sqrt)

Full name: Microsoft.FSharp.Core.Operators.sqrt

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/9M
Posted:	12 years ago
Author:	Kit Eason
Tags:	fast inverse square root; bitwise