Inverse square root revisited

A few years ago the algorithm included in Quake III Arena to calculate a quick approximation of the inverse square root became a common topic in blogs. This inverse square root is useful for calculating the angles of incidence and reflection of lighting and shader effects.

In fact a lot has already been written about this topic so, in order to save you some time, I want to start commenting that there is a machine instruction in the SSE (Streaming SIMD Extensions) set that should be much faster. This instruction is the rsqrt, in fact if we do not seek an exact square root the calculation of rsqrt (x) * x should be faster than the sqrt instruction, although the latter has more precision. Anyway, it is always better to test things out.

If you want to pursue the subject, the algorithm is discussed in this research paper from 2003.

float fastInvSqrt(float x) {
    float xhalf = 0.5f * x;
    int i = *(int *)&x; // Cast the number to integer
    i = 0x5f3759df - (i >> 1); // Magic number
    x = *(float*)&i; // Cast result back to float
    x = x*(1.5f-(xhalf*x*x)); // Apply one iteration of the Newton's method
    return x;
}

The magic number allows to approximate the inverse square root using integer arithmetic. In order to obtain it properties of logarithms and changes of representation between integer and floating point are used. At the end one iteration of Newton's method is applied.

The explanation is here.

Related entries:

Counting bits

The Atom text editor and Rust

Atom is a modern text editor developed in Javascript by the people responsible of GitHub. In their blog you can find many tips and tricks to enhance it. I have tried this editor and works really nicely. It has a good integration with GitHub. They have done a really good promotional video with vintage aesthetics. You should have a look:

One of the best things about this editor is that it has many plug-ins that will help us to develop in Rust, the new systems language developed by Mozilla. And it works really well!!! If we set these plug-ins properly we will have code auto-completion and error highlighting. I have made a guide to help you setting up everything. This is the list of plug-ins I have installed so far and the commands needed:

language-rust - Rust language support in Atom.

apm install language-rust

linter-rust - Lint rust files, using rustc and cargo. Checks for errors in the code

apm install linter

apm install linter-rust

racer - Intelligent rust code completion. This one is bit more tricky, you need also the racer binary:

Check if language-rust plug-in is installed

Follow the steps on github to install racer or use the binary provided by mozilla

apm install racer

Download the rust source code and extract it

Configure racer from atom: Set the paths to the racer executable and the Rust source code

rust-api-docs-helper - Allows to check the Rust standard library automatically

apm install rust-api-doc-helper

You get the idea. It is very easy!!! Once installed the plug-ins can be updated automatically.

I hope you like this entry. Please post your comments with your experiences and share this post with your friends. Have you tried other alternatives to develop in Rust?