|
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); |
|
} |
|
} |
|
} |