Estimate logarithm quickly
04-26-2022, 05:01 PM
Post: #15
 Albert Chan Senior Member Posts: 2,006 Joined: Jul 2018
RE: Estimate logarithm quickly
(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
 « Next Oldest | Next Newest »

 Messages In This Thread Estimate logarithm quickly - Albert Chan - 08-21-2021, 03:39 PM RE: Estimate logarithm quickly - Albert Chan - 08-21-2021, 03:58 PM RE: Estimate logarithm quickly - Albert Chan - 08-21-2021, 05:41 PM RE: Estimate logarithm quickly - trojdor - 08-21-2021, 06:31 PM RE: Estimate logarithm quickly - Albert Chan - 08-21-2021, 11:42 PM RE: Estimate logarithm quickly - EdS2 - 08-23-2021, 06:44 AM RE: Estimate logarithm quickly - Albert Chan - 10-06-2021, 10:58 PM RE: Estimate logarithm quickly - Albert Chan - 10-18-2021, 01:02 PM RE: Estimate logarithm quickly - Albert Chan - 11-20-2021, 02:02 PM RE: Estimate logarithm quickly - Albert Chan - 11-22-2021, 01:49 AM RE: Estimate logarithm quickly - Albert Chan - 11-23-2021, 09:01 PM RE: Estimate logarithm quickly - Albert Chan - 04-26-2022 05:01 PM RE: Estimate logarithm quickly - Albert Chan - 11-26-2021, 06:24 PM RE: Estimate logarithm quickly - Csaba Tizedes - 10-07-2021, 06:25 PM RE: Estimate logarithm quickly - Albert Chan - 10-22-2021, 02:15 PM RE: Estimate logarithm quickly - Albert Chan - 04-27-2022, 10:02 PM RE: Estimate logarithm quickly - klesl - 04-26-2022, 05:52 PM RE: Estimate logarithm quickly - vaklaff - 04-28-2022, 04:33 PM RE: Estimate logarithm quickly - klesl - 04-28-2022, 05:02 PM

User(s) browsing this thread: 1 Guest(s)