Dead Reckoning

The first thing is a kind of psychological trick for long division, that makes the process seem easier without actually changing the algorithm. It's probably best explained by example. If you want to divide 1315863 by 571802, normally at each step you'd find the right multiple of 571802 and subtract it. However, the right multiple usually only depends on the first digits, so you can think of what you're doing as finding the right multiple of 57, subtracting it, and dealing with the rest as a correction. Here, 131 divided by 57 is 2, with remainder 17, so the dividend becomes 175863, but then you have to subtract an extra 2×1802 = 3604 from the other digits, leaving 172259. Then 172 divided by 57 is 3, with remainder 1, and so on.

There are lots of variations on that theme. If you want to divide by 570000 minus 1802 = 568198, the correction is the same, but you add it. If you don't like dividing by 57, you can divide by 6 and correct by 28198 … or correct by 3 and then by 1802. And, if the divisor is small, and ends in 1 or 9, you can divide by something and correct by 1, which amounts to feeding the quotient right back into the dividend! That's very nice, so if for example you want to compute 19/23, it's not unreasonable to start by multiplying both numbers by 3, just to make the divisor end in 9.

Probably that all sounds very complicated, but if you play with it on paper I'm sure you'll get the hang of it in no time.

The second thing is a series of divisibility tests used, and apparently invented, by Wim Klein. The details are different, but the idea is just the same as in the standard series! (If you haven't read that before, it probably won't make any sense unless you start with Primes.) Klein's series uses right-to-left reduction rules based on numbers of the form A×10^k ± 1 (see The Standard Series again), and here they are in a table, adapted from the book but with the rows in the same order. The columns tell the multiplier, the underlying number, and the list of tested primes, and the vertical groups tell whether the rules operate on three digits at a time (k = 3), or on two (k = 2).

−1	1001	7 11 13
+1	999	37
−2	2001	23 29
+4	3999	31 43
+4	399	19
+8	799	17 47
+16	1599	41
−2	201	67
−8	801	89
−9	901	53

The book doesn't say that the tests are meant to be a series, and in fact even the source given there (the book The Great Mental Calculators) doesn't come right out and say so, but it seems pretty clear that they are. For one thing, the lists of primes don't include primes that have already been tested. For example, the test based on 901 = 17×53 also covers 17. More importantly, the clever design of the series shows through: all but one of the multipliers are powers of two, so you can execute the entire series by just doubling, adding, and subtracting!

For example, if you want to investigate the number 724153, first you split off the three digits 153 and look at the numbers 724−153 and 724+153. Then you double and look at 724−306; then you double again and look at 724+612. After that, in theory you have to go back, split off the two digits 53, and double twice, but in practice you might take the last two digits of 612 and stick an appropriate digit in front. Either way, next you look at 7241+212, then you double and look at 7241+424, and so on.

Here are a few other points.

• You might think you should execute the two-digit tests in the order −2 +4 +8 −8 −9 +16 to avoid computing the same numbers twice. However, (a) doubling is easy, (b) you'll probably remember most of the numbers, and (c) it's better to test smaller primes first.
• To multiply by 9, you could shift and subtract (9 = 10 − 1), but since you already know the result of multiplying by 8, it's easier to take that number and add (9 = 8 + 1). The binary representation of 9 is 1001, by the way.
• Klein's series covers the first thirteen primes (plus two more) with ten tests, but the standard series covers the first fourteen primes with eight tests. I sure felt clever when I realized that! (Here I'm not counting 2, 3, and 5 as primes.) On the other hand, the standard series requires multiplying by 3 and by 7, which is harder, and uses tests for 41 and 47 that might be slower.

The second half of the book deals with floating-point operations: taking roots, particularly square roots; computing logarithms and exponentials; and even computing fairly accurate trigonometric functions—sines, cosines, and so on, via mental arithmetic! I'm not very good with floating-point numbers, so most of that material didn't sink in, but it was still interesting to see all the possibilities.

That brings me to the third thing, an improved algorithm for square roots. It's a little harder to remember than the basic algorithm I described in Square Roots, but it's a lot better—for the same effort I can obtain roughly twice as many digits. I won't try and explain it here, though; if you're curious, please see the additional material for chapter 3 at the book's web site.

The fourth and final thing has to do with logarithms. Back when I was learning the products up to 1000 (see Three Digits), it occurred to me that if I knew the logarithms of the relevant primes, it would be easy to find the logarithm of any number up to 1000; but then I realized that there were an awful lot of relevant primes, and that was the end of that … until once again I found the last piece of the puzzle in Dead Reckoning. It turns out that if you know the logarithms of just a few primes, you can find the logarithm of any number by first finding a nearby number n that has only those primes as factors, then applying a small correction given by the following formula.

log (n+a) = log n + 0.8686 a/(2n+a) + …

The series converges more rapidly than you might think—if the nearby number is adjacent (|a| = 1), then the next term, 0.8686 × (1/3) a³/(2n+a)³, will be zero for n ≥ 20, to five decimal places.

As an example, let's figure out the logarithm of 53. A good nearby number is 54; consulting the table of logarithms near the end of Powers of 2, we find that

log 54	= log (2 × 33)
	= log 2 + 3 log 3
	= 0.30103 + 3 × 0.47712
	= 1.73239.

To compute the correction, first we can optimize a little by writing 0.8686 as 86 × 0.0101, and saving the multiplication by 0.0101 for last. Then, dividing 86 by 54+53 = 107 and taking the result to three places gives 0.804; then adding shifted copies gives the correction 0.00812, which we subtract to obtain log 53 = 1.72427. That's correct except for the last digit, which should be 8.

It would be very useful to be able to compute exponentials too, but unfortunately going in that direction is more difficult. The book does give several methods, but none of them jumps out at me; maybe I'll settle on one later.