0x5f3759df - Quake III Arena's Fast Inverse Square Root Function Explained

0x5f3759df-quake-iii-arena-s-fast-inverse-square-root-function-explained.markdown

0x5f3759df - Quake III Arena's Fast Inverse Square Root Function Explained

A Pen by Mo Ismailzai on CodePen.

License.

See http://www.moismailzai.com/0x5f3759df/

index.html

<div class="container-fluid">
  <div class="row">
    <div class="col-xs-12">
      <div class="well well-lg">
        <div class="row">
          <div class="col-xs-5">
            <div class="input-group">
              <input type="text" class="form-control" id="input-value" placeholder="Select a positive number">
              <span class="input-group-btn">
                <button class="btn btn-default" type="button" onclick="explainFastInverseSquareRoot('input-value', 'explanations-div')">Go!</button>
              </span>
            </div>
          </div>
          <div class="col-xs-7"></div>
        </div> <!-- end row -->
        <div class="row">
          <div class="col-xs-12" id="explanations-div">
          </div> <!-- end explanations-div -->
        </div>
      </div> <!-- end well -->
    </div> <!-- end main col -->
  </div> <!-- end main row -->
</div> <!-- end container -->

script.js

var MAGIC_CONSTANT = 0x5f3759df; // derived from the depths of ether

function getBitViews(float, int) {
  var buffer = new ArrayBuffer(8),
      intView = new Int32Array(buffer),
      floatView = new Float32Array(buffer);
  if (float) {
    floatView[0] = float;
  } else if (int) {
    intView[1] = int;
  }
  return {  "buffer": buffer,
            "intView": intView,
            "floatView": floatView
         };
}

function getBitsAsIntValue(num) {
  var buffer = getBitViews(num).floatView.buffer;
  return new Int32Array(buffer)[0];
}

function getBitsAsFloatValue(num) {
  var buffer = getBitViews(false, num).floatView.buffer;
  return new Float32Array(buffer)[1];
}

function getPrettyFloatDiv(floatBitsAsString) {
  var myDiv = document.createElement("div");
  myDiv.className = "block-text";
  for (x = 0; x < floatBitsAsString.length; x++) {
    var mySpan = document.createElement("span");
    if (x > 8) {
      mySpan.className = "big-text floatbit-man";
    } else if (x < 9 && x > 0) {
      mySpan.className = "big-text floatbit-exp";
    } else {
      mySpan.className = "big-text floatbit-sign";
    }
    mySpan.innerHTML = floatBitsAsString[x];
    myDiv.appendChild(mySpan);
  }
  return myDiv;
}

function getRow(explanation, text) {
  var myRow = document.createElement("div"),
      myCol = document.createElement("div"),
      myExplanation = document.createElement("div"),
      myText = document.createElement("div");
  myRow.className = "row";
  myCol.className = "col-xs-12";
  myExplanation.className = "title-text";
  myText.className = "big-text block-text";
  myRow.appendChild(myCol);
  myCol.appendChild(myExplanation);
  myCol.appendChild(myText);
  myExplanation.innerHTML = explanation || "";
  if (text && text.length === 32 && /^[01]+$/.test(text)) { // prettify binary strings
    myCol.appendChild(getPrettyFloatDiv(text));
  } else {
    myText.innerHTML = text || "";
  }
  return myRow;
}

function getPercentageDifference(firstNum, secondNum) {
  return Math.abs((firstNum / 1) - (secondNum)) / (((firstNum / 1) + (secondNum))/2) * 100;
}

function renderElementToDivId(element, divId) {
  var myDiv = document.getElementById(divId);
  myDiv.appendChild(element);
}

function parseFloat(float) {
  var myUnsignedFloat = Math.abs(float), // can't root a negative so ignore sign
      bitsAsIntValue = getBitsAsIntValue(myUnsignedFloat),
      parsed = {
        "asFloat": myUnsignedFloat,
        "asInt": bitsAsIntValue,
        "asIntShiftedRight": bitsAsIntValue >> 1,
        "asString": "0" + bitsAsIntValue.toString(2), // adding leading 0 as sign bit because javascript omits these for positive numbers
      },
      goodGuess = {
        "asFloat": getBitsAsFloatValue(MAGIC_CONSTANT - parsed.asIntShiftedRight),
        "asInt": MAGIC_CONSTANT - parsed.asIntShiftedRight,
        "asString": (MAGIC_CONSTANT - parsed.asIntShiftedRight).toString(2)
      };
  parsed.inverseSquareRoot = {
    "goodGuess": goodGuess,
    "newtonGuess": getBitsAsFloatValue(goodGuess.asInt) * (1.5 - ( (parsed.asFloat * 0.5) * (Math.pow(getBitsAsFloatValue(goodGuess.asInt),2)))),
    "actual": 1 / Math.sqrt(parsed.asFloat)
  };
  parsed.error = {
    "newtonGuessFromActual": getPercentageDifference(parsed.inverseSquareRoot.newtonGuess, parsed.inverseSquareRoot.actual),
    "goodGuessFromActual": getPercentageDifference(parsed.inverseSquareRoot.goodGuess.asFloat, parsed.inverseSquareRoot.actual),
  };
  return parsed;
}

function getExplanations(parsedInput) {
  return {
    "step1" : {
      "explanation": "According to the IEEE Standard for Floating-Point Arithmetic (IEEE 754), the 32-bit formulaic representation of the number <b>" + parsedInput.asFloat + "</b> is:",
      "text": parsedInput.asString
    },
    "step2" : {
      "explanation": "Lets ignore the IEEE 754 encoding and consider the bits \"" + parsedInput.asString + "\" as a base2 binary integer... their base10 decimal equivalent is:",
      "text": parsedInput.asInt
    },
    "step3" : {
      "explanation": "Now lets right-shift the bits in \"" + parsedInput.asString + "\" by 1 position, and again consider the remaining bits as a base2 binary integer... their base10 decimal equivalent is now:",
      "text": parsedInput.asIntShiftedRight
    },
    "step4" : {
      "explanation": "Next, lets subtract this integer value from the magic hexadecimal constant, \"0x5f3759df\". In decimal notation, that is " + MAGIC_CONSTANT + " - " + parsedInput.asIntShiftedRight + ", which yields:",
      "text": parsedInput.inverseSquareRoot.goodGuess.asInt
    },
    "step5" : {
      "explanation": "We don't care about the <em>value</em> of this number, instead, we use its base2 binary representation, \"" + parsedInput.inverseSquareRoot.goodGuess.asString + "\", as though it were an IEEE 754 compliant 32-bit formulaic representation. The number that is derived from this process will serve as our Good Guess for the Newton–Raphson Method of finding roots:",
      "text": parsedInput.inverseSquareRoot.goodGuess.asFloat
    },
    "step6" : {
      "explanation": "Finally, we throw it to the homeboy Isaac Newton, who said the best way to guess roots is: <b>Good Guess * (1.5 - ( (21*.5) * Good Guess^2 ) )</b>. When we plug our Good Guess™ value into this equation, we're left with an inverse square root approximation of:",
      "text": parsedInput.inverseSquareRoot.newtonGuess
    },
    "step7" : {
      "explanation": "How good an approximation is that? Well the actual inverse square root of " + parsedInput.asFloat + " is:",
      "text": parsedInput.inverseSquareRoot.actual
    },
    "step8" : {
      "explanation": "Which means that the error between the actual root and our approximation of it was only:",
      "text": parsedInput.error.newtonGuessFromActual.toPrecision(4) + "%"
    },
    "step9" : {
      "explanation": "But even more impressive, the error between the Good Guess (which we cobbled together by shifting binary bits and subtracting a constant) and the actual inverse square root of " + parsedInput.asFloat + " is only:",
      "text": parsedInput.error.goodGuessFromActual.toPrecision(4) + "%"
    }
  };
}

function explainFastInverseSquareRoot(inputId,outputId) {
  var input = +document.getElementById(inputId).value,
      parsedInput = parseFloat(input),
      explanations = getExplanations(parsedInput);
  document.getElementById(outputId).innerHTML="";
  if (input < 0) {
    alert("We're searching for roots so please type in a positive value.");
    return;
  }
  for (var step in explanations) {
    if (explanations.hasOwnProperty(step)) {
      renderElementToDivId(getRow(explanations[step].explanation, explanations[step].text), outputId);
    }
  }
}

style.css

.big-text {
  font-size: x-large;
  padding: 0.1em;
}
.block-text {
  display: block;
}
.title-text {
  font-family: monospace;
  margin-top: 2em;
}
.floatbit-sign {
  color: red;
}
.floatbit-exp {
  color: blue;
}
.floatbit-man {
  color: green;
}

styles

<link href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.min.css" rel="stylesheet" />