Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
0x5f3759df - Quake III Arena's Fast Inverse Square Root Function Explained
<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 -->
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);
}
}
}
.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;
}
<link href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.min.css" rel="stylesheet" />
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.