On Thu, 13 Jul 2006, Jason Holt wrote:
n n 4 ___ ___ --- \ \ pi ~ n*n * / / 1 if sqrt(x*x+y*y) < n --- --- x=0 y=0
I just noticed that this approach is sort of an intuitive way of looking at the discrete form of the integral from 0..1 of sqrt(1-x^2) dx. The discrete version could also be computed as: n 4 ___ --- * \ pi ~ n*n / sqrt(n*n-x*x) --- x=0 Regarding the subdivision approach to avoid having to choose n at the outset, perhaps we could use a function (call it subdiv()) that, given n, outputs the nth element of the breadth-first traversal of this tree: 0.5 0.25 0.75 0.125 0.375 0.625 0.875 ... Huh. That's the sizes in my SAE socket wrench set: 1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8 [1/16, 3/16, 5/16, 7/16, 9/16, 11/16, 13/16, 15/16] ... So, it's something like... subdiv(n): (1+2*n) mod 2^int(1+log2(n)) -------------------------- 2^int(1+log2(n)) And we could call order(n)=2^int(1+log2(n)). This sort of function must have been invented before; anybody know what it's called? Our series for pi then becomes: n ___ \ order(n)*pi ~ 4* / sqrt(1-subdiv(i)^2) --- i=0 So that's closer, anyway: run as long as you want, then divide the result by order(n) at the end to get your approximation of pi. Of course, it works much better if n=2^k-1 for some k. -J