In an earlier post I ported a Java implementation of a Pi calculator – my port used the BigInteger class that lives in the System.Numerics assembly of .NET 4. I also performance tested my port against an implementation by Julian M Bucknall that used his own BigNumber class. Julian’s implementation won that performance test, coming in at an impressive 70-80 milliseconds to calculate Pi to 1000 decimal places.

Now it is time for me to try an implementation alone!

I’m going to use the following John Machin formula:

Arctan can be calculated using the following Taylor series:

Rather than creating arbitrarily big numbers with BigInteger, I need to create numbers with arbitrarily large precision. I need a BigRational. And one exists, but it did not make it into the .NET 4 framework. You can download BigRational form CodePlex.

So, here is my implementation of arctan:

public class ArcTanWithBigRational { public ArcTanWithBigRational() { Iterations = 0; } public int Iterations; public BigRational Calculate(BigRational x, int maxNumberOfIterations, int precision) { bool doASubtract = true; BigRational runningTotal = x; int count = 0; var divisor = new BigInteger(3); while (count < maxNumberOfIterations) { BigRational current = BigRational.Pow(x, divisor); current = current/divisor; if (doASubtract) { runningTotal = runningTotal - current; } else { runningTotal = runningTotal + current; } doASubtract = !doASubtract; count++; divisor = divisor + 2; if (WeHaveEnoughPrecision(current, precision)) { Iterations = count; break; } } return runningTotal; } private static bool WeHaveEnoughPrecision(BigRational current, int precision) { return current.GetFractionPart().ToString().Length > precision+2; //extra 2 digits to ensure enough precision } }

Now to perform the calculation:

public string Calculate(int numberOfDigits) { var arcTanA = new ArcTanWithBigRational(); var arcTanB = new ArcTanWithBigRational(); var a = 16 * arcTanA.Calculate(BigRational.Divide(1, 5), 1000, numberOfDigits); var b = 4 * arcTanB.Calculate(BigRational.Divide(1, 239), 1000, numberOfDigits); var pi = a - b; return BigRationalPiFormatter.Format(pi, numberOfDigits); }

And the results:

Precision = 1000 digits Number of iterations = 923 Elapsed Milliseconds = 1192

Not bad! No where near as fast as the other implementations in my previous post, but not too bad and with far fewer iterations.

I can try one final optimization to try and get my implementation running faster. I have a dual-core laptop so let’s try some Parallel Tasks:

public string Calculate(int numberOfDigits) { var a = new ArcTanWithBigRational(); var b = new ArcTanWithBigRational(); Task<BigRational> task1 = Task<BigRational>.Factory.StartNew( () => a.Calculate(BigRational.Divide(1, 5),1000,numberOfDigits)); Task<BigRational> task2 = Task<BigRational>.Factory.StartNew( () => b.Calculate(BigRational.Divide(1, 239), 1000, numberOfDigits)); var pi = 16 * task1.Result - 4 * task2.Result; return BigRationalPiFormatter.Format(pi, numberOfDigits); }

The results this time:

Precision = 1000 digits Number of iterations = 923 Elapsed Milliseconds = 1099

A little faster, but nothing to get excited about.

For completeness, here is my routine to format the BigRational Pi into a string:

public class BigRationalPiFormatter { public static string Format(BigRational pi, int numberOfDigits) { BigInteger numeratorShiftedToEnoughDigits = (pi.Numerator * BigInteger.Pow(new BigInteger(10), numberOfDigits)); var bigInteger = numeratorShiftedToEnoughDigits / pi.Denominator; string piToBeFormatted = bigInteger.ToString(); var builder = new StringBuilder(); builder.Append(piToBeFormatted[0]); builder.Append("."); builder.Append(piToBeFormatted.Substring(1, numberOfDigits - 1)); return builder.ToString(); } }