A Ramanujan series for calculating pi

Ramanujan discovered the following remarkable formula for computing π:

frac{1}{pi} = sum_{n=0}^infty {2n choose n}^3 frac{42n + 5}{2^{12n+4}}

This is not the most efficient series for computing π. My next post will give a more efficient method, also based on work of Ramanujan. But the series above is interesting for reasons explained below.

Notice that the denominator of each term in the sum above is a power of 2. This means the partial sums of the series can be represented exactly in binary. We’ll see that each term in the series adds six bits precision to the sum once we’ve added enough terms.

To understand how to use this series, we need to estimate the binomial coefficient term. Stirling’s approximation shows that

{2n choose n} sim frac{2^{2n}}{sqrt{pi n}}

This tells us that the nth term in the series is a rational number with numerator something like 2^6n and denominator 2^(12n+4). Therefore the nth term is on the order of 2^(-6n-4) and so the series converges quickly. The first three terms illustrates this:

frac{1}{pi} = frac{5}{16} + frac{376}{65536} + frac{19224}{268435456} + cdots

The error in summing up a finite number of terms is approximately the first term in the remainder, so just a few terms leads to an accurate approximation for 1/π and hence an accurate approximation for π.

To be a little more precise, when we sum the series from n = 0 to n = N, the error in approximating 1/π is on the order of the next term, 2^(-6N-10). Said another way, summing up to the Nth term computes 1/π to 6N + 10 bits. For example, suppose we wanted to compute 1/π to 200 decimal places. That’s about 664 bits, and so 108 terms of the series should be enough.

We glossed over a detail above. We said that the nth term is on the order of 2^(-6n-4). That’s true for sufficiently large n. In fact, we can say that the nth term is less than 2^(-6n-4), but only for large enough n. How large? We need the denominator term (π n)^3/2 to be larger than the numerator term 42n + 5. This happens if n is at least as large as 58.

One advantage to using this series to compute π is that you could compute later blocks of bits without having to compute the earlier blocks, provided you’re interested in the bits beyond those contributed by 58th term in the series.

Reference

Related post:

Two useful asymptotic series

Tagged with: ,
Posted in Math
0 comments on “A Ramanujan series for calculating pi
5 Pings/Trackbacks for "A Ramanujan series for calculating pi"
  1. [...] about everyone’s favouburite irrational number.  Carnival regular, John D. Cook, brings us A Ramanujan series for calculating pi, 360 has The Difference and Qiaochu Yuan counters with Pi is still wrong.  Finally, madkane [...]

  2. [...] e.g., a compiler might spot programs that calculate pi and always generate code that uses the most rapidly converging method known. This is a very different approach to the traditional methods based on using (mostly) execution [...]

  3. [...] Algorithm for world record pi calculations Ramanujan series for pi [...]

  4. [...] Related post: A Ramanujan series for calculating pi [...]

  5. [...] posts: A Ramanujan series for calculating pi Ramanujan’s factorial [...]