Friday, August 31, 2012

Calculating Pi to 5 Digits

Yesterday I was reading 20 controversial programming opinions which has some interesting debates going on in it.   However I was drawn to the following programming question that one responder likes to ask potential new hires in job interviews:

Given that Pi can be estimated using the function 4 * (1 – 1/3 + 1/5 – 1/7 + …) with more terms giving greater accuracy, write a function that calculates Pi to an accuracy of 5 decimal places.

The first part of this is easy, depending on the language you use.  In Java it's something simple like:


float Pi=(float)1.0;
int mult=-1;
for (int dem=3;dem <1000 dem="dem+2){<br">    float Add=(float)(1.0/(float)dem);
    Pi=Pi+(float)(mult*Add);
    System.out.println("Dem "+dem+"  "+Add+ "  Pi "+4.0*Pi);
    mult=-1*mult;
}



The problem is getting the answer to 5 digits accuracy. How can we know it's accurate unless we know the value of Pi. My solution (which does have it's problems is to iterate until the calculated value of Pi doesn't change to the accuracy we require. In the examples below I've used string formatting to track the old value and the new value until they are the same. Both versions give the same answer 3.14159

In Java

import java.text.*;
public class Pi {
   public static void main(String[] args) {
      double Pi=(double)1.0;
      //http://www.javaprogrammingforums.com/java-programming-tutorials/297-how-format-double-value-2-decimal-places.html
      DecimalFormat df = new DecimalFormat("#.#####");
      String oldPi;
      String newPi;
      long dem=3;
      oldPi =df.format((double)4.0);
      newPi =df.format(Pi);
      int mult=-1;
      while (oldPi.compareTo(newPi)!=0){
        oldPi=df.format((double)4.0*Pi);
        double Add=(double)(1.0/(double)dem);
        Pi=Pi+(double)(mult*Add);
        newPi=df.format((double)4.0*Pi);
        System.out.println("Dem "+dem+"  "+Add+ "  Pi "+df.format((double)4.0*Pi)+ "  Pi "+4.0*Pi+" : "+oldPi+" : "+newPi);
      mult=-1*mult;
     dem+=2;
     }
 }
}

And in C
#include
#include
main(){
   double Pi=(double)1.0;
   char oldPi[100];
   char newPi[100];
   long dem=3;
   sprintf(oldPi,"%.5f",(double)4.0);
   sprintf(newPi,"%.5f",(double)Pi);
   int mult=-1;
   while (strcmp(oldPi,newPi)!=0){
      sprintf(oldPi,"%.5f",(double)4.0*Pi);
      double Add=(double)(1.0/(double)dem);
      Pi=Pi+(double)(mult*Add);
      sprintf(newPi,"%.5f",(double)4.0*Pi);
      printf(" %ld Pi %.5f %s %s \n",dem,4.0*Pi,oldPi,newPi);
      mult=-1*mult;
      dem+=2;
   }
}
The problem with both these versions is they don't work if you try and increase the accuracy.  If you want 6 decimal places then the value doesn't settle down, in fact it oscillates between two values and never stays the same.

So two questions:


  1. What does the code look like in other languages (particularly something like Erlang)
  2. How to deal with the oscillation problem ?

1 comment:

  1. A not so elegant Erlang solution.

    -module (pi).
    -export ([pi/0]).

    pi() -> 4 * pi(0,1,1).
    pi(T,M,D) ->
    A = 1 / D,
    if A > 0.00001
    -> pi(T+(M*A), M*-1, D+2);
    true -> T
    end.

    But the solution is a bad one, lots of iterations so its very slow and the 5 decimal places clause is only met thanks to the dodgy 'f A > 0.00001 ' comparison and the function looses accuracy beyond five decimal places.

    ReplyDelete