3 ms·
There's a little gem buried in the story. The algorithm for logarithms. A lot of HN readers are familiar with Charles Babbage's Difference Engine, and his more
by credit_guy 5y ago
There's a little gem buried in the story. The algorithm for logarithms.
A lot of HN readers are familiar with Charles Babbage's Difference Engine, and his more revolutionary Analytical Engine (and the connection with Ada Lovelace, who wrote the first computer program). The whole point of the Difference Engine was to automatically create tables of logarithms, and other non-elementary functions, like sin, tan, etc.
Well, Feynman's trick could have easily been conceived by a smart fellow back in Babbage's time, and would have made the Difference Engine irrelevant (which it was anyway, since Babbage failed to build it).
Anyway, here's a simple example how this algorithm works, using base 10 rather than 2, to make it more readable.
First, we use the same observation of "range reduction" to say that we only need to concern ourselves with logs of numbers between 1 and 2. Let's say we want to create a table of all the 1000 numbers between 1 and 2 given with 3 decimal accuracy.
Let's pick a number: 1.382. The trick is to stick in an increasing number of zeros after the decimal place.
We start by dividing 1.382 by 1.300. We precompute the reciprocal and logarithm of 1.300 (as well as all the other 26 "elementary numbers" which start with 1. and have a single non-zero decimal). log(1.300) = 0.262; we keep this in an accumulator. The division 1.382/1.300 = 1.063 has one zero after the decimal place. We now dive this by 1.060 and get 1.003; we add the log(1.060)=0.058 to the accumulator and get 0.321. Finally, 1.003 has the log 0.003, we add this to the accumulator and end up with 0.324. The actual result is 0.32353, which indeed rounds up to 0.324. In some cases the last digit will be off by 1.
Why do you need to precompute the reciprocals of the "elementary numbers", not just their logarithms? Because this way dividing by them amounts to doing a multiplication, which is cheaper on many machines. This is how you end up with a log operation taking less than a division, as claimed in the article.