Home

> urticator.net
Search

> Domains
Glue
Stories

Computers
Driving
Games
Humor
Law
Math
> Numbers
Science

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

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

Exponentials, Continued
 > The Algorithm
Error Analysis

## The Algorithm

prev

Here's the complete McIntosh-Doerfler algorithm for calculating exponentials. Given a number t known to five decimal places, do the following to calculate 10t.

1. Throw away the integer part of the number and think of the decimal part as being modulo 1, i.e., as a five-digit odometer that can wrap around in either direction. For example,

.40000 + .60206 = .00206
.40000 - .95424 = .44576.

For mental calculation, it's probably best to organize the digits as a group of three plus a group of two. If the original number was negative, take the second complement of the decimal part, so that for example the number -.95424 becomes .04576.

2. Add or subtract up to two copies of log 3 = .47712 to make the number close to a multiple of 0.1. You can determine the right number of copies by looking at the second and third digits of the number … adding log 3 is like subtracting 23 in those digits, and vice versa.
3. Add or subtract up to five copies of log 2 = .30103 to make the number close to zero. You can determine the right number of copies by looking at the (rounded) first digit and seeing what multiple of 3 will cancel it out. If the number is .39700, for example, then the rounded first digit is 4, which can be canceled by adding 2×3 = 6 … therefore the right move is to add two copies of log 2.
4. Call the current number x, and evaluate the formula 1 + 2.303x + (2.303x)2/2, as follows.

1. If the number is close to zero on the .99999 side, take the second complement and remember that at the end you'll need to subtract instead of add. (That's the last of the mod 1 arithmetic, by the way.)
2. Multiply by 2.303. That's easier than it sounds: just add the number to itself twice, then add up shifted copies of those numbers. Round the result back to five places and remember it for later.
3. Square the number. That's easier than it sounds, too, because the result is almost completely determined by the first three digits. If, e.g., the number is .01357, then from 132 = 169 and 142 = 196 it follows that the result lies between .000169 and .000196. Then, since 13.57 is about halfway between 13 and 14, you can guess (correctly) that the result is about .00018. Here it's very helpful to know the squares!
4. Divide by 2 and round back to five places.
5. Take that number and add it to (or subtract it from) the number you remembered earlier. Then take the result and add it to (or subtract it from) the number 1. You should subtract in both cases if you had to take the second complement in step a.
5. Undo whatever you did in steps 2 and 3. If you subtracted log 3, multiply by 3; if you added 4 log 2, divide by 24 = 16. If you have to divide, do it last, and be sure to keep a few extra digits … you may need them.
6. Shift the decimal point to bring the result into the correct range. The range is determined by the integer part that you threw away in step 1. (Due to the mod 1 arithmetic, the integer part does not tell you how many places to shift, it just directly tells you the correct range.)

And then you're done!

After all that, I'm sure you'll want to see some examples, so here are three.

 .20000 3.14159 - .33550 1. throw .20000 .14159 .66450 2. log 3 + .00000 + .95424 - .95424 .20000 .09583 .71026 3. log 2 - .20412 + .90309 + .30103 .99588 .99892 .01129 4. a. negate .00412 .00108 .01129 b. 2.303 .00949 .00249 .02600 c. square .00009 .00001 .00068 d. divide .00005 .00000 .00034 e. add up .99056 .99751 1.02634 5. undo × 16 × 1/72 × 9/2 15.84896 .0138543 4.61853 6. shift 1.58490 1385.43 0.461853 actual 1.58489 1385.45 0.461849

(Just for the record, although 103.14159 is 1385.45, 10pi is actually 1385.46.)

In that last example, the result is off by four units in the last decimal place. That may not seem very good for an algorithm that's supposed to be quite accurate, but it's the best we can do. I can explain why, but first I have to back up a little.

Actually, before I do that, let me point out two things.

• If you don't need all five decimal places, you can use three places instead, and evaluate the simpler formula 1 + 2.3x. That variant is extremely fast, and quite accurate too, as far as it goes.
• If log 2 weren't such an unusually round number, the algorithm wouldn't be executable. A non-round log 2 would make step 2 too complicated, and a round log p for some other p would make the numbers in step 5 too large. So, there's another special property of base 10 for you, to go with the fact that it's among the best for divisibility testing.

next