PI Calculator, Interview Challenge

Question

Greg Beech says here that he asks C# candidates to produce a formula that calculates PI Given that Pi can be estimated using the function \$4 * (1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \dots)\$.

I'm far from C# interview ready, but I like the challenge. Here is my attempt at the formula. Let me know if there is a better way to do it.

using System;

class MainApp 
{
    static void Main () 
    {
        double number = 0;
        double pi;
        int i = 1;

        do 
        {
            if ((i/2) % 2 == 0)
            {
                number += (double)(1) / i;
            }
            else
            {
                number -= (double)(1) / i;
            }
            pi = 4 * number;
            i += 2;
        } while (Math.Round(pi,5) != 3.14159);

        Console.Clear();
        Console.WriteLine("Pi can be found using the formula 4 * (1 - 1/3 + 1/5 - 1/7 + ...) with {0} iterations.\n" +
        "At this point 4 is multiplied by: {1} to get {2}\n" +
        "This Rounds up to: {3}",i,number,pi,Math.Round(pi,5));
        Console.ReadKey();
    }
}

Answer 1

In an interview it usually doesn't matter if you actually solve the problem. What is most important is the way you (try to) solve it. If they don't tell you it should be the possibly fastest solution ever you should not optimize it prematurely but instead show that you know how to write SOLID code like encapsulate propertly, make the code testable etc. show that you know the techniques.

---

Here you could split the logic up into multiple methods for example you could have one generating the alternating sequence [1, -3, 5, -7, 9, -11, ...] that you can validate with a test:

public static IEnumerable<int> AlternatingSequence()
{
    var i = 1;
    yield return i;
    var b = false;
    while (true) yield return ((b = !b) ? -1 : 1) * (i = i + 2);
}

then you can work on the PI itself and use it for the actual calculation which is then as simple as a LINQ expression:

public static double EstimatePI(int sumLength) 
{
    return (4 * AlternatingSequence().Take(sumLength).Sum(x => 1.0 / x));
}

var pi = EstimatePI(500_000).Dump(); // 3,14159065358969

---

There's all kind of stuff you can show you are familiar with in this simple task like DI or strategy pattern:

public static double EstimatePI(int sumLength, IEnumerable<int> sequenceGenerator) 
{
    return (4 * sequenceGenerator.Take(sumLength).Sum(x => 1.0 / x));
}

var pi = EstimatePI(500_000, AlternatingSequence);

or even more advanced DI and encapsulation

class PiCalculator
{ 
    private readonly IEnumerable<int> _sequenceGenerator;

    public PiCalculator(IEnumerable<int> sequenceGenerator)
    {
        _sequenceGenerator = sequenceGenerator;
    }

    public double EstimatePi(int sumLength)
    {
        ...
    }
}

or you can add an interface to show you know what abstraction means:

interface IPiCalculator
{ 
    double EstimatePi(int sumLength);
}

---

Is this an overkill? It might be but it shows me that you are able to write modular and testable code. Writing short code is a good thing too but if you write only five lines inside a Main in a job interview, you'll go home without any prospects of getting the job. Again, in an inteview you should sell your coding skills and not show how smart you are in solving something with a fewest possible lines of code that no one can verify.

Answer 2

I'm going to give an alternative approach to tchbot's answer

There are places where SOLID prinicpals are required.

I don't see this as one of them. Here, we have a simple "Are you capable of writing a loop" question - about the same level as the Fizz Buzz test.

Really, the function is described in one line, and when applying mathematical formulas, I think it's OK to write terse code.

using namespace System;

public class Program
{
    public static void Main()
    {
        double t = 0.0;
        for(int i = 1, m = 1, c=0; c < 1000000; i+=2,m*=-1,++c) {
            t += (1.0/i)*m; 
        }
        Console.WriteLine("pi={0}", 4*t);
    }
}

---

Note one principal I'm applying here: The length of a variable name should be proportional to its scope. ( Bob C. Martin. )

I could name the variable m something descriptive like togglingNegativeMultiplier, but as it's entire lifetime is over two lines of code a reader would be able to see what it is doing.

---

Incidentally, I wrote a performance test to compare the performance of the Linq solution against the performance of a simple loop. https://dotnetfiddle.net/M3e649

When calculating a million iterations:

• Time using Linq: 89 milliseconds
• Time using Loop: 10 milliseconds

Granted, there are situations where a nine-fold difference in performance matters, and some where it doesn't. But here we're writing number-crunching code, and in these areas performance tends to be important.

Answer 3

Flavio's answer addresses a part of something that matters greatly for this kind of problem: rounding errors will kill you. If you look at the expression:

$$1-\frac13+\frac15-\frac17+...$$

This is the same as

$$\frac{3-1}{1\times3} + \frac{7-5}{5\times 7} + ...$$

It is easy to see that the nth term in this sequence is

$$\frac{2}{(4\times n-3)(4\times n-1)}$$

Now if you need a certain number of digits of precision, you first compute the number of terms you need - now that we have the terms in pairs, they are all contributing a positive amount. This converges extremely slowly... you can estimate this approximately by noticing that

$$\sum_n^\infty \frac{1}{x^2}\approx\int_{n-\frac12}^\infty \frac{dx}{x^2}=\frac{1}{n-\frac12}$$

So if you need the answer to be right to better than 5 digits, you need to sum at least 100,000 elements - and as the required accuracy goes up, you need to carry a LOT more significant figures. Alternatively, the smart person adds the estimated error term at the end - and gets awfully close to the right answer with not a lot of calculation. See below.

Now you may know that a single precision floating point number contains about 23 bits of precision - about 7 digits. This will really mess up your attempt to get even 4 digits of precision if you don't work backwards, starting with the smallest numbers (which means you can carry digits beyond the 7th decimal, until the sum gets bigger).

So the steps you take:

1. Formulate the expression to be monotonic
2. Determine the rate of convergence
3. Find an expression for the number of terms you need to reach a certain precision
4. Execute the calculations in an order that maximizes the accuracy

Only if all the above fail should you resort to brute force (using double precision and above, keeping going until you are sure your answer is no longer changing).

Of course, as others pointed out, for a "pure software" job, a lot of issues of properly structured code come into play - but if the task is one of numerical analysis, not just dropping a few lines of code, then the above considerations really matter.

For example, evaluating the expression for the first 100000 terms in the "forward" direction, using single precision (which emphasizes the problem), you get

pi=3.14138389

Doing it in the "backward" direction (starting with the smallest term) you get

pi=3.14158773

The difference: -0.00020385; they are different from the 5th significant figure onwards even though floating point precision "should be better than that" - but rounding errors compound! You can see that the "backward" method is getting close to 3.14159, while the "forward" method will never get there.

Here is some C code I wrote to demonstrate these points - note that the actual loop that does the piece you asked about takes just four lines. I realize you are looking for comments on your C# code, but the principles I outlined transcend the language you use.

// code that computes the value of pi by evaluating the first few terms
// of the infinite series
// pi = 4*(1/1-1/3+1/5-1/7+...)
//
// three important points:
// rounding error is reduced by evaluating starting with the small values
// rounding error is further reduced by pairing the values
// finally, an analytical estimate of the residual error is used to make the
// result significantly more accurate

#include <stdio.h>
#include <math.h>

int main(void) {
    int N=100;             // number of values to include
    double PI=2*acos(0.0); // to confirm the accuracy later
    float forwardSum, backwardSum, residualSum;
    forwardSum=0;

    for(int ii=1; ii<=N; ii++) {
        forwardSum+=8./((4*ii-3.)*(4*ii-1.));
    }

    // ***** this is the code that does the heavy lifting *****
    backwardSum=0;
    for(int ii=N; ii>=1; ii--) {
        backwardSum+=8./((4*ii-3.)*(4*ii-1.));
    }
    // backwardSum now contains our estimate of pi

    // analytically we know the error should be
    residualSum = 0.5/N;

    printf("Starting with big terms, after %d pairs pi=%.8f\n", N, forwardSum);
    printf("Starting with small terms, after %d pairs pi=%.8f\n", N, backwardSum);
    printf("difference between directions: %.8f\n", backwardSum - forwardSum);
    printf("estimated residual sum = %e\n", residualSum);
    printf("updated estimate of pi: %.8f\n", backwardSum + residualSum);
    printf("after correction, error in pi is %e\n", PI-(backwardSum +residualSum));

    return 0;
}

The output of this code is:

Starting with big terms, after 100 pairs pi=3.13659286
Starting with small terms, after 100 pairs pi=3.13659263
difference between directions: -0.00000024
estimated residual sum = 5.000000e-03
updated estimate of pi: 3.14159274
after correction, error in pi is -8.742278e-08

Using single precision, the error is reduced to about 1 part in \$ 10^7 \$, just as we expect as the limit of accuracy. Incidentally, the error correction term is so good that you get the "right" answer with just 100 pairs of terms.

While brute force is sometimes all you need, a little analysis is not a bad trick to keep up your sleeve.

Answer 4

There is clearly no 'best way' to do this. From a 'Numerical Analysis' approach, you should never sum that way a series with alternating-sign terms: loss of accuracy and slow convergence speed can be expected. Use simple arithmetic to sum the terms in pairs, and then iterate by two units at a time. If you do this, you will gain a lot both in accuracy and in convergence speed. So the expression I would add is :

1 / (n*n + n)

Answer 5

Observations and Suggestions

• Operate on pi directly.

• You can eliminate the pi = 4 * number;.

• You are using more operations than are necessary.

• I prefer decimal over double here for precision.
  Decimal is slower and at 6 digits of precision I don't think double would get you in trouble. More precision double could introduce errors which are not self correcting.

• Do 2 iterations in one overall iteration of the loop and eliminate the modulo operator %

• Eliminate the casting of int to decimal

• The average of + and - is going to be the best current estimate

• The answer will between + and - if no rounding error as been introduced

  public static decimal PI3()
  {   
      decimal pi = 4m, iteration = 3m;
      do
      {  
           pi -= 4m / iteration;
           iteration += 2m;
           pi += 4m / iteration;
           iteration += 2m;
           //Debug.WriteLine(pi);
      } while (Decimal.Round(pi, 5)  !=  3.14159m);
      return Decimal.Round(pi, 5);
  }
  

In reply to OP's question in comments:

Test this versus your solution or other proposed solutions:

public static decimal PI4()
{
    decimal pi = 4m, iteration = 3m, piAvg;
    do
    {   
        pi = Decimal.Subtract(pi, Decimal.Divide(4m, iteration));
        piAvg = pi;
        iteration = decimal.Add(iteration, 2m);
        pi = Decimal.Add(pi, Decimal.Divide(4m, iteration));
        piAvg = Decimal.Divide(Decimal.Add(pi, piAvg), 2m);
        iteration = decimal.Add(iteration, 2m);
        if(decimal.Add(iteration, 1m) % 100000m == 0) {
            Debug.WriteLine(piAvg);
        }
    } while (Decimal.Round(piAvg, 10) != 3.1415926536m);      //3.1415926535897932384626433833
    return Decimal.Round(piAvg, 10);
}

Answer 6

I think what you came up is a good start. I've edited your code to improve and make more concise. It's not the best code, but I hope it helps you.

public static void Main()
{
    double number = 0;
    double pi;
    int i = 1;
    bool sign = true; // we use a boolean to sum or subtract

    do 
    {
        double div = (double)(1.0 / i);  // calculate the ratio
        number += (sign ? div : -div); // sum or subtract depending on sign being true or false

        pi = 4 * number;
        i += 2;
        sign = !sign;  // toggle sign

    } while ((Math.Round(pi,5) != 3.14159));

    Console.WriteLine("Pi can be found using the formula 4 * (1 - 1/3 + 1/5 - 1/7 + ...) with {0} iterations.\n" +
    "At this point 4 is multiplied by: {1} to get {2}\n" +
    "This Rounds up to: {3}",(i-1)/2,number,pi,Math.Round(pi,5)); // to know the iteration we use i-1 / 2

}

Answer 7

What I think is wrong with the code - it's hard to understand

Here's what I think all good code should do:

1. First and foremost it must be understandable. Most of the code you write will be read many more times than edited. There are no comments - which is not necessarily bad if the code is self-explanatory. that's what we should aim for.
2. It must be easy to maintain
3. and if required must be easy to make changes
4. It must actually work: where are your tests!?!

Is it worth writing OOP code or should we go quick and dirty?

Writing pure OOP code might take a little bit longer (but it will probably be more robust). Is it worth it? It might not be. but since this is a hypothetical, let's go down the OOP way:

Your code does not make use of "objects" which send "messages" to each other. (Please google that if you don't know what it means). You've got conditionals in your code which also supply behaviour. OOP is meant to get you to have objects supply the behaviour and to separate conditionals from behaviour as much as possible.

Here is the Summary Code:

public class Pie
{
    /// <summary>
    /// Estimates pi based on the number of fractions we desire it to estimate by.
    /// The way I view it: you basically have 4 * (element0 + element1 + element2 etc.)
    /// where element0, element1 etc are instances of the Element class.        
    /// </summary>
    /// <param name="elementCount"></param>
    /// <returns></returns>
    public double Estimate(int elementCount)
    {
        ElementCollection ec = new ElementCollection(elementCount);
        return 4 * ec.AddAllElements();
    }
}

Here is the Full Code:

namespace BKTest
{
    public class Pie
    {
        /// <summary>
        /// Estimates pi based on the number of fractions we desire it to estimate by.
        /// The way I view it: you basically have 4 * (element0 + element1 + element2 etc.)
        /// where element0, element1 etc are instances of the Element class.
        /// I use a factory method to instantiate the element types and use polymorphism to differentiate
        /// between the two different types of elements that are currently out there: Element0 and the others: Element1, Element2 etc .
        /// Element zero is different because you can't divide by zero! (This probably won't make any sense)
        /// Till you attempt the problem yourself.
        ///
        /// </summary>
        /// <param name="elementCount"></param>
        /// <returns></returns>
        public double Estimate(int elementCount)
        {
            ElementCollection ec = new ElementCollection(elementCount);
            return 4 * ec.AddAllElements();
        }
    }

    public class ElementCollection
    {
        private int elementCount;

        public ElementCollection(int elementCount)
        {
            this.elementCount = elementCount;
        }

        public double AddAllElements()
        {
            double result = 0.0;
            for (int i = 0; i < elementCount + 1; i++)
            {
                ElementN element = ElementFactory(i);
                result += element.Value();
            }

            return result;
        }

        public ElementN ElementFactory(int i)
        {
            if (i == 0)
            {
                return new Element0(i);
            }
            else
            {
                bool even = (i % 2 == 0);

                if (even)
                {
                    return new ElementEven(i);
                }
                else
                {
                    return new ElementOdd(i);
                }
            }
        }

        public class Element0 : ElementN
        {
            public Element0(int elementCount)
                : base(elementCount)
            {
            }

            public override int Sign()
            {
                return 1;
            }

            public override double PosivitveValue()
            {
                return 1.0;
            }
        }

        public class ElementEven : ElementN
        {
            public ElementEven(int elementCount)
                : base(elementCount)
            {
            }

            public override int Sign()
            {
                return 1;
            }
        }

        public class ElementOdd : ElementN
        {
            public ElementOdd(int elementCount)
                : base(elementCount)
            {
            }

            public override int Sign()
            {
                return -1;
            }
        }

        public abstract class ElementN
        {
            private int elementCount;

            public ElementN(int elementCount)
            {
                this.elementCount = elementCount;
            }

            virtual public double Value()
            {
                return Sign() * PosivitveValue();
            }

            virtual public double PosivitveValue()
            {
                return ((1.0) / (2.0 * elementCount + 1));
            }

            /// <summary>
            /// Either the sign is positive or negative
            /// We could probably put this into its own class
            /// and have a factory method but we'll keep it like this for the moment
            /// till one day change requires us to change it. After all, a sign can only
            /// either be positive or negative. (apparently you can also multiple by the
            /// square root of (-1) but that's another matter.
            /// </summary>
            /// <returns></returns>
            abstract public int Sign();
        }
    }
}

Here are the Tests:

using NUnit.Framework;

namespace BKTest
{
    [TestFixture]
    internal class PieTest
    {
        [Test]
        [TestCase(0, 4)]
        [TestCase(1, 4 * (1 - 1.00 / 3.0))]
        [TestCase(2, 4 * (1 - 1.00 / 3.0 + 1 / 5.0))]
        [TestCase(3, 4 * (1 - 1.00 / 3.0 + 1 / 5.0 - 1 / 7.0))]
        [TestCase(4, 4 * (1 - 1.00 / 3.0 + 1 / 5.0 - 1 / 7.0 + 1 / 9.0))]
        public void Estimate_1Parameter_expect_fourMinusOneThird(int input, double output)
        {
            // set up
            double result = new Pie().Estimate(input);
            Assert.AreEqual(output, result);
        }
    }
}

(Note - originally the code was put on Gist)

Points about the code:

• API is simpler to read and understand. The main logic is hidden away.
• Easily amenable to change. What if the boss walks in and says he/she wants every 4th fraction to be: 1/e - will your code easily be able to handle that? I'd simply add a new ElementN sub-class called ElementE and add a conditional to my factory method and the changes would be made instantly.
• Compare my code with yours: I've put the conditionals in a factory - which is where they should be. everything is very neatly separated. I make use of an abstract class and then supply the various implementations of that abstract class. this is what good OOP code should do. And OOP is good because it is easily amenable to change, mainly because classes and methods are not tightly coupled together (please google it if you don't know what that means). As I see it, there are only three different types of fractions: the first one (which is one) then the second which is a positive fraction and the third, which is negative. and that's it! so I subclass everything into three class which supply the relevant behaviour. and I only need 1-2 conditionals to make the whole thing work. This is an OOP way of handling it. ask a functional programmer and he or she might do it a different way but then again, it's harder to change.

Answer 8

I think your code doesn't look straightforward and is a little confusing. You use int i and then implicitly cast i/2 to int to check if it is even.

The casting to double also seems weird, it would look better if it was 1.0 / i or 1d / i.

Also, you don't need to multiply by 4 every iteration, since multiplication distributes over addition.

My answer yould look like this, trying to make it very simple and readable.

/// <summary>
/// Uses the formula 4 * (1 - 1/3 + 1/5 - 1/7 + ...) to estimate pi
/// </summary>
public static double EstimatePi(int iterations)
{
    double series = 0;
    for(int i = 0; i < iterations; i++)
    {
        int sign = i.IsEven() ? 1 : -1;
        series += sign / (2d*i + 1);
    }
    return 4 * series;
}

private static bool IsEven(this int number)
{
    return (number % 2 == 0);
}