Kash Farooq's software development blog

.NET Developer

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:

John Machin's Pi formulaArctan can be calculated using the following Taylor series:

ArcTan calculated using the Taylor SeriesRather 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();
    }
}

Posted in .NET, Algorithms | Tagged: , , , | 2 Comments »

 
Follow

Get every new post delivered to your Inbox.