2
$\begingroup$

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<n\le 85/4$, 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<n<(2+\sqrt5)^2\approx 17.944$, 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)$?

$\endgroup$
4
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Logarithm#Calculation $\endgroup$
    – Wojowu
    May 4, 2022 at 14:28
  • $\begingroup$ For $1<n<17.9$, my converging ratio $(1)$ is better than the one provided by Wikipedia. $\endgroup$ May 4, 2022 at 14:42
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Wojowu
    May 4, 2022 at 15:09
  • 2
    $\begingroup$ 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). $\endgroup$ May 4, 2022 at 15:22

1 Answer 1

10
$\begingroup$

Theorem 9.1 by Brent states the following:

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ May 14, 2022 at 6:57
  • $\begingroup$ @Zhi-WeiSun : Thank you for this information. $\endgroup$ May 15, 2022 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.