= Napier's Constant =

I had always been bothered by the origin story of the constant \(e\).
Explaining the constant \(\pi\) is no problem, as even a child can understand
the ratio of a circle's circumference to its radius. In contrast, I imagine I'd
have a tough time explaining the base of the natural logarithm to less
mathematically inclined adults, let alone children.

We can express \(e\) as the sum of the reciprocal of the factorials:

\[
e = 1 + \frac{1}{1}
+ \frac{1}{1\cdot 2}
+ \frac{1}{1\cdot 2\cdot 3}
+ ...
\]

And \(\pi\) has a similar expansion:

\[
\frac{\pi}{2} = 1 + \frac{1}{3}
+ \frac{1\cdot 2}{3\cdot 5}
+ \frac{1\cdot 2\cdot 3}{3\cdot 5\cdot 7}
+ ...
\]

Both series converge quickly enough for cute party tricks:

seed = (1 :: Double, 1 :: Double)
sum $ take 20 $ snd <$> iterate (\(n,x) -> (n+1, x/n)) seed
(2*) $ sum $ take 20 $ snd <$> iterate (\(n,x) -> (n+1, x*n/(2*n+1))) seed

You would think a constant with a simple elegant formula would have an easy
explanation. This is indeed true for \(\pi\). Might this also be true for
\(e\)? Did I somehow miss an easy explanation all these years?

To answer this question, I read _e: The Story of a Number_ by Eli Maor, which
comprises of seemingly unrelated episodes, each culminating in a big reveal
where we learn \(e\) was behind it all along. For example:

  1. John Napier, the 8th Laird of Merchiston, "doubled the life of the
  astronomer" by publishing a table of numbers capable of miracles such
  as transforming multiplication into addition, division into subtraction, and
  taking square roots into halving.
  2. For the same rate, interest compounded daily grows faster than interest compounded monthly. What do we get when it is compounded more frequently? What if it were compounded continuously?
  3. Even before calculus, mathematicians managed to measure the area under curves of the form \(y = x^n\) where \(n\) is an integer. The toughest case is \(n = -1\), the hyperbola. Why? And what's the answer?
  4. Calculus gave mathematicians a brand new toy to play with, who promptly
  tried it on curves like \(y = 2^x\). They found its derivative was
  \(y' = m 2^x\) where \(m\) is the slope of the curve at \(x = 0\).
  Does this mean for some \(r\), the slope of \(y = r^x\) at \(x = 0\) is
  exactly 1, yielding a function that is its own derivative?

The fourth puzzle was how I first learned about \(e\), from a calculus textbook
whose title I forget. I learned of the other 3 puzzles soon after, so I hadn't
missed out after all.

In other words, the bad news is \(e\) is not as easy as \(\pi\). But the good
news is we get to watch a gripping drama. When young, we enjoy simple stories,
but as we age, we are drawn to mysterious and intricate plots with interwoven
threads, often presented nonlinearly.

Maor tells a good tale, and his book is full of tasty historical tidbits, but
he botches the opening scene. He distorts Napier's contributions. Maor's
statement in footnote 13 of the first chapter, "The often-made statement that
Napier discovered [\(1/e\)] (or even \(e\) itself) is erroneous", is itself
erroneous.

Instead of a documentary, we're left with a yarn based on a true story. We set
the record straight, with the help of
https://inria.hal.science/inria-00543934/document[Denis Roegel, _Napier's ideal
construction of the logarithms_].

== An unjust twenty-year sentence ==

Maor claims Napier built his wonderful canon of logarithms by choosing
the following base, or common ratio:

\[
1 - 10^7 = 0.9999999
\]

Maor suggests Napier then computed successive powers until he reached 0.5. This
cannot be! It already takes over a million iterations to reach 0.9:

length $ takeWhile (> 0.9) $ iterate (0.9999999*) 1

Indeed, Maor corrects himself when he lists the geometric progressions that
Napier actually computed. They come in 4 flavours:

  1. Napier did in fact compute successive powers of \(0.9999999\), but only one hundred of them: \(1, 0.9999999, ..., 0.9999999^{100}\).

  2. He computed successive powers of a five 9s version of the ratio: \(1, 0.99999, ..., 0.99999^{20}\).

  3. He computed successive powers of a two 9s version of the ratio: \(1, 0.99, ..., 0.99^{68}\).

  4. For every \(c\) in the previous step, he computed \(c, 0.9995 c, ..., 0.9995^{20} c\).

Then Maor states: "...he set himself to the task of finding, by tedious
repeated subtraction, the successive terms of his progression...Napier carried
it through, spending twenty years of his life (1594-1614) to complete the job."

Really? We'll examine the details later, but briefly, the first three sequences
only require shifts and subtractions, while the sequences of the last step
require only a little more work in the form of one extra halving operation.

The total bill comes to 1568 shifts and subtractions, and 1380 halvings.

100 + 20 + 68 + 69*20
69*20

Throughout my school years, my teachers frequently assigned around 10 homework
exercises that were due the next day: exercises comparable in technical
difficulty to subtraction and halving. (Some exercises may have revolved
around more advanced concepts like integration, but the calculation itself
followed simple rules.) In other words, schoolchildren could complete these
tables within half a year! There is no way Napier needed twenty. Maor's
sentence must be false.

And what could Napier possibly have done with these sequences? All numbers of
the first two sequences are close to 1, and there are only about 120 different
numbers anyway. The numbers of the third sequence are the seeds for the last
set of sequences, which are numerous and range from 0.5 to 1. The latter must
be where Napier looked up numbers to find their logarithms. This should raise
alarm bells. Two different sets of alarm bells, for we have exposed two gaping
plot holes.

Firstly, if Maor's explanation is to be believed, it appears the ratio Napier
used was not 0.9999999 but rather 0.9995.

Secondly, and more worryingly, what is the point of the first three sequences?
If Napier chose the ratio 0.9995, then all he had to do was compute:

\[
1, 0.9995, ..., 0.9995^{1386} = 0.49998...
\]

namely, one sequence of 1387 numbers instead of 69 sequences with 21 numbers
each. There must be more to the story.

== Waiting for Zeno ==

To truly understand Napier, we should walk a mile in his shoes. We do so almost
literally, because Napier explained logarithms by imagining a point traveling a
certain distance in a straight line that periodically marked off distances
following a geometric progression.

It seems Zeno was his cobbler because allowing artistic license, the trek
Napier envisioned began at noon at one mile per hour, but slowed down
exponentially as the destination neared. Every hour on the hour, the remaining
distance is \(r\) times the remaining distance one hour ago, for some constant
\(r < 1\). We'll never arrive, despite getting arbitrarily close.

Let's take advantage of modern mathematical notation to analyze this
journey. For a natural \(n\), let \(f(n)\) be the remaining distance in miles
after \(n\) hours. Thus:

\[
f(0) = 1 ,
f(n + 1) = r f(n)
\]

By induction:

\[ f(n) = r^n \]

Let's extend this equation to all reals \(t\):

\[ f(t) = r^t \]

Initially, we head towards our destination at one mile per hour:

\[ f'(0) = -1 \]

Haven't we met somewhere before? This is the fourth puzzle listed above,
namely, how I first learned \(e\) decades ago from my calculus textbook, except
with a sign flipped. We must have \(r = 1/e\).

Napier defined the logarithm to be the inverse of \(f\): given a remaining
distance in miles, how many hours have elapsed? In other words, Napier
invented logarithms to the base \(1/e\).

Maor alleges: "Napier unknowingly came within a hair's breadth of discovering"
\(e\).

Let's take stock. Napier defined the same function (up to sign) that my
calculus textbook defined to introduce \(e\), a function that Maor himself
discusses in Chapter 10. For memory, my textbook only argued \(e\) was between
2 and 3, and stated several digits without proof. In contrast, Napier figured
out quite a few digits of quite a few numbers, and explained how he did it. In
his 1614 table, the entry for 21 degrees and 35 minutes includes:

3678541 1000685

This means Napier is claiming \(\ln 0.3678541 = -1.000685\), which is
startlingly accurate: only the last digit is wrong. We can interpret this as:

\[
1/e \approx 0.3678541
\]

which is correct to 4 decimal places (\(1/e = 0.3678944...\)).

Napier even saw that the remaining distance (in miles) is also the current
speed (in miles per hour), a fact his work hinged on. This is obvious today
because we all know the derivative of \(e^t\) is itself, but Napier had no
access to calculus. In fact, in his day, non-integer exponents were poorly
understood.

Is it fair, then, to say Napier only came close to discovering \(e\)?

Confusingly, in Appendix 1, Maor mentions Napier's moving point, and adds:
"Napier's logarithms are actually logarithms to the base \(1/e\)",
contradicting his Chapter 1 claim that after rescaling, the base is
+\( (1 - 1/10^7)^{10^7} \)+.

The retconning of Appendix 1 somewhat redeems Chapter 1, but still fails to
explain why Napier bothered computing the first three sequences. It also
introduces another gun that Chekhov would condemn. If Napier's goal was to
compute successive powers of 0.9999999, why did he define this moving point?

We'll soon reveal the terrifying reasons, but first we atone for some
storytelling transgressions.

== A Pointless Exercise ==

We've swept a couple of details under the rug. My guess is Napier wanted a
function that takes a length and returns a length, so he wrote of a second
point that always moved at 1 mile per hour, and defined the logarithm using the
distance traveled by this second point. We view this as an unnecessary layer of
indirection.

More troublesome for us was that Napier lived through a sort of numerical
hyperinflation. A cutting-edge researcher, Napier was at ease with the latest
inventions such as the decimal point: indeed, Napier helped popularize this
handy bit of notation. But in 1614, for the sake of his intended audience, he
chose a https://en.wikipedia.org/wiki/Sinus_totus[_sinus totus_] of \(10^7\),
pumping up his numbers by 7 zeroes (markedly fewer than the number of zeroes
tacked onto certain unfortunate currencies throughout history).

Instead of "0.1234567", readers would see "1234567", with no trace of those
newfangled decimal points. They'd have to rescale now and then, but this was a
prevailing custom anyway.

In detail, the _Naperian logarithm_ is given by:

\[
\newcommand{\NapLog}{\mathop{\rm NapLog}\nolimits}
\NapLog x = - 10^7 \ln (x / 10^7)
\]

We do our best to dodge this security-blanket scaling factor, though if we
replace "mile" with "sinus totus" then some of our statements are equivalent to
Napier's. But on occasion we really are talking about numbers ten million times
smaller than Napier's.

One particularly tiresome mismatch is that \(\NapLog 10^7 = 0\). Everybody
loves that:

\[
\log a b = \log a + \log b
\]

but with Naperian logarithms, we get:

\[
\NapLog a b = \NapLog a + \NapLog b - \NapLog 1
\]

Naturally, Napier's fans soon clamoured for an upgraded logarithm that returns
0 when given 1.

== Shift Work ==

Let's look closer at the calculations Maor describes, which supposedly took 20
years. We call them auxiliary tables, but fear not: we'll divulge their true
purpose soon enough!

When multiplying a number \(x\) by a number of the form \(1 - 10^{-n}\),
Napier shifted \(x\) right by \(n\) places, simply truncating digits to fit
into the desired precision.

Napier computed his first sequence with 14 decimal places of precision.
The common ratio is \(1 - 10^{-7}\).

aux1 = take 101 $ iterate (\n -> n  - n `div` 10^7) (10^14)
take 5 aux1
last aux1

We stick to integer arithmetic to make it clear where the truncation occurs.
(So now we're the ones avoiding decimal points with hyperinflation!)

Our digits agree with Napier's:

image::https://upload.wikimedia.org/wikipedia/commons/7/7f/Napier%27s_first_table.agr.png[auxiliary table 1, 150]

Napier used 13 decimal places for the second sequence, whose common ratio is
\(1 - 10^{-5}\).

aux2 = take 51 $ iterate (\n -> n  - n `div` 10^5) (10^13)
take 5 aux2
last aux2

This time we disagree with Napier:

image::https://upload.wikimedia.org/wikipedia/commons/4/49/Napier%27s_second_table.agr.png[auxiliary table 2, 150]

The first 5 numbers are identical, but the last digits of the last number
should be 4826, not 2927. Napier must have slipped up at least once along the
way. We'll soon witness this tiny bug spread and grow as Napier computed more
of his logarithms.

For the heads of the 69 sequences, Napier used 11 decimal places. The common
ratio is 0.99:

aux3heads = take 69 $ iterate (\n -> n - n `div` 100) (10^11)

The rest of each of these sequences have the common ratio of 0.9995, which some
sources say were computed by shifting, then halving, then subtraction.
I assume Napier also truncated digits for these shifts, but what about the
halving? Did he truncate? Or did he round? Did he actually use higher precision
then truncate later? Could he have halved before shifting?

Whatever he did, I was unable to reproduce it exactly. We choose to shift,
truncate, halve, round, then subtract:

aux3 = map (take 21 . iterate (\n -> n - (n `div` 1000 + 1) `div` 2)) aux3heads
aux3sample = (take 3 aux3 ++ [last aux3])
(\ns -> (take 5 ns, last ns)) <$> aux3sample

This gets us pretty close:

image::https://upload.wikimedia.org/wikipedia/commons/4/4f/Napier%27s_third_table.agr.png[auxiliary table 3, 500]

Luckily, the discrepancies only seem to affect the last digit, and at any rate
they have far less impact than Napier's mistake in the second auxiliary table.

== The War on Error ==

Napier must have realized the accumulated truncation errors might be as high as
the number of steps taken, which may be why he chose 69 sequences with 21 items
each rather than a giant sequence needing over 1000 truncations. Within each of
the 69 sequences, an entry has at most 20 accumulated truncation errors.

The start of the 69th sequence, 50488588900, is off by at most 63; less than 68
because it comes from a sequence with a ratio of 0.99 computed with 11 decimal
places (so the first 5 shifts and subtractions are exact). With arbitrary
precision arithmetic at our fingertips, we find the last 3 digits should be
878, not 900:

take 11 $ show $ 99^68

Maor suggests that Napier took the index of an entry to be its logarithm.
Not so. Napier only computed the 69 sequences to establish geometric
progressions with reasonable coverage of the interval [0.5..1]. Then the real
fun begins: Napier proceeds to compute the logarithms of each member of each
progression.

Napier of course computed Naperian logarithms, but we'll talk of natural
logarithms instead, which is mostly harmless. One might object that we need
\(\ln 10\) to convert one kind to the other. However, this constant is unneeded
when computing Naperian logarithms alone, and once done, we can figure out
\(\ln 10\) from the tables.

But why not just use an entry's index? Because Napier cared deeply about
accuracy (aside from the last few digits lost to truncation errors). He knew no
power of 0.9995 is exactly 0.99, so integer indices won't cut it.

There's more. For the sake of argument, let's say Napier somehow possessed
accurate approximations to some logarithms, for example:

\[ 0.9995^{1349} = 0.5093251... \]

\[ 0.9995^{1350} = 0.5090704... \]

Then how do we solve the following?

\[ 0.9995^x = 0.5092 \]

The answer lies between 1349 and 1350, but where exactly? Should we linearly
interpolate and hope for the best?

I speculate Napier may have toyed with ideas like this. But in the end, Napier
did the right thing: define a sort of continuous ideal geometric progression,
namely the exponential curve, and exploit its properties to produce incredibly
accurate approximations.

== I got 0.99 problems ==

The properties of logarithms imply a shortcut. If Napier could look up the
values of \(\ln 0.99\) and \(\ln 0.9995\) then he could just add and subtract
to find the logarithms of all \(69 \times 21\) numbers in his coverage table,
the third auxiliary table. Unfortunately, his goal was to create from scratch a
lookup table that would provide such answers in the first place! We have a
chicken-and-egg problem.

It is only at this point we learn why Napier bothered with the first two
sequences. They were for bootstrapping:

  1. Napier found a good approximation for \(\ln 0.9999999\).

  2. Since \(0.9999999^{100} \approx 0.99999\), their logarithms are also close.
  Napier bounded the difference between their logarithms to approximate
  \(\ln 0.99999\).

  3. Since \(0.99999^{20} \approx 0.9995\), their logarithms are also close,
  but this time, instead of bounding their difference to derive an
  approximation, he went above and beyond. He approximated the logarithm of
  their ratio using the highly accurate approximation from step 1, which
  in turn led to an approximation for \(\ln 0.9995\).

  4. Since \(0.9995^{20} \approx 0.99\), their logarithms are also close.
  Napier found an approximation for \(\ln 0.99\) in a similar manner as the
  previous step.

  5. Profit! Napier approximated the logarithms of every number in his
  lookup table via repeated additions of the approximations for \(\ln 0.99\)
  and \(\ln 0.9995\).

Napier's moving point makes short work of step 1. When there are 0.9999999
miles left to go, our current speed is also 0.9999999 miles per hour. Our pace
was only faster in the past, which means we took less than \( (1 - 0.9999999) /
0.9999999 \) hours to reach our current position.

Dually, since we set off at 1 mile per hour, and since our pace has only
slowed, more than \( 1 - 0.9999999 \) hours have elapsed. In other words:

\[ 1 - 0.9999999 < -\ln 0.9999999 < \frac{1 - 0.9999999}{0.9999999} \]

Napier approximated the denominator of the right-hand side with the first few
terms of the geometric series:

\[ \frac{1}{1 - 10^{-7}} = 1 + 10^{-7} + 10^{-14} + ... \]

and averaged the resulting bounds to get:

\[ \ln 0.9999999 \approx -1.00000005 \times 10^{-7} \]

This https://www.google.com/search?q=ln+0.9999999[agrees with Google], and any
program limited to IEEE 754 double-precision floats. We need more precision to
detect the error:

\[ \ln 0.9999999 = -1.00000005000000333333358... \times 10^{-7} \]

Napier took the first 100 multiples of -1.00000005 to be the logarithms of the
(approximiate) powers of 0.9999999. In particular, his first sequence ended
with:

\[ 0.9999999^{100} \approx 0.9999900000495 \]

thus:

\[ \ln 0.9999900000495 \approx -1.00000005 \times 10^{-5} \]

In general we have:

\[ x < -\ln (1 - x) < \frac{x}{1 - x} \]

which may look banal to modern eyes, because of the Taylor expansion:

\[ -\ln (1 - x) = x + \frac{x^2}{2} + \frac{x^3}{3} + ... \]

So we stress Napier derived these bounds without calculus, for a brand new
function he invented. Napier provided no explanation for choosing the average,
but we can see it's essentially the second-order Taylor approximation.

== What's the difference? ==

If we replace \(1 - x\) with \(a/b\) and rearrange, we obtain:

\[ \frac{a - b}{b} < \ln b - \ln a < \frac{a - b}{a} \]

Napier used this formula to approximate a logarithm if he already knew a
nearby logarithm. For step 2, set:

\[ a = 0.9999900000495, b = 0.99999 \]

The bounds on either side are approximately:

\[ a - b = -4.95 \times 10^{11} \]

so he took the lower and upper bound to be the same.

Napier performed a sort of
https://en.wikipedia.org/wiki/Interval_arithmetic[interval arithmetic], that
is, he postponed the averaging of bounds as late as possible. He added lower
bounds together and upper bounds together, and only when he wanted to record a
single number would he compute their average. (In this particular case, there
is no benefit since one set of bounds are identical, but in general, working
with bounds gives more accurate answers.)

He found:

\[ \ln 0.99999 \approx \ln 0.9999900000495 - 4.95 \times 10^{11}
\approx -1.000005 \times 10{^-5}  \]

Again, this agrees with double-precision float arithmetic, and we need higher
precision to spot the error.

Then we have the beginnings of a tragedy. Napier's erroneous last few digits in
the last entry of the second auxiliary table, 2927 instead of 4826, means the
following approximation is worse than it should have been:

\[
\ln 0.99999^{50} \approx 50 \times \ln 0.9995001222927 \approx -5.000025 \times 10^{-4}
\]

The bug propagates in step 3, where Napier computed:

\[
\frac{0.9995}{0.9995001222927} \approx 0.9999987764614
\]

Setting:

\[ a = 0.9999987764614, b = 0.9999999 \]

in the above leads to:

\[ \ln 0.9999987764614 \approx -1.2235387 \times 10^{-7} \]

then interval arithmetic and averaging yields:

\[ \ln 0.9995 \approx \ln 0.9999987764614
- \ln 0.9995001222927 \approx 5.0012485387 \times 10^{-4}
\]

This approximation is smaller than it should have been because of Napier's bug.

Step 4 followed a similar procedure to arrive at:

\[ \ln 0.99 \approx 0.1005033210291 \]

which again is lower than it should have been, because of other approximations
that were infected by the bug.

Step 5 completes the tragedy. The error virulently spread and magnified
throughout the third \(69 \times 21\) table, accumulating with every addition.

While the errors were tolerably small in practice, it is a shame that Napier
worked so hard to boost accuracy but was sabotaged by a trivial mistake in
elementary arithmetic.

We now see why Napier computed the first two sequences: they were to bootstrap
the approximations. We also see why he invented the exponential function: the
indices alone are far too inaccurate, and he needed a way to approximate
logarithms from known nearby logarithms.

However, we have not quite fired all the guns of Chekhov. How long would the
above taken? Almost all of the logarithms are derived from others via addition
or multiplication by a small constant. Only 4 of the logarithms require
interval arithmetic. The divisions in the bounds can be approximated by
multiplications with a truncated geometric series because the denominators are
close to 1.

Overall, while it is certainly a mountain of work, it's not an order of
magnitude more than the initial shifts, subtractions, and halvings.
It would not have taken Napier twenty years.

What could have eaten so much time? Surely Napier spent hours on failed
experiments and inferior approaches, and on finding miraculous coincidences
such as \(0.9999999^{100} \approx 0.99999\), inventing the exponential function
and interval arithmetic, and so on. But this kind of work is not soul-crushing
drudgery.

The bulk of the two decades must have been spent elsewhere.

== Take care of the minutes... ==

Where did the time go? Where was the soul-crushing drudgery?

We dropped a hint when we mentioned 21 degrees and 35 minutes. There are 60
minutes in a degree, and Napier's tables handled every degree between 0 and 90.
For each of these 5400 degrees and minutes, Napier looked up its sine value
from a reference, then computed the logarithm. For values close to 1 he could
use the first-order Taylor approximation which is almost no work, but for most
sine values he had to find the closest value in the third auxiliary table, then
approximate the logarithm via the above formula for the bounds.

image::napier-21-recto.jpg[page showing 21 degrees 35 minutes]

These involved divisions where geometric series approximations are of no help
because the divisor is too far from 1. Some sine values required even more
work, as Napier had to first apply trigonometric identities or logarithm laws
to bring numbers in range of the third auxiliary table.

Napier also had to perform 2700 subtractions to compute the logarithms of
tangent values. Though trivial compared to divisions, this alone is about
double the number of subtractions Napier needed for the auxiliary tables.