Hiroshi Hayashi

1/sqrt(x) is complicated. Imagine instead of computing 1/sqrt(x), imagine instead that you wanted to compute exp_2(-.5 log_2(x)). Also imagine you have an ultra fast way to compute exp_2 and log_2. If you have an ultra fast way to compute exp_2 and log_2, then exp_2(-.5 log_2(x)) is gonna be fast to compute.

It turns out you do have an ultra fast way to compute log_2: you bitcast a float to an integer, and then twiddle some bits. The first 8 bits (after the sign bit, which is obviously zero because we're assuming our input is positive) or whatever are the exponent, and the trailing 23 bits are a linear interpolation between 2^n and 2^(n+1) or whatever. exp_2 is the same but in reverse.

You can simply convert the integer to floating point, multiply by -.5, then convert back to integer. But multiplying -.5 by x can be applied to a floating point operating directly on its bits, but it's more complicated. You'll need to do some arithmetic, and some magic numbers.

So you're bitcasting to an integer, twiddling some bits, twiddling some bits, twiddling some bits, twiddling some bits, and bitcasting to a float. It turns out that all the bit twiddling simplifies if you do all the legwork, but that's beyond the scope of this post.

So there you go. You've computed exp_2(-.5 log_2 x). You're done. Now you need to figure out how to apply that knowledge to the inverse square root.

It just so happens that 1/sqrt(x) and exp(-.5 log x) are the same function. exp(-.5 log x) =…

> L1. There are gaps out there.

I had a similar experience. At one point I decided that I wanted to understand, step by step, how Ada Lovelace's Bernoulli program works[1]. There was a few steps that didn't seem right to me but I was sure if there were any bugs in there they would be well-known and mentioned somewhere I could find. This being one of the most iconic and historically significant programs ever written. Indeed I found more than one person claiming that the program was known to be correct.

It took a long time before I could believe that it wasn't just me not getting it, there were indeed a few things out of place and apparently there was just no mention of it anywhere on the web or in any of the research into the analytical engine I could get my hands on.

[1]: http://h14s.p5r.org/2012/12/bernoulli.html

Thanks for sharing that. I've actually been learning some Forth recently and had been wondering how a parser or a compiler might actually look using Forth, and you actually already made one, which is pretty cool. I was wondering this because deterministic parsers are often already stack based (LL and LR parsers can both be implemented as imperative programs that manipulate a stack based on the input tokens, or just recursive descent).

I still can't really understand everything just from reading the code, but I had assumed it would be some kind of explicitly stack-based state machine precedence parser, like this article describes: https://h14s.p5r.org/2014/10/shiftreduce-expression-parsing-by-douglas-gregor.html

Kind of looks like you did that in expr.fs? Not completely sure, though.

Carmack also started a rocket company at a time when it was much more difficult to do so (there were far fewer government dollars available via contracts), Bezos also has far more capital to put in than Carmack.

Not undeservingly Carmack is something of a folk hero here (for example: http://h14s.p5r.org/2012/09/0x5f3759df.html) but I don't think being a 10X programmer necessarily translates into great rocket company CEO and in terms of entrepreneurial and organizational skill Bezos excels (at least based on Amazon's success).