What is elegant code?

Code can be beautiful, so how does this differ from elegant code? Elegant code uses cleverness to accomplish something in much less code than most people would think possible, but in a way that’s readable and obvious. In some respects, the recursive form of Towers of Hanoi is elegant. It uses the cleverness of recursion to produce a program able to solve the problem in much less code than the non-recursive version. Is the solution obvious? Yes, to a point. If you don’t understand the intricacies of recursion, this version of ToH will be difficult to comprehend.

Here is another example, the Fast Inverse Square Root code, found in the game Quake. All it does is basically calculate (1/√x). You’re thinking, why not calculate the square root, and divide in the regular way? Well, division, and square root calculation are expensive (or at least they use to be). So looking for a better way of performing this in a program which may use the calculation millions of times a second may be important – nobody likes slow games. Here is the code for the function invSqrt(), (obviously in C), derived from the original code:

1  float invSqrt(float x){
2     long i;
3     float x2, y;
4     x2 = x * 0.5F;
5     i = *(long*)&x;
6     i = 0x5f3759df - (i >> 1); 
7     y = *(float*)&i;
8     y = y*(1.5F - x2*y*y);
9     return y;
10 }

It calculates the inverse to the square-root using only multiplication and bit-shift operations. Fast? Yes. Elegant? Yes, but again to a point (you have to have a working knowledge of bit-shift operations). To the lay-person it does seem like some form of bizarre Harry Potter magic. It isn’t exactly readable.

But how does it work? Basically it takes the the real number, and negates and halves the exponent to obtain an approximation of the inverse square root. It then calculates one round of Newton’s approximation to refine the estimate. Let’s take a quick closer look at what is going on. In C, a float is stored as a 32-bit number: 1 bit for the sign, 8 bits for the exponent and 23 bits for the number.

  1. The line of code on Line 5 of the function represents the 32-bit float as an integer, stored in the long int variable i.
  2. In Line 6 of the code, the 32-bit integer is shifted right by 1. This basically divides the integer representation by 2, but does crazier things if the same number were interpreted as a float.
  3. In the same line, the bit-shifted number is subtracted from 0x5f3759df, a so-called “magic number” (see there *is* magic involved).
  4. In Line 7, the integer is re-interpreted as a float (y), and its value will hold an initial guess of the inverse square root of x.
  5. Lastly in Line 8, one iteration of Newton-Raphson iteration is performed, to refine the estimate.

Does it work? Yes. Is it truly elegant? That, is in the eye of the beholder.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.