Posts Tagged ‘BigRational’

Calculating Pi in C# part 3 – using the BigRational class

Posted by Kash Farooq on August 1, 2011

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();
() => a.Calculate(BigRational.Divide(1, 5),1000,numberOfDigits));
() => b.Calculate(BigRational.Divide(1, 239), 1000, numberOfDigits));

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);
builder.Append(".");
builder.Append(piToBeFormatted.Substring(1, numberOfDigits - 1));
return builder.ToString();
}
}
```