Estimate logarithm quickly

[Albert Chan]

(11-23-2021 09:01 PM)Albert Chan Wrote:  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)
...

(*) 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.

To proof log2(13) > 3.7 with next convergent is equivalent to:

R = ln(13^3/2^11) / ln(16/13) > (3*3.7-11) / (4-3.7) = 0.1/0.3
R = atanh(t1 = 149/4245) / atanh(t2 = 3/29) > 1/3

Since t1 < t2, if we estimate atanh(x) ≈ x, we get R upper bound instead, not what we wanted.

R < (t1/t2) ≈ 0.339301

Tighter atanh bound is better, but still the wrong bound.

R < (t1/t2) * (1-t2²/3)/(1-t1²/3) ≈ 0.338230

(t1/t2) matched 2 digits. We may claim better R good for 0.338 > 1/3, but there is surer way.

A trick is to convert atanh to asinh, with alternate sign series expansion
see Arc SOHCAHTOA method, for hyperbolics

R = atanhq(149²/4245²) / atanhq(3²/29²)                                       // TOA
   = asinhq(s1 = 149²/(4245²-149²)) / asinhq(s2 = 3²/(29²-3²))      // SOH

R = sqrt(s1/s2) * [1, (1+s2/6)/(1+s1/6)] = [0.337689, 0.338228] > 1/3 QED

Instead of atanh 1-sided estimate, asinh allowed ratio estimate be bracketed.
(here, we don't need upper bound. R ≥ sqrt(s1/s2) > 1/3 is enough)

Bonus: asinh converge faster than atanh.
Below R bounds, last factor (1+ε) → 1/(1-ε), for better pade estimate.

R < (t1/t2) * (1+(t1²/3)/(1-3/5*t1²)) / (1+(t2²/3)/(1-3/5*t2²))
   = 0.338226 271757      // error = -9602 ulp

R > sqrt(s1/s2) * (1-(s1/6)/(1+9/20*s1)) / (1-(s2/6)/(1+9/20*s2))
   = 0.338226 257560      // error = +4595 ulp