Computing π to “infinite” binary precision in C#

Question

So far it looks like Fabrice Bellard's base 2 equation is the way to go

Ironically this will require a BigReal type; do we have this for .Net? .Net 4.0 has BigInteger.

Anyone have a Haskell version?

Answer 1

Wikipedia details a lot of ways to get numerical approximations of pi here. They also give some sample pseudo-code

Edit : If you're interested in this kind of mathematical problems without having any related real-world problem to solve (which is definitely a good attitude to have, IMHO), you could visit the Euler Project page

Answer 2

There exists such possibility to process big rational numbers in DLR-based dynamic languages (e.g. IronPython). Or you can use any portable C/C++ implementation of big real numbers through P/Invoke.

Answer 3

Since you're asking for a Haskell version, here is a paper by Jerzy Karczmarczuk, called "The Most Unreliable Technique in the World to compute π":

This paper is an atypical exercice in lazy functional coding, written for fun and instruction. It can be read and understood by anybody who understands the programming language Haskell. We show how to implement the Bailey-Borwein-Ploue formula for π in a co-recursive, incremental way which produces the digits 3, 1, 4, 1, 5, 9. . . until the memory exhaustion. This is not a way to proceed if somebody needs many digits! Our coding strategy is perverse and dangerous, and it provably breaks down. It is based on the arithmetics over the domain of infinite sequences of digits representing proper fractions expanded in an integer base. We show how to manipulate: add, multiply by an integer, etc. such sequences from the left to the right ad infinitum, which obviously cannot work in all cases because of ambiguities. Some deep philosophical consequences are discussed in the conclusions.

It doesn't really solve the problem in an efficient or very practical way, but is entertaining and shows some of the problems with lazy infinite precision arithmetic.

Then there's also this paper by Jeremy Gibbons.

Answer 4

By far my favorite Haskell spigot for pi comes from Jeremy Gibbons:

pi = g(1,0,1,1,3,3) where
    g(q,r,t,k,n,l) = 
        if 4*q+r-t<n*t
        then n : g(10*q,10*(r-n*t),t,k,div(10*(3*q+r))t-10*n,l)
        else g(q*k,(2*q+r)*l,t*l,k+1,div(q*(7*k+2)+r*l)(t*l),l+2)

The mathematical background that justifies that implementation can be found in:

A Spigot Algorithm for the Digits of Pi