Post Reply 
Estimate logarithm quickly
11-22-2021, 01:49 AM
Post: #12
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
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
Estimate logarithm quickly - Albert Chan - 08-21-2021, 03:39 PM
RE: Estimate logarithm quickly - trojdor - 08-21-2021, 06:31 PM
RE: Estimate logarithm quickly - EdS2 - 08-23-2021, 06:44 AM
RE: Estimate logarithm quickly - Albert Chan - 11-22-2021 01:49 AM
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)