Post Reply 
Estimate logarithm quickly
10-18-2021, 01:02 PM (This post was last modified: 10-18-2021 04:30 PM by Albert Chan.)
Post: #9
RE: Estimate logarithm quickly
(10-06-2021 10:58 PM)Albert Chan Wrote:  
(10-06-2021 05:12 PM)Eric Rechlin Wrote:  Computing Logarithms by Integration - Richard Schwartz (17:02)

Thanks for the video. I finally "get" Doerfler's formula Smile

Both methods actually are one and the same.
Doerfler's Borchardt's algorithm + Richardson extrapolation: d(k,k) ≈ ∫(n^t,t,0,1) = (n-1)/ln(n)

CAS> d00 := a0 := (1+n)/2

CAS> g0 := sqrt(n)
CAS> d01 := factor(a1 := (a0+g0)/2)       → (n + 2*n^(1/2) + 1)/4
CAS> d11 := factor(d01 + (d01-d00)/3)    → (n + 4*n^(1/2) + 1)/6

CAS> g1 := sqrt(a1*g0)       → (sqrt(sqrt(n)*(n+1)+2*n))/2

This seemingly looking "AGM" is really to evaluate doubled points. (*)
We can rewrite g1 = (√√n) * (1+√n)/2, expanded:

CAS> g1 := (n^(1/4) + n^(3/4))/2
CAS> d02 := factor(a2 := (a1+g1)/2)       → (n + 2*n^(3/4) + 2*n^(1/2) + 2*n^(1/4) + 1)/8
CAS> d12 := factor(d02 + (d02-d01)/3)    → (n + 4*n^(3/4) + 2*n^(1/2) + 4*n^(1/4) + 1)/12
CAS> d22 := factor(d12 + (d12-d11)/15)   → (7*n + 32*n^(3/4) + 12*n^(1/2) + 32*n^(1/4) + 7)/90

(*) We can "see" doubling of points by thinking weights as a "number"
weight of a3 = 122222221 = 11111111*11
weight of g2 = 1010101 = 11111111/11
weight of g3 = √(a3*g2) = 11111111
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 - 10-18-2021 01: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)