Logarithms, Tables, and Babylonians
On pre-computation methods for speeding up algorithms
John Napier is the discoverer of logarithms, and was sometimes called the “Marvellous Merchiston,” which is a pretty neat name. His publication, in 1614, of his book entitled “Mirifici Logarithmorum Canonis Descriptio” was a milestone for science. This work changed science at the time—it made calculations possible that were previously impossible.
Today I want to talk about logarithms as an example of a more general principle: when can pre-computed tables be used to speed up computations?
Some credit Michael Stifel with discovering logarithms years before Napier, but Napier’s book included ninety pages of log tables that made them a practical tool. They were used by scientists of all kinds—including apparently astrologists.
Stifel did make important advances in mathematical notation: he was the first to use juxtaposition to denote multiplication, for example. I should have included his work in our recent discussion on notation. Stifel also tried his hand at predictions: he predicted the world would end at 8am on October 19, 1533. This points out a key rule for anyone who attempts to make predictions:
A prediction should be vague in effect or far in the future or both.
I ran across an interesting discussion of how log tables were used at Cambridge during math exams. Students were allowed to bring only basic tools such as a compass, a protractor and writing instruments to an exam. They were checked carefully as they entered the examination room to see if they might have any notes or other forbidden materials with them. They could also bring a special book of logarithms—it was often checked for illegal notes.
I learned how to use logarithms at Massapequa High School, not at Cambridge. In his first lecture on logarithms, our math teacher explained that we would each be supplied with a special printed sheet of paper whenever we were tested. These sheets contained a printed version of the log tables that were exactly the same as the tables in the back of our math books. This method avoided the need to check that we might have written some notes on the tables, since they were given out and collected for each test.
Our teacher also told us a story about the sheets that he claims really happened. In a class, years before, he had two students who were identical twins—very smart identical twins. They missed the first day of his class on logarithms.
After a while he gave his class their first exam on logarithms. As he was handing out the sheets he gave one to the first twin. The twin looked at the sheet and asked “what is this for?” Our teacher said they were the log tables they could use during the exam—they were copies of the tables from the math book. The twin handed the sheet back and said that he did not need it, since he and his brother had assumed they would need to know the tables. So they had memorized them.
The twins were smart, but they also had photographic memories. They assumed that part of learning logarithms was having to know the log tables. They were wrong: the whole point is that you do not have to remember the tables, and that is a main part of today’s discussion. They were impressive: I cannot imagine being able to remember even one page of the logarithm table.
The point of pre-computed tables is they can be used to speed up a computation. This idea is ancient, powerful, and probably not as widely used today as it could be. Perhaps the tremendous speed of our computers has made it less important to do pre-computation. Certainly logarithm tables are no longer needed—just use your calculator.
However, we do see tables used in a number of significant situations.
- Perhaps the best example is search—especially of the Web. All search engines have precomputed tables that allow the search of the countless pages of the Web in a fraction of a second. Okay there are only a finite number of pages, but the number is huge. It is claimed that the number of unique URL’s is above one trillion—as in 1,000,000,000,000. So fast search would be impossible without tables.
- Another important class of examples come from pervasive computing. Table lookup has been suggested as a way to save energy. The basic idea is to have the smart device pre-compute parts of a protocol, for example, when the device is being re-charged. Then the protocol will run faster when the device is running on batteries.
Napier’s logarithms reduce multiplication to additions and lookups. There are other ways to do this, to replace multiplication by “easier” operations. One dates from ancient times, perhaps thousands of years ago. Two clay tablets found at Senkerah on the Euphrates in 1854 show that the Babylonian’s seem to have used tables to reduce multiplication to squaring. The key equations are:
Both can be used to reduce multiplication to squaring.
What is the advantage of log tables over square tables? Let’s take a careful look at the cost of each of these methods.
The log method to multiply times is:
- Lookup and get and from the logarithm table.
- Add these to form .
- Then look up in another table and get the answer: .
This takes: three lookups, one add, and two tables.
The square method to multiply times is:
- Add to get .
- Look up the squares of in the table: let the values be respectively .
- Form , and then divide by two. This yields .
This takes: three lookups, three add’s, one divide by two, and only one table. I grouped addition and subtraction together, since they have about the same complexity.
Clearly, the logarithm method uses less total operations. But it does require two tables. From an asymptotic point of view both the above methods are linear time plus the three lookups.
Several questions come to mind. Why did the squaring method not get wider practical application? It uses such basic mathematics that it could have been used years before Napier’s work. Preparing a squaring table is not to difficult.
One answer is based on a property that Subrahmanyam Kalyanasundaram pointed out that distinguishes the log method from the squaring method. Here are his comments:
An inherent feature of the log based multiplication is that we take the log over the “normalized” number. Basically is multiplied as
I feel that this normalizing makes sure that we shift to the most significant digit and we spend our best efforts computing these digits. The log based method does it when we divide the number into characteristic and mantissa. Can the square method also do something like this?
Another question is what is the best that you can do with tables? I have never thought about this question. Given different costs on lookups and add’s what is the optimal method for reducing multiplication to table lookups? Of course multiplication is a very well studied problem. The current best is the beautiful algorithm of Martin Fürer that uses no tables and multiplies in time
Here is almost a constant, so his algorithm is very close to . Yet we still do not know if multiplication requires more than linear time.
A more general question is what is the power of tables in computing a general function. Given a function what is the table lookup cost? Probably we should restrict the tables to be unary: each table should only be able to compute where runs over a range of values.