Pi. Yum.

Problem:  Write a function that calculates π.

double calculatePi(void) {
...
}

Solution:  The core of the problem is straight forward -- output a numerical value for π . And yes, you can't simply return a constant like many languages allow (that would be too easy, though it's worth mentioning this to the interviewer). Also, as π is irrational, we can only approximate it with a numerical value. 


Instead, the interviewer will explain a way to do this using a Gregory-Leibniz series.  This is a mathematical sum that calculates pi at infinity.  The proof behind this is quite complicated (and truthfully, I don't understand it, but it works).  This series is shown below which sums up to pi.

Also, this is a very slow converging function.  At k=150, we only have two decimal points of precision, but well, we can go much further than this!


So, coding this up should be fairly straight-forward.  If we choose a big k (say 20,000), we can get a nice value for π.


Let's also put the constraint on that we can't use a power.  This is also not too bad, as the (-1)^k only determines parity, so we can use an if statement letting us know that if k is even, we should pe positive, else negative.


Putting this all together, we can code it up:



double calculatePi(void) {


    int i;
    double pi = 0;


    for (i = 0; i < 20,000; i++){
        /* determine parity */
        if (i%2 == 0)  /* even and positive */
            pi += 4 / (2*i + 1);
        else
            pi -= 4 / (2*i +1);
    }
    return pi;
}


It's worth doing a few examples here (0, 1, 2) which yield (4/1) - (4/3) + (4/5) . . . 


Pretty neat.  Try this, and you'll notice that you can very nice value for pi.


Also, the run-time of this function is O(20,000), which is constant, and actually quite fast as the multiply by 2 is a very fast function.


There are some optimizations possible, but this is good.  


This was written on pi day (3/14).  So, happy pi day!


/* Please let me know if you find errors or alternate solutions.  Thank you.  Noah */