Richard Feynman and the Connection Machine (1989)

> By the end of that summer of 1983, Richard had completed his analysis of the behavior of the router, and much to our surprise and amusement, he presented his answer in the form of a set of partial differential equations. To a physicist this may seem natural, but to a computer designer, treating a set of boolean circuits as a continuous, differentiable system is a bit strange. Feynman’s router equations were in terms of variables representing continuous quantities such as “the average number of 1 bits in a message address.” I was much more accustomed to seeing analysis in terms of inductive proof and case analysis than taking the derivative of “the number of 1’s” with respect to time. Our discrete analysis said we needed seven buffers per chip; Feynman’s equations suggested that we only needed five. We decided to play it safe and ignore Feynman.

How is it possible to use PDEs to model boolean circuits?

If you don't have a real multiplier[2], then the algorithm described is somewhat attractive because multiplying by 1/(1+2^-k) has a nice series expansion. You can do it using only shifts and adds (and the number of terms you need is O(1/k), so it falls off reasonably quickly), and you get the part you need to compute the next `k` early, so there's no serial dependency. Actually finding k is just a count-leading-zeros operation, which is cheap enough.

Computers today pretty much all have real multipliers, so no one does this. Instead we reduce to a range like [1/sqrt(2),sqrt(2)], and then either use a minimax approximation on that interval (if the accuracy requirement is reasonably low) or further reduce by looking up a value of r close to x for which we have a pre-computed 1/r and log(r) and take advantage of:

    log(x) = log(r * 1/r * x) = log(r) + log(1/r * x)

[1] If you have a fast approximate exp and log you can make use of it in an approximate N-R iteration, but it still doesn't buy you much. In practice no one does this; we compute exp and log directly, and they're among the fastest functions in the math library.

[2] Meaning either you don't have one at all or that it's much, much slower than addition, as was common in the 1980s and earlier.

[3] This trick is called "Gal's Accurate Tables" (https://en.wikipedia.org/wiki/Gal's_accurate_tables), but as with most things named for someone, it was independently invented multiple times, and likely dates back decades before the credited inventor.

representing continuous quantities such as “the average number of 1 bits in a message address.”

suggested to me that maybe he recast it as a system dynamics problem? I'm a little out of my depth here, though.

Maybe this was meant to be a fast rough approximation? 1 + 1/2^-m + 1/2^-n ~= (1+1/2^-m)(1+1/2^-n). So check each bit in a fixed-point int and add a factor from a table for each 1 bit found? Then run a few rounds of Newton iteration at the end if you want it a little less rough? This goes well with the SIMD nature of the machine -- they broadcast single-bit ops one by one to all processors in parallel -- but maybe it's terrible numerically, I haven't checked.