Estimate logarithm quickly
11-23-2021, 09:01 PM (This post was last modified: 04-26-2022 11:09 AM by Albert Chan.)
Post: #13
 Albert Chan Senior Member Posts: 2,516 Joined: Jul 2018
RE: Estimate logarithm quickly
(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 "<")

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.
 « 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)