Estimate logarithm quickly

[Albert Chan]

(11-22-2021 01:49 AM)Albert Chan Wrote:  FYI, 37/10 is a convergent of log2(13), thus below ratio is very close to 1.

13^10 / 2^37 = (13/8)^3 / (16/13)^7

Another way to proof above ratio > 1 is to proof log2(13) > 37/10
However, we have to get the right inequality (here, we wanted ">", not "<")

We can proof this instead, which leads to the same thing.
To proof: ln(13/8)/ln(16/13) > (3.7-3)/(4-3.7) = 7/3 ≈ 2.33333

We use a simple formula to test, ln(x) = 2*atanh(y), where y = (x-1)/(x+1)

Y(x) := (x-1)/(x+1);       // if x is fractions, Y(n/d) = (n-d)/(n+d)

y1>y2>0: atanh(y1)/atanh(y2) > (y1/y2)

ln(13/8)/ln(16/13) > Y(13/8)/Y(16/13) = (5/21)/(3/29) = 145/63 ≈ 2.30159

atanh(y) ≈ y not enough. We add pade correction: atanh(y)/y > 1/ (1 - y^2/3)

y1>y2>0: atanh(y1)/atanh(y2) > (y1/y2) * (3-y2^2)/(3-y1^2)

(145/63) * (3-(3/29)^2)/(3-(5/21)^2) = 43995/18821 ≈ 2.33755 > 7/3 QED

---

8/13 < 1 < 16/13                  → log2(13) = (3/1, 4/1)

Try next semi-convergent: (3+4)/(1+1) = 7/2       (*)

2^7/13^2 = 128/169 < 1      → log2(13) = (7/2, 4/1)

(169/128 ≈ 1.32031) > (16/13 ≈1.23077)

We can keep the same denominator, to ensure we are solving for tighter z lower bound.

ln(169/128)/ln(16/13) > Y(169/128)/Y(16/13) = (41/297)/(3/29) = 1189/891

solve((2z-7)/(4-z) > 1189/891, z), we get z = [3.70010, 4)       → log2(13) > 37/10 QED

(*) We do not want log2(13) next convergent, (3+4*2)/(1+1*2) = 11/3,
because it guaranteed to be in the denominator, solving the tighter upper bound instead.