Case Study 1 — Certifying a Logarithm: How a Math Library Computes $\ln 2$

Field: Numerical analysis / scientific computing Calculus used: Alternating series test and its error bound (§22.7), the ratio test and convergence rate (§22.5), absolute convergence (§22.8)

The problem nobody sees

Every time a program evaluates log(x), something has to compute that logarithm from scratch — there is no lookup table with infinitely many entries. The standard math library must produce, say, $\ln 2 = 0.6931471805599453\ldots$ to the full $53$ bits of a double-precision float, and it must do so provably: a library that is "usually accurate" is a library nobody can trust. The question this case study answers is the one a library author actually faces: given an infinite series for $\ln 2$, exactly how many terms must I add to guarantee the answer is correct to the last bit — and which series should I even use? Both halves of that question are convergence-test questions, and Chapter 22 answers them completely.

The honest but hopeless series

The most famous series for $\ln 2$ falls out of the alternating harmonic series from §22.7: $$\ln 2 = \sum_{n=1}^\infty \frac{(-1)^{n+1}}{n} = 1 - \frac12 + \frac13 - \frac14 + \cdots$$ This is an alternating series with $b_n = 1/n$ decreasing to $0$, so by Leibniz's test it converges, and — crucially for a library author — it comes with the certified error bound of §22.7: $$\left|\ln 2 - S_N\right| \le b_{N+1} = \frac{1}{N+1}.$$ That bound is a gift: it is a single computable number that proves how close we are, with no appeal to the true value. So let us use it. Double precision carries about $16$ significant decimal digits, meaning we want an error below roughly $10^{-16}$. The bound demands $$\frac{1}{N+1} \le 10^{-16} \quad\Longrightarrow\quad N \ge 10^{16} - 1.$$ Ten quadrillion terms. On a machine adding a billion terms per second, that is about four months of computation to evaluate a single logarithm — and along the way, the rounding errors of $10^{16}$ floating-point additions would themselves swamp the answer. The series is mathematically impeccable and practically useless. The error bound did not fail us; it told us the brutal truth, which is exactly what a certified bound is for.

The deeper diagnosis comes from the rate. The alternating harmonic series is only conditionally convergent (§22.8): its absolute version $\sum 1/n$ diverges, so all of its convergence is borrowed from sign cancellation, and the leftover error decays only like $1/N$ — algebraically, agonizingly slowly. To win, we need a series whose error decays geometrically, and §22.5 tells us where to look: terms with a ratio bounded below $1$.

The series a real library uses

Recall the power series for the natural logarithm (developed fully in Chapter 23): $$-\ln(1-x) = \sum_{k=1}^\infty \frac{x^{k}}{k}, \qquad |x| < 1.$$ Setting $x = \tfrac12$ gives $-\ln\!\left(\tfrac12\right) = \ln 2$, so $$\boxed{\;\ln 2 = \sum_{k=1}^\infty \frac{1}{k\,2^{k}} = \frac12 + \frac{1}{8} + \frac{1}{24} + \frac{1}{64} + \cdots\;}$$ This is the same logarithm, but a completely different series — and a completely different convergence story. Its terms $a_k = 1/(k2^k)$ are positive, so we test it as a positive series. Apply the ratio test (§22.5): $$\frac{a_{k+1}}{a_k} = \frac{1/((k+1)2^{k+1})}{1/(k2^{k})} = \frac{k}{2(k+1)} \longrightarrow \frac12 = \rho < 1.$$ So the series converges absolutely, and $\rho = \tfrac12$ tells us it behaves geometrically with ratio about one-half — it loses roughly one bit of error per term, the fast regime §22.5's Computational Note promised. Because it is absolutely convergent, we may also rearrange or regroup terms freely (§22.8) without changing the sum, which gives the implementer latitude to reorder additions for numerical stability.

The certified term count

Now we make "geometric" quantitative, because a library cannot ship "roughly." Truncate at $N$ terms and bound the tail directly: $$\ln 2 - S_N = \sum_{k=N+1}^\infty \frac{1}{k\,2^{k}}.$$ For every $k \ge N+1$ we have $\tfrac1k \le \tfrac{1}{N+1}$, so $$0 < \ln 2 - S_N \le \frac{1}{N+1}\sum_{k=N+1}^\infty \frac{1}{2^{k}} = \frac{1}{N+1}\cdot\frac{1}{2^{N}}.$$ (The inner geometric tail sums to $2^{-N}$, by the Chapter 21 formula.) This is a clean, computable certificate — and notice it shrinks like $2^{-N}$, not $1/N$. To hit double precision, solve $$\frac{1}{(N+1)\,2^{N}} \le 10^{-16}.$$ At $N = 50$, $2^{50}\approx 1.13\times10^{15}$ and $(N+1)2^N \approx 5.7\times10^{16}$, giving a bound near $1.8\times10^{-17}$ — already below $10^{-16}$. So about $50$ terms suffice to compute $\ln 2$ to the last bit of a double. Set that against the $10^{16}$ terms the alternating-harmonic series demanded: the geometric series is faster by fourteen orders of magnitude, for the exact same number. That gulf is precisely the difference between $\rho = 1$ (conditional, $1/N$ decay) and $\rho = \tfrac12$ (absolute, geometric decay) — the chapter's central rate lesson, cashed out in microseconds of real runtime.

Putting it together in code

# Two series for the SAME number, ln 2 = 0.69314718055994531...
# (a) alternating harmonic: error ~ 1/N      (hopeless)
# (b) -ln(1-x) at x=1/2:     error ~ 1/((N+1) 2^N)  (what libraries use)
def ln2_alt(N):                 # conditional, slow
    return sum((-1)**(n+1) / n for n in range(1, N + 1))

def ln2_geom(N):                # absolute, geometric
    return sum(1.0 / (k * 2**k) for k in range(1, N + 1))

# Hand-computed outputs (do NOT need to run this):
# ln2_alt(50)  -> 0.683347...   actual error ~ 9.9e-3   (bound 1/51 ~ 1.96e-2)
# ln2_geom(50) -> 0.6931471805599453   error < 1.8e-17  (full double precision)

After $50$ terms the alternating series is still wrong in the second decimal place, exactly as its $1/N$ bound forecasts, while the geometric series has pinned every bit a double can hold. The two functions compute the same constant; convergence-test analysis is the only thing that tells you which one is shippable.

Why this is the real lesson of Chapter 22

A student version of this chapter ends at "does it converge?" A practitioner's version begins there. Both series for $\ln 2$ converge; convergence alone is worthless to the library author. What the tests also deliver is the rate (via $\rho$ in the ratio test) and a certificate (via the alternating bound, or here the geometric tail bound), and those are what turn a true statement into a usable algorithm. This is why §22.5's Computational Note insisted that a series with $\rho = 0.5$ and one with $\rho = 0.99$ are worlds apart even though both "converge," and why absolute convergence (§22.8) matters in practice: it is the rate, and the order-independence, that the engineer is buying.

Discussion questions

  1. The alternating-harmonic bound $1/(N+1)$ and the geometric bound $1/((N+1)2^N)$ both came from the first omitted structure of the tail. Identify which convergence test produced each bound, and explain why one decays algebraically and the other geometrically.
  2. We used $x = 1/2$. The series $-\ln(1-x)=\sum x^k/k$ also represents $\ln 2$ at $x=1/2$ only — but $\ln 3$ would need $x=2/3$, where $\rho = 2/3$. How would the required term count change, and why? (Real libraries reduce arguments to keep $x$ small precisely to keep $\rho$ small.)
  3. Why is it safe to reorder the additions in the geometric series for stability, but dangerous to reorder the alternating-harmonic series? Tie your answer to absolute vs. conditional convergence (§22.8).
  4. The certified bound proves correctness without knowing the true value of $\ln 2$. Why is that property essential for a math library, and how does the alternating series test uniquely provide it?

Your turn

  1. Using the geometric tail bound $1/((N+1)2^N)$, find by hand the smallest $N$ that guarantees $\ln 2$ to single precision ($\approx 10^{-7}$). (Answer near $N=20$.)
  2. Derive a fast series for $\ln(3/2)$ by choosing $x$ in $-\ln(1-x)$, find $\rho$, and state how many terms give double precision.
  3. Explain, in two sentences, why a library would never use the Leibniz series $\pi/4 = 1 - \tfrac13 + \tfrac15 - \cdots$ to compute $\pi$ (see Exercise 22.25), invoking the same rate argument used here.

Further reading

  • Muller, J.-M. (2016). Elementary Functions: Algorithms and Implementation (3rd ed.). Birkhäuser. How real libraries evaluate log, exp, and friends with proven accuracy — argument reduction and series selection are exactly the moves above.
  • Higham, N. J. (2002). Accuracy and Stability of Numerical Algorithms (2nd ed.). SIAM. The standard reference on why summation order and convergence rate govern real-world accuracy.
  • Borwein, J., and Borwein, P. (1987). Pi and the AGM. Wiley. A tour of fast and slow series for classical constants, with the rate analysis made central.