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

## No comments:

## Post a Comment