Talk:Natural logarithm/Archive 2

What exactly do we mean by "cubic convergence"?

For simplicity, I will assume here that x ≥ 1 and thus ln (x) ≥ 0. If we apply Halley's method#Cubic convergence to our situation (trying to calculate the natural logarithm of x), using f(y) = exp (y) - x as we do in Natural logarithm#High precision, then we get the following

$\ln(x)-2\ {\frac {x-1}{x+1}}={\frac {3\exp(\eta )-2\exp(\xi )}{12-6(1-x)}}(\ln(x))^{3}$

for

$0\leq \eta ,\xi \leq \ln(x)$.

Thus

${\frac {3-2x}{6(x+1)}}(\ln(x))^{3}\,\leq \,\ln(x)-2\,{\frac {x-1}{x+1}}\,\leq \,{\frac {3x-2}{6(x+1)}}(\ln(x))^{3}$.

To extend this to 0 < x ≤ 1, replace x by 1 / x and observe that the result can be returned to the same form.

After that one can replace x by x / exp (y_n), getting

${\frac {3\exp(y_{n})-2x}{6(x+\exp(y_{n}))}}(\ln(x)-y_{n})^{3}\,\leq \,\ln(x)-y_{n+1}\,\leq \,{\frac {3x-2\exp(y_{n})}{6(x+\exp(y_{n}))}}(\ln(x)-y_{n})^{3}$.

OK? JRSpriggs (talk) 14:52, 1 May 2018 (UTC)

It is also useful to notice that for x > 0,

$0<{\frac {d}{dx}}\left(2\,{\frac {x-1}{x+1}}\right)={\frac {4}{(x+1)^{2}}}<{\frac {1}{x}}={\frac {d\ln(x)}{dx}}$

and thus

$\ln(x)\leq 2\,{\frac {x-1}{x+1}}\leq 0{\text{ or }}0\leq 2\,{\frac {x-1}{x+1}}\leq \ln(x)$.

Consequently,

$\ln(x)\leq y_{n+1}\leq y_{n}{\text{ or }}y_{n}\leq y_{n+1}\leq \ln(x)$,

that is, the iteration never overshoots. JRSpriggs (talk) 09:16, 2 May 2018 (UTC)

While

$x\approx \exp(y_{n})\,\Rightarrow \,\ln(x)-y_{n+1}\approx {\frac {1}{12}}(\ln(x)-y_{n})^{3}$,

it may be more useful to know how close to the "root" ln (x) one has to be before the cubic convergence becomes effective. More on this later. JRSpriggs (talk) 09:30, 2 May 2018 (UTC)

I did some calculations and got

$\vert \ln(x)-y_{n}\vert <1\,\Rightarrow \,\vert (\ln(x)-y_{n+1})-{\frac {1}{12}}(\ln(x)-y_{n})^{3}\vert \leq {\frac {0.52}{24}}\vert \ln(x)-y_{n}\vert ^{4}.$

Since ln(x)-y_n+1 is an odd function of ln(x)-y_n, it should be possible to increase the exponent of the bound from 4 to 5. However, I doubt that the extra effort would be worthwhile since this does nothing to get rid of the cubic term. For that, we would need a better function in the iteration. JRSpriggs (talk) 21:41, 4 May 2018 (UTC)

Belatedly, I realized that the calculations I was doing were a round-about way of getting the Taylor series of a certain function

$f(z)=z-2{\frac {\exp(z)-1}{\exp(z)+1}}=z-2\tanh \left({\frac {z}{2}}\right)$.

That made it a lot simpler. However, although I have reason to think that the coefficients will remain small numbers, the expression I have for the derivatives produces large positive and large negative numbers which mostly cancel. This means that it is still not easy, and so I cannot yet determine the error bound.

$\ln(x)-y_{n+1}={\frac {1}{12}}(\ln(x)-y_{n})^{3}+{\frac {-1}{120}}(\ln(x)-y_{n})^{5}+O((\ln(x)-y_{n})^{7}).$

More terms can be determined from hyperbolic function#Taylor series expressions. JRSpriggs (talk) 02:27, 6 May 2018 (UTC)

The main cost of performing an iteration is calculating the exponential of y_n. We can use the formula I gave in my first comment in this section to avoid doing the last exponential before comparing it to x to see whether it is close enough. Here is pseudo-code for the algorithm:

input x and tolerance.

verify that they are positive real numbers.

let y := 0.

let expy := 1.

begin loop:

let nexty = y + 2 ( (x - expy) / (x + expy) ).

let min := min (x, expy).

if ( 3 (x + expy) - 5 min ) | x - expy |³ ≤ tolerance 6 (x + expy) min³, then:

let lnx := nexty.

output lnx.

stop.

end if.

let y := nexty.

let expy := exp ( y ) *** this is the expensive step which we are trying to avoid.

end loop.

end routine.

Note that this uses the theorem

$\vert \ln(x)-y\vert \leq {\frac {\vert x-\exp(y)\vert }{\min(x,\exp(y))}}$

to get around the fact that we do not yet know what ln (x) is. JRSpriggs (talk) 03:40, 6 May 2018 (UTC)

The test for exiting the loop is intended to achieve the same effect as:

$\vert \ln(x)-y_{n+1}\vert \leq \operatorname {tolerance}$

but without having to calculate exp (y_n+1) and without knowing ln (x). Can the test be simplified? Yes, if you are not too picky about getting it right. We could define another variable

let threshold := cube_root ( 12 tolerance )

and compare | x - expy | ≤ threshold min. Or we could use nexty as a substitute for ln (x), which would make the test | nexty - y | ≤ threshold. JRSpriggs (talk) 13:03, 7 May 2018 (UTC)

To get a general idea of how this technique (the iterative method, not the program) converges, I ran a test beginning with a distant initial guess y₀. I got the following:

ln (x) - y₀ = 4.0000000000

ln (x) - y₁ = 2.0719448398

ln (x) - y₂ = 5.193595899·10^-1

ln (x) - y₃ = 1.13675706·10^-2

ln (x) - y₄ = 1.224097816·10^-7

Notice that at first it moves closer by a little less than 2 which is the limit on how far it can move in one iteration. Then after it comes within 1 of the correct value, the cubic convergence begins to take hold. JRSpriggs (talk) 04:20, 8 May 2018 (UTC)

An alternative iteration to get the natural logarithm

I discussed the current version of Natural logarithm#High precision in the previous section of talk, Talk:Natural logarithm#What exactly do we mean by "cubic convergence"?. Now, I would like to suggest an alternative. Thanks to the third order Householder's method, we could use

$y_{n+1}=y_{n}+3{\frac {x^{2}-(\exp(y_{n}))^{2}}{x^{2}+4x\exp(y_{n})+(\exp(y_{n}))^{2}}}.$

Advantages: It converges faster, moving upto 3 when far away (as opposed to 2 for the Halley's method) per iteration and having quintic (fifth power) convergence (usually the third Householder's method only gives quartic convergence, but this is a especially favorable situation) when close rather than the cubic convergence of the Halley's method. This may allow for fewer iterations of the method and thus fewer evaluations of the power series for the exponential.

Disadvantages: It is a change, and any change may cause confusion. It requires three more multiplications to compute the adjustment. It is slightly more complex than the previous method. Although, I have proved that the convergence is quintic, I do not have the coefficient yet. If it is too large, that might be a problem.

Do you think that we should change the section to use this new method? JRSpriggs (talk) 05:05, 9 May 2018 (UTC)

I don't think it's appropriate for this article. In fact, a whole lot of the stuff currently in the "Series" and "Continued fraction" sections should probably be pruned out, as well. This is not an article on numerical methods for computing logarithms. --Trovatore (talk) 09:46, 9 May 2018 (UTC)

In that case, can we create an article on numerical methods for computing logarithms and transfer that material to it? JRSpriggs (talk) 00:14, 10 May 2018 (UTC)

Hmm, is that a topic called out as such in the literature? Certainly numerical methods are an important area of study and can be covered in Wikipedia, but going into detail about the pluses and minuses of specific ways of computing a particular function feels a little "handbook-like" to me.

That said, I wouldn't object to it nearly as much in its own article. Just make sure all the methods are sourced (and specifically for computing logs). Also convergence estimates, caveats, etc, should have sources that specifically say this is what happens when you're computing logarithms. --Trovatore (talk) 00:42, 10 May 2018 (UTC)

For the iteration suggested above,

$\ln(x)-y_{n+1}={\frac {1}{180}}(\ln(x)-y_{n})^{5}-{\frac {1}{1512}}(\ln(x)-y_{n})^{7}+O((\ln(x)-y_{n})^{9})$.

JRSpriggs (talk) 06:08, 10 May 2018 (UTC)

Assuming that errors in calculating exp (y_n) and y_n+1 from x and y_n are negligible,

$0\leq \ln(x)-y_{n+1}\leq \min \left({\frac {(\ln(x)-y_{n})^{5}}{180}},\,\ln(x)-y_{n}\right)\quad {\text{ or }}\quad \max \left({\frac {(\ln(x)-y_{n})^{5}}{180}},\,\ln(x)-y_{n}\right)\leq \ln(x)-y_{n+1}\leq 0.$

JRSpriggs (talk) 01:27, 17 May 2018 (UTC)