PI: 3.1415926535...

Calculate Pi by Averaging

Calculate Pi by Averaging: First use the following formula, Gregory's series for pi:

Consider the partial sums of this series, defined by the following:

Here are the first few partial sums. They are getting ever closer to pi/4, but alternately larger and smaller than pi/4.

Since these values are flipping back and forth around pi/4, it seems as if the results would be much more accurate if we took the average of each pair of entries. Starting with s[0] and s[1], take the average of adjacent values, and overwrite the lower value with the new average. (This overwritten value doesn't participate in the later calculations.)

Notice that because of the averaging, there is one fewer value in the list, so that s[9] is ignored afterward.

These values are about a factor of 10 closer to pi/4, and they also flip back and forth around pi/4, so we could average adjacent values again, and yet again.

The tables below show this averaging process taken a number of times. In the specific tables below, everything is multiplied by 4, so that the series is converging to pi.

All values in the tables were stored as doubles in the program, but were truncated for display. These calculations wouldn't work at all without the full precition of a double.

The column labeled "0" below gives the partial sums s[15] through s[31].

The column labeled "1" gives averages of adjacent elements from the "0" column. When entries for index i and i+1 are averaged, the result is stored in index i. At the end there is one fewer entry, and the resulting averages are stored under indexes 15 to 30.

Then column "2" gives averages from column "1", and so on. Each time the averages are taken there is one fewer element, so that when we start with 17 elements, and after we average 16 times, there is only one element left. In this case, this final average gives pi accurate to 16 significant digits.

This seems surprising to me. Using just the partial sums s[15] through s[31] and using repeated averaging gives 16 significant digits of pi.

The program below was used to generate the data above. The calculations below repeatedly run through the given values, averaging adjacent pairs (giving one fewer value when done). The program starts with N terms of the series, and then does A averages, ending with a sequence of N - A values. The first program below gets 16 digits of accuracy using only 32 terms of the original series, plus 16 steps of averaging.

Pi by averaging Output of a run
// PiAve: compute pi using inaccurate formula,
//   followed by repeated averaging.
import java.text.DecimalFormat;
public class PiAve {
   public static DecimalFormat d16 = new
      DecimalFormat("0.0000000000000000");

   public static String diff(double r) {
      double t = (Math.PI) - r;
      if (t < 0) return d16.format(t);
      else return " " + d16.format(t);
   }

   public static void main(String[] args) {
      // number of terms in the initial series
      int N = Integer.parseInt(args[0]);
      // number of times to average
      int A = Integer.parseInt(args[1]);
      if (A > N - 1) System.out.println("N too small");
      double sum = 0.0;  // cumulative sum
      double term;       // each term, without sign
      double sign = 1.0; // sign of each term
      double[] sums = new double[N]; // averaged values

      // calculate N terms of inaccurate series for pi
      for (int k = 0; k < N; k++) {
         term = 1.0/(2.0*k + 1.0);
         sum = sum + sign*term;
         sign = -sign;
         sums[k] = 4*sum;
      }

      // average adjacent pairs, processing A times
      int M = N;
      for (int dummy = 0; dummy < A; dummy++) {
         for (int j = 0; j < M - 1; j++)
            sums[j] = (sums[j] + sums[j + 1])/2.0;
         M--;
      }

      // print final N - A values
      for (int k = 0; k < N - A; k++)
         System.out.println(k + "  " + sums[k] +
            "   " + diff(sums[k]));
   }
}

% java PiAve 32 16
 k        sums[k]              pi - sums[k]

 0  3.1415930039365283   -0.0000003503467352
 1  3.1415926263422733    0.0000000272475198
 2  3.1415926569580237   -0.0000000033682306
 3  3.1415926530329275    0.0000000005568657
 4  3.141592653703066    -0.0000000001132729
 5  3.141592653562805     0.0000000000269882
 6  3.141592653597091    -0.0000000000072977
 7  3.1415926535876073    0.0000000000021858
 8  3.14159265359051     -0.0000000000007168
 9  3.141592653589542     0.0000000000002509
10  3.141592653589889    -0.0000000000000959
11  3.1415926535897567    0.0000000000000364
12  3.1415926535898104   -0.0000000000000173
13  3.141592653589788     0.0000000000000053
14  3.1415926535897976   -0.0000000000000044
15  3.141592653589793     0.0000000000000000

% java PiAve 32 31
 k        sums[k]              pi - sums[k]

 0  3.141592653594113    -0.0000000000043201

% java PiAve 45 44
 k        sums[k]              pi - sums[k]

 0  3.1415926535897953   -0.0000000000000022

// simple version of the program
public class Pi {
   public static void main(String[] args) {
      double[] s = new double[32];
      s[0] = 1;
      int M = 32;
      for (int k = 1; k < 32; k++)
         s[k] = s[k-1] + (-k%2*2+1)/(2*k + 1.0);
      for (int i = 0; i < 16; i++) {
         for (int j = 0; j < M - 1; j++)
            s[j] = (s[j] + s[j + 1])/2;
         M--;
      }
      System.out.println(s[15]*4);
   }
}
3.141592653589793

Starting with a more accurate series for pi: Now suppose one starts with values given by the third formula on the page with better formulas. Then apply the averaging. In this case one starts with far more accurage values, but you still need N = 28 and A = 14 to get 15 significant digits for pi. Here are the last two terms in the initial calculation for pi (so we are starting with very much more accurate data):

Here is the corresponding list of averaged values:

In this case, even though the initial data is so very much better, it still took nearly as many averages to get 15 significant digits of pi.