Reducing the Number of Slope Evaluations for Newton's Method

[Albert Chan]

(11-12-2024 12:27 PM)Namir Wrote:  And solve for, x to find the value of x that makes the 10^7 summations equal to 8 (typo, should be 9, from code). The answer is x = 1.855 and it does take a while for each function call to perform ten million loop iterations!
This is an example where reducing the number of function calls pays off.

1st, we should make curve as straight as possible 1/x should be flipped

Σ(1/(i*x), i=1..n) = y0      → 1/Σ(1/(i*x), i=1..n) = 1/y0

This patch would speed up convergence greatly.

< RETURN (y0 - y);
> RETURN (y0 - y) / (y0*y);

2nd, x can be pulled out, remaining sum is just harmonic number.
We should not have f(x) keep calculating the same constant.

x / H(n) = 1/y0
x = H(n) / y0

3rd, no need to sum 10 million terms, we can estimate H(huge n)

(08-28-2020 09:26 PM)Albert Chan Wrote:  \(\qquad\qquad\exp( \psi(x+1/2)) = x
+\frac{1}{24 \cdot x
+\Large\frac{1}{\frac{10}{37} \cdot x
+\frac{1}{\frac{689976}{74381} \cdot x \;
+\; \cdots}}} \)

H(n) = Ψ(n+1) + gamma = Ψ((x=n+0.5) + 0.5) + gamma

lua> n = 1e7
lua> x = n + 0.5
lua> gamma = 0.5772156649015329
lua> Hn = log(x + 1/(24*x + 3.7/x)) + gamma
lua> Hn
16.69531136585985
lua> Hn / 9
1.8550345962066501