> urticator.net

  About This Site
> Domains

> Numbers

  Powers and Fractions
  Notes About Squares
  Decimal Expansions
  Repeat Length Again
  Number Maze
  Intrinsic Nature of Primes
  Other Topics
> Other Topics (2)

  Machine Language
  Pascal's Triangle
  Dead Reckoning
> Exponentials
  Multiplication in Base 10
  The Multiplication Table

  Exponentials, Continued
  The Algorithm
  Error Analysis


Two 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.

  • It's fairly simple. If you have some enthusiasm for mental calculation, it's certainly within reach; if not, well, it works with pencil and paper too.
  • It requires very little memorization. The only numbers you need to know are log 2 (.30103), log 3 (.47712), and the conversion factor 2.303.
  • It's quite accurate. In particular, it makes full use of the five decimal places provided by the logarithm method.

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 01.

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 01, 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 00.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 00.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.



  See Also

  Favorite Things

@ September (2006)