## How to

When solving these problems, learning by doing is much better than learning by reading. I encourage to you read only as far in the solution as you need, then trying to solve the problem. If you get stuck, try reading a little further. And of course, let me know if you find a better solution!

## Monday, March 19, 2012

### 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 */