5 ms·

I came across this before and found the section "An Algorithm For Logarithms" interesting. As pointed out (in second para. of that section) Feynman's observati

by ocfnash 10y ago

I came across this before and found the section "An Algorithm For Logarithms" interesting. As pointed out (in second para. of that section) Feynman's observation about representing a number as product of terms of the form $1 + 2^{-k}$ reduces the problem of estimating log to computing those values k which appear in the product. (Btw the article incorrectly claims the representation is unique.) There's an obvious linear time algorithm for finding a sequence of values k but I don't think that would really perform so well compared to, say, Newton-Raphson. So I wonder why this was a good approach. Perhaps there's a smart way to estimate the k or perhaps it just happened to fit the constraints under which they were working. Anyone have some insights?

stephencanon 10y ago
Newton-Raphson doesn't buy you much for logarithms, because the iteration itself involves either exp(x) or log(x)[1]. 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) this allows one to achieve high-accuracy results if r is chosen so that one of 1/r and log(r) is exact and the other is unusually close to the exact value[3], or stored in extended precision. [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 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.
- ocfnash 10y ago
  Thanks for these remarks Stephen. IIUC you're speculating that the relevant constraint they faced was that multiplication was very burdensome. I agree; it seems plausible this was the reason they found this an attractive approach. Also agreed about Newton-Raphson; that was a thinko on my part. It would be an unusual situation if NR were the right tool for estimating log.
abecedarius 10y ago
It might be relevant that the CM-1's processors were tiny: they had a 1-bit word size. 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.
- ocfnash 10y ago
  Thanks, this is a good point: we have no idea how accurate they wished to be.

by ocfnash 10y ago

stephencanon 10y ago

Newton-Raphson doesn't buy you much for logarithms, because the iteration itself involves either exp(x) or log(x)[1]. 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) this allows one to achieve high-accuracy results if r is chosen so that one of 1/r and log(r) is exact and the other is unusually close to the exact value[3], or stored in extended precision. [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 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.

ocfnash 10y ago
Thanks for these remarks Stephen. IIUC you're speculating that the relevant constraint they faced was that multiplication was very burdensome. I agree; it seems plausible this was the reason they found this an attractive approach. Also agreed about Newton-Raphson; that was a thinko on my part. It would be an unusual situation if NR were the right tool for estimating log.

abecedarius 10y ago

It might be relevant that the CM-1's processors were tiny: they had a 1-bit word size. 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.

ocfnash 10y ago
Thanks, this is a good point: we have no idea how accurate they wished to be.