Abrazolica

This is a note on how to calculate logarithms in terms of continued fractions. The number \(x=\log_b{a}\) is the log of \(a\) to the base \(b\). It solves the equation \(a=b^x\). To find \(x\), we start by finding the integer \(n_0 \ge 0\) such that

\[b^{n_0} < a < b^{n_0+1}\]

Given \(n_0\), we can write \(a\) as \(a=b^{n_0+1/x_1}\) for some yet to be determined number \(1/x_1 < 1\). Our logarithm is then \(x=n_0+1/x_1\) and the problem is to find \(x_1\). We get an equation for \(x_1\) by defining \(b_1=a/b^{n_0}=b^{1/x_1}\) or \(b=b_1^{x_1}\). This shows that \(x_1\) is the log of \(b\) to the base \(b_1\). As above, we next find the integer \(n_1 \ge 0\) such that

\[b_1^{n_1} < b < b_1^{n_1+1}\]

We can then write \(b\) as \(b=b_1^{n_1+1/x_2}\) for a yet to be determined number \(1/x_2 < 1\). So we have \(x_1=n_1+1/x_2\) and the same procedure repeats to find \(x_2\), \(x_3\), and so on. These terms are related as follows

\[x=n_0+1/x_1\] \[x_1=n_1+1/x_2\] \[x_2=n_2+1/x_3\] \[\cdots\]

In continued fraction form \(x\) is then

\[x = n_0 + \cfrac{1}{n_1 + \cfrac{1}{n_2 + \cfrac{1}{n_3 + \cdots}}}\]

What we have described so far is basically Shanks' algorithm for calculating logarithms. For more information on this algorithm see the following references.

"A Logarithm Algorithm", Daniel Shanks, Mathematical Tables and Other Aids to Computation, Vol. 8, No. 46 (April 1954), pp. 60-64

"On Shanks' Algorithm For Computing The Continued Fraction Of logb.", Terence Jackson and Keith Matthews, Journal of Integer Sequences, 5.2 (2002): 3.

One way to improve the algorithm is to use the following approximation for \(x_i\)

\[x_i=\frac{b_i+1}{b_i-1}\frac{b_{i-1}-1}{b_{i-1}+1}\]

This is an excellent approximation for \(x_i=\log_{b_i}{b_{i-1}}\) in the range \(1\le b_{i-1}\le b_i\). At the endpoints of the range the approximation gives the correct answers \(x_i=0\) and \(x_i=1\). The figure below shows \(x=\log_2{b}\) and the approximation \(x=3\frac{b-1}{b+1}\) for \(1\le b\le 2\). The approximation is excellent near the endpoints of the range and is worse near the center.

It is easy to see that the \(b_i\) terms in the above algorithm approach \(1\) for increasing \(i\) so the approximation for \(x_i\) will also improve. It is always possible to get \(n_i\) by taking the integer part of \(x_i\) but we can also get \(n_{i+1}\) and more terms by doing a continued fraction expansion of \(x_i\). For example we have

\[n_{i+1}=\left\lfloor{\frac{1}{x_i-n_i}}\right\rfloor\]

With \(b_{i-1}\approx 1\) you can get \(n_{i+2}\), \(n_{i+3}\) and more terms from \(x_i\). If the goal is to calculate the logarithm and not the continued fraction then the approximation for \(x_i\) can be used as the last term in the continued fraction for an excellent and fast approximation of the logarithm.