Skip to content

Instantly share code, notes, and snippets.

@juandesant
Last active January 23, 2023 12:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save juandesant/978f4e04024d57ba0f72f7a6ee0512c0 to your computer and use it in GitHub Desktop.
Save juandesant/978f4e04024d57ba0f72f7a6ee0512c0 to your computer and use it in GitHub Desktop.
"Fast" Inverse Square Root based on Quake's algorithm implemented in Swift
//Quick inverse square root using bit patterns
//Might be slower nowadays than using specific functions
// The following is the abridged version of the Quake function
// See more at https://en.wikipedia.org/wiki/Fast_inverse_square_root
//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;
//}
// We reimplement the function above in Swift
func Q_rsqrt(x: Float) -> Float {
// get binary floating point representation of x
var x_bits : UInt32; // We need a UInt32 to hold the bit-pattern for the Float
var half_x, result : Float;
half_x = x*0.5; // This is used later in the iteration. See wikipedia link above.
x_bits = x.bitPattern; // Instead of using pointer and casting trickery,
// we obtain the bit-pattern directly from the
// Swift floating point object
x_bits = 0x5f3759df - (x_bits >> 1); // We do the binary operation
new_float = Float(bitPattern: x_bits);// We use a Float creator that uses the bitPattern
new_float = new_float * (1.5 - (half_float*new_float*new_float)) // See wikipedia link
return new_float;
}
// Normal inverse of square root for
func rsqrt(x: Float) -> Float {
return 1/(x.squareRoot());
}
// The following allows running this algorithm in a Swift Playground, so that we can
// see values, or even graph them with time
var x :Float;
var y, y_, y_diff : Float;
for x in stride(from: 0.2, to: 64.2, by: 0.2) {
let y = Q_rsqrt(x: Float(x));
let y_ = rsqrt(x: Float(x));
let y_diff = abs(y-y_);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment