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)$?

Improve this question
$\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$
    – Zhi-Wei Sun
    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$
    – Steven Stadnicki
    May 4, 2022 at 15:22

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Zhi-Wei Sun
    May 14, 2022 at 6:57
  • $\begingroup$ @Zhi-WeiSun : Thank you for this information. $\endgroup$
    – Iosif Pinelis
    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.