About This Site
Powers and Fractions
Notes About Squares
Repeat Length Again
Intrinsic Nature of Primes
> Other Topics (2)
The Multiplication Table
ExponentialsTwo months ago, at the end of my essay about the book Dead Reckoning, I picked one of the book's methods for calculating logarithms as my favorite, and described it, but I didn't pick a corresponding method for calculating exponentials, because none of the ones in the book had appealed to me. Since then, I've been discussing the problem with the author; and now I'm pleased to present the result of that discussion, the McIntosh-Doerfler algorithm. Among other things, it has the following properties.
If you want to see the whole algorithm right away, feel free to peek … it's down in the subessay The Algorithm. However, I think it will make more sense if first I tell you a little about where it came from.
The general idea is the same as in the book's methods.
Given a number that you want to exponentiate, remove pieces with known exponentials until the remainder is within range of a formula, then run the formula and multiply the result by the pieces.
What pieces? And what formula? Well, let's start with the pieces.
The first piece is easy. The number 1 has the known exponential 10, so we can remove the integer part of the number we want to exponentiate and then multiply by 10 a few times at the end … i.e., shift the decimal point. That leaves the remainder in the range 0–1.
The second piece is pretty easy, too. The logarithm of 2 is a nice round number, roughly 0.3, and of course it has the known exponential 2. So, given a number in the range 0–1, we can remove up to three copies of log 2 and then multiply by 2 that many times at the end. That leaves the remainder in the range 0–0.3.
Actually, if we're willing to add pieces as well as remove them, we can do even better! If we add 3 log 2 and subtract 1, that decreases the remainder by roughly 0.1; doing that at most twice leaves the remainder in the range 0–0.1.
Or, instead of removing copies of log 2 in one step and then adding them back again in the next, we can just look at the first decimal place of the original number and all at once figure out how many copies of log 2 to add or remove (and what power of 2 to multiply by at the end). If the number is close to 0.7, for example, well, obviously the right thing to do is to add one copy of log 2 and then multiply by 1/2 at the end. (Don't worry about the power of 10, we'll deal with that later.)
Here's a table that I hope will make everything clear.
The grid shows the powers of 2 from 2-6 to 26 arranged by first decimal place (approximate first decimal place, of the logarithm). The first column on the right shows the best power of 2 for each case; the second shows the numerical value of the power, with the decimal point shifted to bring the logarithm into the correct range.
You do not need to memorize this table! The second column is not useful here at all; I only included it because I like how the numbers have evenly spaced logarithms (and because it relates to the discussion of first digits in Powers of 2). The first column is useful, but it's probably just as easy to figure out on the fly as it is to memorize. All you really need to know is which power of 2 is which.
I said above that the table shows the best powers of 2, but actually there's one case where it's not entirely clear which power is best. If we have a number close to 0.8, we can either subtract 6 log 2 ~ 1.8 or add 4 log 2 ~ 1.2 … and then at the end either multiply by 64 or multiply by 1/16, i.e., divide by 16. Normally I'd rather multiply than divide, but here the divisor is pretty small, so it's hard to say. The reason I finally settled on 1/16 is that it's easy for me to divide by 16 since I know the multiples of 16 from hexadecimal.
@ September (2006)