# What's the fastest way to compute $\log n$ for $n>1$?

As it is well known, if $$|x|<1$$ then we can compute $$\log(1+x)$$ by the Taylor series $$\log(1+x)=x-\frac{x^2}2+\frac{x^3}3-\cdots.$$ Thus, to compute $$\log n$$ with $$n>1$$, we may employ the series $$\log n=-\log\left(1-\frac{n-1}n\right)=\sum_{k=1}^\infty\frac{1}k\left(\frac{n-1}n\right)^k,$$ which converges at geometric rate with ratio $$(n-1)/n$$. Wikipedia provides a more efficient series for computing $$\log n$$: $$\log n=2\sum_{k=0}^\infty\frac1{2k+1}\left(\frac{n-1}{n+1}\right)^{2k+1}$$ which converges at geometric rate with ratio $$(n-1)^2/(n+1)^2$$.

For $$1, I have found series for $$\log n$$ which converges at geometric rate with ratio $$-\frac{(n-1)^4}{16n(n+1)^2}.\tag{1}$$ If $$1, then $$\frac{(n-1)^4}{16n(n+1)^2}<\frac{(n-1)^2}{(n+1)^2}$$ and so my series for computing $$\log n$$ is more efficient.

Question. What's the fastest way to compute $$\log n$$ for $$n>1$$? Is there a series for $$\log n$$ which converges at geometric rate with ratio better than $$(1)$$?

• en.wikipedia.org/wiki/Logarithm#Calculation May 4, 2022 at 14:28
• For $1<n<17.9$, my converging ratio $(1)$ is better than the one provided by Wikipedia. May 4, 2022 at 14:42
• You may want to conider clarifying exactly what range you are interested in. Efficient algorithms for large $n$ will differ significantly for ones for small $n$. May 4, 2022 at 15:09
• Are you interested only in the rate of convergence of a geometric series, or in the actual computation time involved in computing $\log n$? And if the latter, with respect to relative or absolute error? Fast means of computing $\log n$ are most likely to involve division by some power of $e$, since that can be computed to high accuracy rather quickly. (Or alternately, division by some power of 2 with a high-precision computed value of $\ln 2$ serving a similar role). May 4, 2022 at 15:22

If $$x>0$$ is a precision $$n$$ number, then $$\log(x)$$ may be evaluated to precision $$n$$ in time $$\sim13M(n) \log_2 n$$ as $$n\to\infty$$ [assuming $$\pi$$ and $$\log(2)$$ precomputed to precision $$n+O(n/ \log(n))$$].
Here $$M(n)=O(n\log(n)\log\log(n))$$ is the time required to perform a precision $$n$$ multiplication.
The corresponding method of the evaluation of $$\log(x)$$ involves A–G mean iterations. Brent also says "There are several algorithms for evaluating $$\log(x)$$ to precision $$n$$ in time $$O(M(n) \log(n))$$."
So, the time to compute $$\log(x)$$ to precision $$n$$ is greater than the time to do a precision $$n$$ multiplication only by a logarithmic factor.
• In Brent's paper, the Taylor series for $\log (1-\delta)$ with $\delta$ small is used. For small $\delta$, I have series for $\log(1-\delta)$ converging rapidly. see my preprint available from arxiv.org/abs/2204.08275. May 14, 2022 at 6:57