How to determine the almost accurate initial guess to calculate the $\ln(x)$ via Newton-Raphson method?

Question

I'm developing my own Real Number class, and for that, I have to implement the Natural Logarithm function.

I've used Maclaurin series of Natural log with iteration of 300 or 500. The division method for my class is also defined by me, and user can get truly "unlimited" digits after the decimal point as the result of division (if exists).

Now, the Maclaurin series is converging very slowly. After 300 or 500 iterations, it is giving correct precision up to 15 or 16 digits. But in my class, user can set the number of digits after the decimal point for the answer of the natural log.

I searched in internet, and found two methods - Halley's Method and Newton's Method. I decided to go with Newton's method, but unable to determine a suitable initial guess to start the iteration.

I want a generalized way to get the initial guess for any Argument to the natural log function. One way I'm thinking about is, finding $n \in \mathbb{Z}$ such that $e^n \leq x < e^{n+1}$ to calculate $\ln(x)$ where $x>0$. But I want to avoid this because, again I'm using the Taylor Series to compute $e^x$ and it takes 300 iterations per computation.

Is there any other way to find a good initial guess? Please suggest me.

Answer 1

The suggestion by @LutzLehmann reduces the problem of computing $\log(x)$ to the interval $x \in [1,2]$. Here you can approximate $\log(x)$ using a linear function $$\phi(x) = a x + b.$$ It is not surprising that $a = \log(2)$ is a good choice but a short calculation will establish that the best polynomial with respect to the infinity norm is represented by $$ a = \log(2), \quad b = - \frac{1+ a + \log(a)}{2}.$$ The error function $e(x) = \log(x) - \phi(x)$ peaks at the endpoints of the interval and at $x=\frac{1}{a}$ and $$ | \log(x) - \phi(x) | \leq a + b \approx 2.98 \cdot 10^{-2}.$$ You will find that $x_0 = \phi(x)$ is a good initial guess for $\log(x)$ when $x \in [1,2]$.

1. You will need to compute $\log(2)$ once and then recycle that value in the future.
2. You will need an implementation of the exponential function in order to refine the initial guess by applying, say, Newton's method to the equation $$e^x - \alpha = 0.$$

If $|x| \leq \delta$ is sufficiently small, then you can approximate $e^x$ using a truncated Taylor series $$e^x \approx p_n(x) = \sum_{j=0}^n \frac{x^j}{j!}.$$ If $|x| > \delta$, but $|x| \leq 2^m \delta$ for an integer $m \ge 0$, then you can approximate $y = e^x$ as follows $$\begin{align} t &= x/2^m \\ e^t & \approx p_n(t) \\ z_0 &= p_n(t) \\ z_j &= z_{j-1}^2, \quad j=1,2,...,m. \end{align}$$ and $y \approx z_m$ will be a good approximation provided that $\delta$ is sufficiently small and $n$ is sufficiently large. You will it straightforward to compute $e^t$ with a small relative error when $t$ is small and positive. When $t$ is small and negative, then you can compute $e^t$ using $e^t = 1/e^{-t}$.

Answer 2

When you want to solve for $x$ the equation $f(x)=0$ using Newton method, Darboux theorem says that, if no problem with the second derivative, then choosing $x_0$ such that $$f(x_0)\times f''(x_0) >0$$ will gives convergence without any overshoot.

Answer 3

$e^x=1+x+x^2/2 +... \implies x\approx \frac{-1 \pm \sqrt{1-2(1-e^x)}}{1}$

$\implies x \approx -1 \pm \sqrt{2e^x-1}\implies \ln x \approx -1 \pm \sqrt{2x-1}$

So a good initial guess is for $1/2\le x \le 1$ is $-1 \pm \sqrt{2x-1}$

Take the reciprocal of larger numbers then use Newton's to find the natural log, then multiply the answer by negative 1. Should make progress.

Answer 4

Another cute approximation for $\log(1+x)$ on $-0.5 < x < 1$ which comes from applying the Pade transformation to its rather badly convergent Taylor series in $x$ is

$$log(1+x) = x - \frac {x^2} 2 + \frac {x^3} 3 - \dots \approx \frac {x(6+x)} {(6+4x)} \ .$$

It immediately gives $\log(2) = 0.7$ and a simple tweak will get $0.693$. The only downside is that it requires a fast divide to be useful.