CODEWITHSUNDEEP
swiftsqrt
Ancalagon BerenLuthien
Ancalagon BerenLuthien

Reputation: 1194

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
}

Upvotes: 0

Views: 834

Answers (1)

Martin R
Martin R

Reputation: 539865

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
}

Upvotes: 6

Related Questions