Estimate logarithm quickly
11-22-2021, 01:49 AM
Post: #12
 Albert Chan Senior Member Posts: 2,230 Joined: Jul 2018
RE: Estimate logarithm quickly
Here is an example, to prove 13^40 > 4^74, difference of only 1.2%
The video make use of (13^3 = 2197) ≈ (2^11 = 2048). Here, we don't use it.

We compare ratio of 4th root, (difference is now tiny 0.3%, but it doesn't matter)
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

RHS make the base close to 1, which is needed for Doerfler's formula to work well.
Note: Constant 6 of Doerfler's formula is skipped. (it will be cancelled anyway)

Comparing numerator/denominator ratio with its logarithm, an increasing function.

(3/2*ln(169/64)) / (7/2*ln(256/169))
> (3/7) * ((169/64-1)/(4*(13/8) + 169/64+1)) / ((256/169-1)/(4*(16/13) + 256/169+1))
= (3/7) * (105/649) / (29/419)
= 18855/18821
≈ 1.00181 > 1 ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ // ⇒ 13^10 > 2^37, QED

We give up a bit of accuracy by doing ln(x^2) instead of ln(x), to avoid square root mess.
Had we use ln(x) instead, we would get a ratio of 1.00208 (true ratio ≈ 1.00210)

---

Actually, we can do better, (13/8 = 1.625) ≈ (256/169 ≈ 1.515)
Both under-estimated errors have similar size, thus mostly cancel each other.

Apply Doerfler's formula for (3*ln(13/8)) / (7/2*ln(256/169)), we get a ratio of 1.00209
 « 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)