Bill Ancalagon the black Bill Ancalagon the black - 5 months ago 26
Swift Question

Fastest Inverse Square Root on iPhone (Swift, not ObjectC)

Refer to
Fastest Inverse Square Root on iPhone

I need do a "Fastest Inverse Square Root" on iPhone iOS Swift, which is supposed to be faster than

1/sqrt(float)
.
How do I do it?

In embedded C programming, it is:

// Fast inverse square-root
// See: http://en.wikipedia.org/wiki/Fast_inverse_square_root
func invSqrt(x: Float) -> Float {
var halfx : Float = 0.5 * x
var y : Float = x
long i = *(long*)&y

i = 0x5f3759df - (i>>1)
y = *(float*)&i
y = y * (1.5 - (halfx * y * y))

return y
}

Answer

The only tricky part is how to do the forced conversions between floating point numbers and integer types, and the easiest way is to use memcpy():

// Fast inverse square-root
// See: http://en.wikipedia.org/wiki/Fast_inverse_square_root
func invSqrt(x: Float) -> Float {
    let halfx = 0.5 * x
    var y = x
    var i : Int32 = 0
    memcpy(&i, &y, 4)
    i = 0x5f3759df - (i >> 1)
    memcpy(&y, &i, 4)
    y = y * (1.5 - (halfx * y * y))
    return y
}

I made some performance tests on an iPhone 6s with 1.000.000 random floating point numbers in the range 0 ... 1000, and it turned out that invSqrt(x) is about 40% faster than 1.0/sqrt(x).

The maximal relative error was below 0.176%, confirming the bound in the Wikipedia article.

I also made a test with vvrsqrtf from the Accelerate framework, but this was actually slower than calling 1.0/sqrt(x), at least when called with single floating point numbers.


As of Swift 3, memcpy() can be replaced by the bitPattern: method of Float and the corresponding constructor from UInt32:

func invSqrt(x: Float) -> Float {
    let halfx = 0.5 * x
    var i = x.bitPattern
    i = 0x5f3759df - (i >> 1)
    var y = Float(bitPattern: i)
    y = y * (1.5 - (halfx * y * y))
    return y
}
Comments