I found a startlingly simple and pretty efficient algorithm to approximate π today, on a web demo for Tabby. It was so interesting that I tried it myself. Here's the script:
n := 1000000
k := 1
x := 0
with std.loop(n) fn {
x <- x + 1 / (k * k)
k <- k + 2
}
fmt.printf('Almost π: {{0}}\t(at n = {{1}})', math.sqrt(x * 8), n)
Looks deceptively simple, right? Just a few additions and multiplications. For various values of n
, here's the output:
Almost π: 2.8284271247461903 (at n = 1)
Almost π: 3.1096254579886478 (at n = 10)
Almost π: 3.1384079670670912 (at n = 100)
Almost π: 3.14127432760274 (at n = 1000)
Almost π: 3.1415608224399487 (at n = 10000)
Almost π: 3.141589470489344 (at n = 100000)
Almost π: 3.1415923352799697 (at n = 1000000)
Almost π: 3.1415926217577352 (at n = 10000000)
It looks like the formula is a variant of a Taylor series-like approximation of π, but written iteratively/imperatively rather than as a sum per se, and it comes out really clean. I like it.