# How to evaluate $\log x$ to high precision "by hand"

I want to prove

$$\log 2<\frac{253}{365}.$$

This evaluates to $0.693147\ldots<0.693151\ldots$, so it checks out. (The source of this otherwise obscure numerical problem is in the verification of the Birthday problem.) If you had to do the calculation by hand, what method or series would you use to minimize the number of operations and/or size of the arguments involved in order to get this result? I'm doing a formal computer proof, so it's not exactly by hand, but I still want to minimize the number of evaluations needed to get to this result.

One method is by rewriting it into $2<e^{253/365}$ and using the power series; since it is a positive series you know you can stop once you have exceeded $2$. Working this out, it seems you need the terms $n=0,\dots,7$ of the sum, and then it works out to

$$2<\sum_{n=0}^7\frac{(253/365)^n}{n!}=\frac{724987549742673918011}{362492763907870312500},$$

which involves rather larger numbers than I'd like. There is also the limit $(1+\frac{253}{365n})^n\to$ $e^{253/365}$, but the convergence on this is not so good; it doesn't get past $2$ until $n=68551$, at which point we are talking about numbers with $507162$ digits.

For $\log 2$ there is of course the terribly converging alternate series $\log 2=\sum_{n=1}^\infty\frac{-(-1)^n}n$, which requires $71339$ terms to get the desired bound. This can be improved by pushing the series into its geometrically convergent region as $\log 2=2\log{\sqrt 2}=-2\sum_{n=1}^\infty \frac{(1-\sqrt2)^n}n$, but now there is the added complication of estimating $\sqrt 2$ to sufficient precision. Assuming that $\sqrt 2$ is known exactly, you need to take this series out to $12$ terms, at which point we are verifying

$$\frac{1959675656 \sqrt2-2771399891}{1011780}<0\Leftarrow2771399891^2>1959675656^2\cdot 2.$$

What other methods are there to do a calculation like this? Is there a way to use a root-finding method like Newton's to get a strict bound out with fast convergence?

• One Newton-like method is Newton's method. Commented Apr 16, 2015 at 15:28
• @GFauxPas Yes, but Newton's method as is only gives a convergent series - can you put bounds on the distance to the root? Commented Apr 16, 2015 at 15:29
• The book Euler: Master of Us All has a section on logs that I think might be relevant. (There's an online free version, I think.) Commented Apr 16, 2015 at 15:36
• Also, whenever I do anything involving $e$ or $\ln$, I like to try to do it without any calculus, using only the formula $e^x\ge x+1$. (It's quite effective; it lets you prove that $\ln2=1-\frac12+\frac13-\dotsb$, for example.) Commented Apr 16, 2015 at 16:04
• A practical method to get the fraction $\dfrac {253}{365}$ is to start with the (supposed known) value $\ln(2)\approx 0.69315$ and to evaluate the continued fraction up to $[0, 1, 2, 3, 1, 6, 3, 1]$ that is : $$\ln(2)\approx 0.69315\approx\cfrac 1{1+\cfrac 1{2+\cfrac 1{3+\cfrac 1{1+\cfrac 1{6+\cfrac 1{3+\cfrac 11}}}}}}=\frac {253}{365}$$ Commented Apr 16, 2015 at 16:15

You could express this as $\log(1/2) > -\dfrac{253}{365}$. The series $$\log(1/2) = \log(1-1/2) = -\sum_{n=1}^\infty \dfrac{1}{n 2^n}$$ converges quickly, and has nice bounds: $$\log(1/2) \ge - \sum_{n=1}^{N-1} \dfrac{1}{n 2^n} - \sum_{n=N}^\infty \dfrac{1}{N 2^n} = - \sum_{n=1}^{N-1} \dfrac{1}{n 2^n} - \dfrac{1}{N 2^{N-1}}$$

EDIT: Another way to write it is $2 < (\exp(1/365))^{253}$, and use the continued fraction $$\exp(1/n) = 1 + \dfrac{1}{n-1 + \dfrac{1}{1 + \dfrac{1}{1 + \dfrac{1}{3n-1 + \dfrac{1}{1+ \dfrac{1}{1+ \dfrac{1}{5n-1 + \ldots}}}}}}}$$ In particular, $$\exp(1/365) >1+ 1/(364+1/(1+1/(1+1/1094))) = \dfrac{800080}{797891}$$ and (if you don't mind exact arithmetic with big integers) $$\left(\dfrac{800080}{797891}\right)^{253} > 2$$

• Oh, that's a good one, forgot about that symmetry of $\log$. For the record you need $12$ terms of that series to get the stated bound, at which point you are verifying $\frac{3935051}{5677056}<\frac{253}{365}$, which is quite respectable. Commented Apr 16, 2015 at 15:36

Since $\log 2=2\operatorname{arctanh}\frac{1}{3}$, we may use the series: $$\log 2 = \sum_{n\geq 0}\frac{2}{(2n+1)\,3^{2n+1}}$$ and the bound: $$\sum_{n\geq 4}\frac{2}{(2n+1)\,3^{2n+1}}\leq\sum_{n\geq 4}\frac{2}{3^{2n+3}}=\frac{1}{157464}$$ to prove that (we just need the terms of the previous series till $n=4$): $$\log 2\approx \frac{4297606}{6200145} = \color{red}{0.69314}\color{blue}{60474\ldots}$$ where the red digits are the right ones for sure.

• Yep, just about to add this one following @columbus8myhw's suggestion to check Euler's "strongly convergent" $\log\frac{1+x}{1-x}=2\sum_{n=0}^\infty\frac{x^{2n+1}}{2n+1}$, which is essentially equivalent to using the arctan expansion. $4$ terms is very nice! Commented Apr 16, 2015 at 15:54

We may use this generalized continued fraction to get directly excellent fractions as near as wished of $\,\ln\,2$ : $$\ln\,2=\cfrac 1{1+\cfrac 1{2+\cfrac 1{3+\cfrac 2{2+\cfrac 2{5+\cfrac 3{2+\cfrac 3{7+\cfrac 4{2+\cfrac 4{9+\cdots}}}}}}}}}=b_0+\cfrac {a_1}{b_1+\cfrac {a_2}{b_2+\cfrac {a_3}{b_3+\cfrac {a_4}{\cdots}}}}$$

Let's obtain the first successive convergent using the previous values of $a_k,b_k$ and $\;\left[\matrix {n_k\\d_k}\right]=\left[\matrix {n_{k-1}\;n_{k-2}\\d_{k-1}\;d_{k-2}}\right]\left[\matrix {b_k\\a_k}\right],\quad\left[\matrix {n_1\\d_1}\right]=\left[\matrix {b_0\,b_1+a_1\\b_1}\right]=\left[\matrix {1\\1}\right],\;\left[\matrix {n_0\\d_0}\right]=\left[\matrix {b_0\\1}\right]=\left[\matrix {0\\1}\right]$ :

\begin{array} {l|c|ccccc} k&b_k,a_k&&&f_k=\dfrac{n_k}{d_k}\\ \hline\\ 1 & \color{#0000ff}{1,1} &\cfrac 1{1}&&=\cfrac 1{1}=\dfrac {n_1}{d_1}\\ 2 & \color{#0000ff}{2,1} & \cfrac 1{1+\frac 1{2}}&=\dfrac{n_1 b_2+n_0 a_2}{d_1 b_2+d_0 a_2}=\dfrac{1\cdot\color{#0000ff}{2}+0\cdot\color{#0000ff}{1}}{1\cdot\color{#0000ff}{2}+1\cdot\color{#0000ff}{1}}&=\dfrac 23=\dfrac {n_2}{d_2}\\ 3 & \color{#0000ff}{3,1} & \cfrac 1{1+\frac 1{2+\frac 1{3}}}&=\dfrac{n_2 b_3+n_1 a_3}{d_2 b_3+d_1 a_3}=\dfrac{2\cdot\color{#0000ff}{3}+1\cdot\color{#0000ff}{1}}{3\cdot\color{#0000ff}{3}+1\cdot\color{#0000ff}{1}}&=\dfrac {7}{10}=\dfrac {n_3}{d_3}\\ 4 & \color{#0000ff}{2,2} &\cfrac 1{1+\frac 1{2+\frac 1{3+\frac 2{2}}}}&=\dfrac{7\cdot\color{#0000ff}{2}+2\cdot\color{#0000ff}{2}}{10\cdot\color{#0000ff}{2}+3\cdot\color{#0000ff}{2}}&=\dfrac {18}{26}=\dfrac {9}{13}\\ 5 & \color{#0000ff}{5,2}&\cfrac 1{1+\frac 1{2+\frac 1{3+\frac 2{2+\frac 2{5}}}}}&=\dfrac{18\cdot\color{#0000ff}{5}+7\cdot\color{#0000ff}{2}}{26\cdot\color{#0000ff}{5}+10\cdot\color{#0000ff}{2}}&=\dfrac {104}{150}=\dfrac {52}{75}\\ 6 & \color{#0000ff}{2,3}&\cfrac 1{1+\frac 1{2+\frac 1{3+\frac 2{2+\frac 2{5+\frac 3{2}}}}}}&=\dfrac{104\cdot\color{#0000ff}{2}+18\cdot\color{#0000ff}{3}}{150\cdot\color{#0000ff}{2}+26\cdot\color{#0000ff}{3}}&=\dfrac {262}{378}=\dfrac {131}{189}\\ 7 & \color{#0000ff}{7,3}&\cfrac 1{1+\frac 1{2+\frac 1{3+\frac 2{2+\frac 2{5+\frac 3{2+\frac 3{7}}}}}}}&=\dfrac{262\cdot\color{#0000ff}{7}+104\cdot\color{#0000ff}{3}}{378\cdot\color{#0000ff}{7}+150\cdot\color{#0000ff}{3}}&=\dfrac {2146}{3096}=\dfrac {1073}{1548}\\ 8 & \color{#0000ff}{2,4}&\cfrac 1{1+\frac 1{2+\frac 1{3+\frac 2{2+\frac 2{5+\frac 3{2+\frac 3{7+\frac 4{2}}}}}}}}&=\dfrac{2146\cdot\color{#0000ff}{2}+262\cdot\color{#0000ff}{4}}{3096\cdot\color{#0000ff}{2}+378\cdot\color{#0000ff}{4}}&=\dfrac {5340}{7704}=\dfrac {445}{642}\\ 9 & \color{#0000ff}{9,4}&\cfrac 1{1+\frac 1{2+\frac 1{3+\frac 2{2+\frac 2{5+\frac 3{2+\frac 3{7+\frac 4{2+\frac 4{9}}}}}}}}}&=\dfrac{5340\cdot\color{#0000ff}{9}+2146\cdot\color{#0000ff}{4}}{7704\cdot\color{#0000ff}{9}+3096\cdot\color{#0000ff}{4}}&=\dfrac {56644}{81720}=\dfrac {14161}{20430}\\ \cdots &\\ \end{array}

For even values of $k$ the fraction will be too small while for odd values it will be too large. The last fraction provided here (for $k$ odd) is larger than $\,\ln\,2\,$ but smaller than your fraction proving your claim. The previous approximation is smaller than $\,\ln\,2\,$ (but more precise too than your fraction).

As observed earlier a convergent from the continued fraction of the numerical approximation $\,0.69315\;$ returns directly the initial fraction : $$\ln(2)\approx 0.69315\approx\cfrac 1{1+\cfrac 1{2+\cfrac 1{3+\cfrac 1{1+\cfrac 1{6+\cfrac 1{3+\cfrac 11}}}}}}=\frac {253}{365}$$

$\log 2 = \log (1 + 1/3) + \log (1 + 1/2)$, and each of those terms can be easily evaluated to the desired predictions using $\log (1+x) = x - x^2/2 + x^3/3 - \cdots$. There are other ways to write $\log 2$ as a sum of logarithms that will let you write it as a sum of more, but faster-converging series; I'm not sure what minimizes the arithmetic. In general we have

$$\log 2 = \log \left( 1 + {1 \over 2n-1} \right) + \log \left( 1 + {1 \over 2n-2} \right) + \cdots + \log \left(1 + {1 \over n} \right)$$

of which the original identity I gave is the $n = 2$ case.