Almost PI

While doing some light reading on the “interweb” I came across the following interesting interview question:

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.

What I think is great about this interview question is that is not about maths, but about how to translate the given mathematical formula into code.

I came up with 2 Haskell solutions for the problem, the first a very quick and naive solution, and the second solution is a bit clearer and performs better.

The first solution is as follows:

pi = 4.0 * (r 1.0 3 50000000 0)
 
r startVal denominator numOfPlacesMax currentNumOfPlaces =
   if currentNumOfPlaces > numOfPlacesMax
      then startVal
      else startVal - (1 / denominator) + (r (1 / (denominator + 2)) (denominator + 4) numOfPlacesMax (currentNumOfPlaces + 1))

After trying to make the code clearer, I refactored it into the following solution:

pi = 4.0 * (r 1 False 10000000 0 0)
 
r !denominator doSubtract numOfPlacesMax !currentNumOfPlaces !acc
   | currentNumOfPlaces > numOfPlacesMax = acc
   | otherwise =  if doSubtract
                     then r nextDenominator (not doSubtract) numOfPlacesMax nextNumOfPlaces (acc - (1 / denominator))
                     else r nextDenominator (not doSubtract) numOfPlacesMax nextNumOfPlaces (acc + (1 / denominator))
   where
      nextDenominator = denominator + 2
      nextNumOfPlaces = currentNumOfPlaces + 1

The first solution was consuming about 2GB of memory, then exiting with an “out of memory” exception. This is because of laziness and not using tail recursion. In the second version of the solution, I changed the code to be properly tail recursive, but that change alone is not enough. Because of laziness, I had to make some of the parameters of the r function strict by using BangPatterns. Now the second solution runs in constant space.