I was reading about generators as series in python. To recap, here is a series represented as a generator (lazy list), and euler's series accelerator:
# Euler accelerator, from SICP def firstn(g, n): for i in range(n): yield g.next() def pi_series(): sum = 0 i = 1.0; j = 1 while(1): sum = sum + j/i yield 4*sum i = i + 2; j = j * -1 def euler_accelerator(g): s0 = g.next() # Sn-1 s1 = g.next() # Sn s2 = g.next() # Sn+1 while 1: yield s2 - ((s2 - s1)**2)/(s0 - 2*s1 + s2) s0, s1, s2 = s1, s2, g.next()
So let's run their example:
>>> list(firstn(euler_accelerator(pi_series()), 8)) 3.166666666666667, 3.1333333333333337, 3.1452380952380956, 3.1396825396825401, 3.1427128427128435, 3.1408813408813416, 3.1420718170718178, 3.1412548236077655
So it occurred to me, what if you accelerated the accelerated series? I expected that you wouldn't get any additional benefit, but you do. I created a Kleene star expansion: def kleenex(f, x): ff = x while 1: yield ff ff = f(ff)
and applied it to the accelerator:
>>> list(x.next() for x in firstn(kleenex(euler_accelerator, pi_series()),8)) 4.0, 3.1333333333333337, 3.1416433239962656, 3.1415924384368328, 3.1415926542772872, 3.1415926535880514, 3.1415926535897984, 3.1415926535897949
compare with a single step of the accelerator: You can see that it converges quite fast, and if python had handy bigfloats I'd have a look.
Perhaps someone can tell me the convergence rate?
Ok, I found python-gmpy, and compared against the built in pi() function - turns out that the converges looks to be linear, gaining about 3 digits per iteration. Oh well, intriguing anyway.