Kash Farooq's software development blog

.NET Developer

Posts Tagged ‘Software Development’

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();
    }
}
Advertisements

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

Calculating Pi in C# part 2 – using the .NET 4 BigInteger class

Posted by Kash Farooq on July 23, 2011

In my previous post, I used a couple of algorithms to calculate Pi. With my implementation of the algorithms, to get to a precision of just 6 decimal places took well over a million iterations and over 3 seconds.

Clearly I was doing something wrong.

A few Google searches later I found this implementation by Julian M Bucknall. In this implementation, Julian creates a BigNumber class to handle the fact that, before .NET 4, there was no way to handle numbers to many digits of precision. His class uses  fixed point arithmetic for storing data and performing calculations – effectively it works in base 4,294,967,296 (which is 232).

As .NET does now contain a BigInteger class (in .NET 4’s System.Numerics), I started searching for C# implementations that used this class. I couldn’t find anything in C#, but I did find a Java implementation that used a BigInteger class.

So, I decided to port it to C#, amending the BigInteger usages to match the .NET implementation syntax.

The formula used is the one that John Machin devised in 1706:

John Machin's Pi formulaSo, here is the .NET port of the Java implementation  – it includes a method called InverseTan to be used in the above formula, which I won’t even try to understand at the moment. I’m just doing the port!

public class PiJavaPort {
    public static BigInteger InverseTan(int denominator, int numberOfDigitsRequired) {
        int demonimatorSquared = denominator*denominator;

        int degreeNeeded = GetDegreeOfPrecisionNeeded(demonimatorSquared, numberOfDigitsRequired);

        BigInteger tenToNumberPowerOfDigitsRequired = GetTenToPowerOfNumberOfDigitsRequired(numberOfDigitsRequired);

        int c = 2*degreeNeeded + 1;
        BigInteger s = BigInteger.Divide(tenToNumberPowerOfDigitsRequired, new BigInteger(c)); // s = (10^N)/c
        for (int i = 0; i < degreeNeeded; i++) {
            c = c - 2;
            var temp1 = BigInteger.Divide(tenToNumberPowerOfDigitsRequired, new BigInteger(c));
            var temp2 = BigInteger.Divide(s, new BigInteger(demonimatorSquared));
            s = BigInteger.Subtract(temp1, temp2);
        }
        Console.WriteLine("Number of iterations=" + degreeNeeded);

        // return s/denominator, which is integer part of 10^numberOfDigitsRequired times arctan(1/k)
        return BigInteger.Divide(s, new BigInteger(denominator));

    }

    private static int GetDegreeOfPrecisionNeeded(int demonimatorSquared, int numberOfDigitsRequired) {
        //the degree of the Taylor polynomial needed to achieve numberOfDigitsRequired
        //digit accuracy of arctan(1/denominator).
        int degreeNeeded = 0;

        while ((Math.Log(2*degreeNeeded + 3) + (degreeNeeded + 1)*Math.Log10(demonimatorSquared))
                                                <= numberOfDigitsRequired*Math.Log(10)) {
            degreeNeeded++;
        }
        return degreeNeeded;
    }

    private static BigInteger GetTenToPowerOfNumberOfDigitsRequired(int numberOfDigitsRequired) {
        var tenToNumberOfDigitsRequired = new BigInteger(1);

        //  The following loop computes 10^numberOfDigitsRequired
        for (var i = 0; i < numberOfDigitsRequired; i++) {
            tenToNumberOfDigitsRequired = BigInteger.Multiply(tenToNumberOfDigitsRequired, new BigInteger(10));
        }
        return tenToNumberOfDigitsRequired;
    }
}

Finally, we need a method to put it all together – we need to implement the Machin formula:

public static string Calculate(int numberOfDigitsRequired)
{
    numberOfDigitsRequired += 8; //  To be safe, compute 8 extra digits, to be dropped at end. The 8 is arbitrary

    var a = BigInteger.Multiply(InverseTan(5, numberOfDigitsRequired), new BigInteger(16)); //16 x arctan(1/5)
    var b = BigInteger.Multiply(InverseTan(239, numberOfDigitsRequired), new BigInteger(4)); //4 x arctan(1/239)

    BigInteger pi = BigInteger.Subtract(a, b);

    var piAsString = BigInteger.Divide(pi, new BigInteger(100000000)).ToString();
    var piFormatted = piAsString[0]+"."+piAsString.Substring(1,numberOfDigitsRequired-8);
    return piFormatted;
}

Now to test the two implementations for performance – my Java port above vs. Julian M Bucknall implementation using his own BigNumber class.

First, my Java Port using .NET’s numerics:

Precision = 1000 digits
Number of iterations needed = 3659
Elapsed Milliseconds = 96

Not bad! Much better than 1 million plus iterations for 6 decimal places that my pathetic attempt took!

Now to Julian M Bucknall’s implementation (using his own BigNumber class):

Precision = 1000 digits
Number of iterations needed = 1603
Elapsed Milliseconds = 77

We have a winner.

Julian’s BigNumber class is optimised for this calculation – it can only divide a BigNumber by an integer. You cannot divide a BigNumber by another BigNumber. He states that if he had to implement such functionality he “would have discretely dropped the entire project”!

BigInteger does not have this limitation (and this functionality is used in the port).

Posted in .NET, Algorithms | Tagged: , , , | Leave a Comment »

Programmatically searching Google (Part 2): Using the RESTful interface

Posted by Kash Farooq on January 30, 2011

This post follows on from part 1, in which I perform a Google search using the .NET wrapper library project. I was curious why the library didn’t appear to provide any paging functionality and seemed to just get all the search results in one hit.

So, I’m now going to look at searching directly using Google’s RESTful API.

The URL that you hit is:

http://ajax.googleapis.com/ajax/services/search/web?v=1.0&q=MY SEARCH TEXT&rsz=large&key=MY GOOGLE KEY&start=0

You can omit the key, but Google recommends you provide it.

This returns a JSON result set like the following.

[Note: also see “Creating .NET objects from JSON using DataContractJsonSerializer“]

{"responseData":
 {"results":
 [
  {
  "GsearchResultClass":"GwebSearch",
  "unescapedUrl":"http://www.google.com/help/features.html",
  "url":"http://www.google.com/help/features.html",
  "visibleUrl":"www.google.com",
  "cacheUrl":"http://www.google.com/search?q\u003dcache:BNRWhS8EKYAJ:www.google.com",
  "title":"\u003cb\u003eSearch\u003c/b\u003e Features - \u003cb\u003eGoogle\u003c/b\u003e",
  "titleNoFormatting":"Search Features - Google",
  "content":"To find reviews and showtimes...."
  },
  {
  "GsearchResultClass":"GwebSearch",
  etc
  },
  etc
 ],
 "cursor": {
 "pages": [
  { "start": "0", "label": 1 },
  { "start": "8", "label": 2 },
  etc
  { "start": "56","label": 8 }
  ],
  "estimatedResultCount": "59600000",
  "currentPageIndex": 0,
  "moreResultsUrl": "http://www.google.com/search?oe=utf8&ie=utf8&source=uds&start=0&hl=en&q=MY SEARCH TEXT"
  }
 },
 "responseDetails": null,
 "responseStatus": 200
}

Now we’re getting somewhere. The “cursor” block at the bottom of the returned data provides paging information, a “moreResultsUrl”, an estimate of the number of results. Eveything we need.

As I have been told the number of pages (in the above example there are 8 pages) and the starting point of each page (0, 8, …, 56), I can just use my original URL again, and adjust the start parameter for each call (i.e. I don’t need to use the moreResultsUrl data provided in the cursor block).

So, I can just use:

http://ajax.googleapis.com/ajax/services/search/web?v=1.0&q=MY SEARCH TEXT&rsz=large&key=MY Google KEY&start=8

After playing with some more searches I realised that a maximum of 8 pages were being returned each time.

In my example above, each page returned 8 results. 8 pages of 8 results does not give me 59600000 results!

I tried the following URL:

http://ajax.googleapis.com/ajax/services/search/web?v=1.0&q=MY SEARCH TEXT&rsz=large&start=100

The result returned was:

{"responseData": null, "responseDetails": "out of range start", "responseStatus": 400}

Google does not allow you to search for more than 64 results!

So the only way to get more than 64 results would be to screen scrape, which is ugly (but can be made more bearable by using SGMLReader and LINQ to XML). Though I’m pretty sure Google’s T’s & C’s don’t allow screen scraping!

Posted in .NET | Tagged: , , | Leave a Comment »