John Carmack’s Unusual Fast Inverse Square Root (Quake III)

by

FYI. Carmack didn’t write it. Terje Mathisen and Gary Tarolli both take partial (and very modest) credit for it, as well as crediting some other sources.

How the mythical constant was derived is something of a mystery.

To quote Gary Tarolli:

Which actually is doing a floating
point computation in integer – it took
a long time to figure out how and why
this works, and I can’t remember the
details anymore.

A slightly better constant, developed by an expert mathematician (Chris Lomont) trying to work out how the original algorithm worked is:

float InvSqrt(float x)
{
    float xhalf = 0.5f * x;
    int i = *(int*)&x;              // get bits for floating value
    i = 0x5f375a86 - (i >> 1);      // gives initial guess y0
    x = *(float*)&i;                // convert bits back to float
    x = x * (1.5f - xhalf * x * x); // Newton step, repeating increases accuracy
    return x;
}

In spite of this, his initial attempt a mathematically ‘superior’ version of id’s sqrt (which came to almost the same constant) proved inferior to the one initially developed by Gary despite being mathematically much ‘purer’. He couldn’t explain why id’s was so excellent iirc.

More Related Contents:

  1. Writing your own square root function
  2. Floating Point Divider Hardware Implementation Details
  3. How best to sum up lots of floating point numbers?
  4. How can I convert between a double-double and a decimal string?
  5. Can a Fibonacci function be written to execute in O(1) time?
  6. Optimized low-accuracy approximation to `rootn(x, n)`
  7. How to convert decimal fractions to hexadecimal fractions?
  8. Find running median from a stream of integers
  9. How to find the lowest common ancestor of two nodes in any binary tree?
  10. Efficiency of purely functional programming
  11. Possible Interview Question: How to Find All Overlapping Intervals
  12. Time complexity of Sieve of Eratosthenes algorithm
  13. Getting the submatrix with maximum sum?
  14. Box stacking problem
  15. How to design an algorithm to calculate countdown style maths number puzzle
  16. What is a bubble sort good for? [closed]
  17. Creating a random number generator from a coin toss
  18. What is a loop invariant?
  19. How to express tetration function, for complex numbers
  20. Why does the greedy coin change algorithm not work for some coin sets?
  21. Hashing a Tree Structure
  22. Quicksort superiority over Heap Sort
  23. Best way of calculating n choose k?
  24. Why DFS and not BFS for finding cycle in graphs
  25. Finding multiple entries with binary search
  26. Given a number, find the next higher number which has the exact same set of digits as the original number
  27. Algorithm for permutations of operators and operands
  28. What are probabilistic data structures?
  29. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  30. Connected Component Labeling – Implementation

Leave a Comment