Kash Farooq's software development blog

.NET Developer

Archive for the ‘.NET’ Category

MongoDB in C#: Mapping IDs

Posted by Kash Farooq on March 4, 2012

In my previous post about C# and MongoDB, I polluted my domain model with a MongoDB type:

public class Movie
{
  public BsonObjectId Id { get; set; }
  public string Title { get; set; }
  public string Year { get; set; }

  etc
}

When you Insert a document into MongoDB using the C# driver, the driver needs to check to see if the Id has a value. It assigns one if it doesn’t. The above code worked because I used a MongoDB C# driver ID type – the driver could work out what my ID property is. But I don’t really want to use BsonObjectId in this class – it ties me to MongoDB. Instead, you can use a built-in .NET type for the ID property and tell the MongoDB C# driver about it.

First, let’s change the type of the Id property. I’ve gone for a string but there are other types you could use:

public class Movie
{
  public string Id { get; set; }
  public string Title { get; set; }
  public string Year { get; set; }

  etc
}

Now, you need to map that property. I’m doing this code in an NUnit test, so I’m going to do the mapping in the TestFixtureSetUp:

[TestFixtureSetUp]
public void TestFixtureSetUp()
{
  BsonClassMap.RegisterClassMap<Movie>(cm => {
                                              cm.AutoMap();
                                              cm.SetIdMember(cm.GetMemberMap(x => x.Id).SetIdGenerator(StringObjectIdGenerator.Instance));
                                             }
                                       );
}

So, I’ve told the MongoDB C# driver that the ID column is Movie.Id and that it needs to use its built in StringObjectIdGenerator to generate IDs.

There are several ID generators built into the driver:

  • BsonObjectIdGenerator
  • CombGuidGenerator
  • GuidGenerator
  • NullIdChecker
  • ObjectIdGenerator
  • StringObjectIdGenerator
  • ZeroIdChecker<T>

Read the CSharp Driver Serialization Tutorial for more information about these generators and mapping them to properties.

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

Cleaning all bin and obj files with MSBuild

Posted by Kash Farooq on February 26, 2012

I thought I’d blog this as it took me a frustratingly long time to work out how to do it (I’m new to MSBuild scripts – I usually do my builds with nant).

I wanted to simply clean my solution before the build. The solutions I found on Stack Overflow were unsatisfactory. For example, I didn’t want to have to name the folders that I wanted to delete files from.

So, here’s what I did; I simply called the “Clean” MSBuild target for all csproj files found below the directory the build was initiated from:


<?xml version="1.0" encoding="utf-8" ?>
<Project xmlns="http://schemas.microsoft.com/developer/msbuild/2003" DefaultTargets="Build-and-test">

  <Target Name="Build-and-test">
    <CallTarget Targets="clean-all-folders"/>
    <CallTarget Targets="build"/>
    <CallTarget Targets="unit-tests"/>
  </Target>

  <ItemGroup>
    <ProjectFiles Include="**\*.csproj" />
  </ItemGroup>

  <Target Name="clean-all-folders">
    <MSBuild Projects="@(ProjectFiles)" targets="Clean" />
  </Target>

  etc.
</Project>

This doesn’t delete the bin, debug and obj folders – but I don’t believe that is a problem.

The above script is generic – it doesn’t care what the project files or solution are called.

You can eliminate the ItemGroup if you are willing to hard code your solution file:

<Target Name="clean-all-folders">
   <MSBuild Projects="MySolition.sln" targets="Clean" />
</Target><

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

Playing with FluentAssertions

Posted by Kash Farooq on February 23, 2012

I thought I’d try a FluentAssertions - a different way of doing asserts in Unit Tests.

As the name of the library suggests, your assertion code is fluent. i.e. methods are chained.

Some examples.

A simple assert:

person.YearOfBirth.Should().Be(1945);

To check a list has the correct number of elements:

personList.Should().HaveCount(10);

To ensure that a list has elements in a certain order:

IEnumerable<int> positions = personList.Select(x => x.Rank);
positions.Should().ContainInOrder(new[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10});

There are lots of helper methods and the lots of examples in the on-line documentation.

I quite like it and have been using it on a project.

And it’s not just the assertion style that I like.

The thing that really impressed me was when one of my tests failed. In my assert I was comparing two strings. I clearly should have done a .Trim() on my string under test, but I forgot. And here is the error I saw in my test runner window:


Expected string to be
"John Smith", but it has unexpected whitespace at the end.

How useful is that! No more “the string differs at position 45″.

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

Getting started with MongoDB in C#

Posted by Kash Farooq on February 18, 2012

I thought I’d play with NoSQL. There are lots of implementations to choose from, but I’ve decided to start with MongoDB. Especially after seeing the impressive list of real-life production MongoDB deployments.

The MongoDB server and data structure is organised as follows:

  • A Mongo server holds a set of databases
  • A database holds a set of collections
  • A collection holds a set of documents
  • A document is a set of fields
  • A field is a key-value pair
  • A key is a string
  • A value is a
    • strings, integers, etc.
    • another document
    • an array of values

Right. Let’s get started. First, download the two things you’ll need to start developing MongoDB apps in .NET: the database software and the C# driver.

I also recommend you download a PDF of the documentation. It is available as a MongoDB docs daily build. This PDF contains everything: set-up instructions, tutorials, advice and language specific driver documentations.

Use the Windows Quick Start to get going and test your MongoDB server with the administrative JavaScript shell client. I also advise you go through the tutorial - it walks you through more complex examples using the administrative shell client. As noted above, both these guides are in the MongoDB Docs PDF.

Install the C# driver by just running the MSI. It installs to C:\Program Files (x86)\MongoDB.

Create a .NET project and add assembly references to MongoDB.Driver.dll and MongoDB.Bson.dll. I created NUnit integration tests to test MongoDB.

First, I created a class that I wanted to store as a MongoDB document:

public class Movie
{
  public BsonObjectId Id { get; set; }
  public string Title { get; set; }
  public string Year { get; set; }
  public List<string> Actors { get; set; }

  public void AddActor(string actor)
  {
    if (Actors == null)
    {
      Actors = new List<string>();
    }
    Actors.Add(actor);
  }
}

Things to note in this class:

  • I’ve used the type BsonObjectId. To get up and running quickly, I basically told the MongoDB C# driver which property to use as an ID. You don’t have to do this. To see how to remove MongoDB C# driver specific types from your domain object, see my Mapping IDs post.
  • I’ve included a generic list – I wanted to see how the C# driver copes with this, how MongoDB stores this data, and how we can search for documents using this data.
  • I had to make the Actors list public, otherwise the C# driver wouldn’t store it. Perhaps there is a way to force the driver to store it without making it public? Something to research.

Next, let’s open a connection to a database and insert some data. I’m orchestrating the prerequisites for my test through a NUnit Setup method the connects to the database, empties the collection and inserts some fresh data:

private MongoServer server;
private MongoDatabase moviesDatabase;

[SetUp]
public void SetUp()
{
  Connect();
  Clean();
  InsertData();
}

private void Connect()
{
  server = MongoServer.Create();
  moviesDatabase = server.GetDatabase("movies_db");
}

As you can see, the connect method didn’t use any information such as connection strings, usernames, etc. It just calls Create. If you don’t provide any parameters it connects to a default instance of MongoDB on localhost. If you’ve changed any of the default settings, you’ll need a connection string.

The GetDatabase method gets me an instance of the “movies” database if it exists, or lazily creates it if it doesn’t (i.e. it won’t actually be created until you save some data to it).

The Clean() method is just used to empty the collection each time a test runs. I’m calling the RemoveAll method to empty all elements from the movies_collection:

private void Clean()
{
  var moviesCollection = moviesDatabase.GetCollection<Movie>("movies_collection");
  moviesCollection.RemoveAll();
}

Now let’s add some data to the movies_collection and save it to the movies_db:

private void InsertData()
{
  //Create some data
  var movie1 = new Movie {Title = "Indiana Jones and the Raiders of the Lost Ark", Year = "1981"};
  movie1.AddActor("Harrison Ford");
  movie1.AddActor("Karen Allen");
  movie1.AddActor("Paul Freeman");

  var movie2 = new Movie {Title = "Star Wars: Episode IV - A New Hope", Year = "1977"};
  movie2.AddActor("Mark Hamill");
  movie2.AddActor("Harrison Ford");
  movie2.AddActor("Carrie Fisher");

  var movie3 = new Movie {Title = "Das Boot", Year = "1981"};
  movie3.AddActor("Jürgen Prochnow");
  movie3.AddActor("Herbert Grönemeyer");
  movie3.AddActor("Klaus Wennemann");

  //Insert the movies into the movies_collection
  var moviesCollection = moviesDatabase.GetCollection<Movie>("movies_collection");
  moviesCollection.Insert(movie1);
  moviesCollection.Insert(movie2);
  moviesCollection.Insert(movie3);
}

So, we’ve created/opened a database called movie_db and insert some data into a movies_collection. Let’s check it’s there – get the collection and check that there are 3 movies in it.

[Test]
public void ShouldFindThreeMoviesInTheCollection()
{
  var moviesCollectionRetrieved = moviesDatabase.GetCollection<Movie>("movies_collection");
  Assert.That(moviesCollectionRetrieved.Count(), Is.EqualTo(3));
}

Now let’s do a query on the movie data. Let’s look for movies that were released in 1981, i.e. perform a query based on one of the keys – in this case, the “Year” key:

[Test]
public void ShouldFindTwoMoviesThatWereMadeIn1981()
{
  var moviesCollectionRetrieved = moviesDatabase.GetCollection<Movie>("movies_collection");

  QueryComplete findMoviesMadeIn1981Query = Query.EQ("Year", "1981");
  var moviesFound = moviesCollectionRetrieved.FindAs<Movie>(findMoviesMadeIn1981Query);

  Assert.That(moviesFound.Count(), Is.EqualTo(2));
  Assert.That(moviesFound.Count(movie => movie.Title == "Das Boot"), Is.EqualTo(1));
  Assert.That(moviesFound.Count(movie => movie.Title == "Indiana Jones and the Raiders of the Lost Ark"),Is.EqualTo(1));
}

Note that I used the generic version FindAs method – to get the C# driver to create movie objects from the MongoDB documents.

You can also very easily perform queries based on values stored in lists. Here, for example, I am looking for documents that contain a certain value in the Actors list – let’s look for movies that Harrison Ford has been in:

[Test]
public void ShouldFindTwoMoviesThatHarrisonFordHasBeenIn()
{
  var moviesCollectionRetrieved = moviesDatabase.GetCollection<Movie>("movies_collection");

  var findMoviesWithHarrisonFordInThem = Query.EQ("Actors", "Harrison Ford");
  var moviesFound = moviesCollectionRetrieved.FindAs<Movie>(findMoviesWithHarrisonFordInThem);
  Assert.That(moviesFound.Count(), Is.EqualTo(2));
  Assert.That(moviesFound.Count(movie => movie.Title == "Star Wars: Episode IV - A New Hope"),Is.EqualTo(1));
  Assert.That(moviesFound.Count(movie => movie.Title == "Indiana Jones and the Raiders of the Lost Ark"),Is.EqualTo(1));
}

Very neat.

In the code above I’ve been using Count(). That does not mean that the C# driver supports delayed execution and LINQ. The official statement is: “Version 1.0 of the official C# driver does not yet support LINQ”. In fact, the documentation states that for the following code, the query is sent to the server twice (once for FirstOrDefault and once for LastOrDefault)


var query = Query.EQ("author", "Ernest Hemingway");
var cursor = books.Find(query);
var firstBook = cursor.FirstOrDefault(); //query executed twice on the server
var lastBook = cursor.LastOrDefault(); //once for each of these IEnumerable<T> extension methods.

Finally, let’s look at how the data has been stored using the administrative JavaScript shell client, mongo.exe.

With the client, I’ll connect to the server, switch to the movies database and then display all the documents in the movies_collection:


MongoDB shell version: 2.0.2
connecting to: test
> use movies_db
switched to db movies_db
> db.movies_collection.find().forEach(printjson);
{
 "_id" : ObjectId("4f3f82a1d5c8851b60430b9a"),
 "Title" : "Indiana Jones and the Raiders of the Lost Ark",
 "Year" : "1981",
 "Actors" : [
 "Harrison Ford",
 "Karen Allen",
 "Paul Freeman"
 ]
}
{
 "_id" : ObjectId("4f3f82a1d5c8851b60430b9b"),
 "Title" : "Star Wars: Episode IV - A New Hope",
 "Year" : "1977",
 "Actors" : [
 "Mark Hamill",
 "Harrison Ford",
 "Carrie Fisher"
 ]
}
{
 "_id" : ObjectId("4f3f82a1d5c8851b60430b9c"),
 "Title" : "Das Boot",
 "Year" : "1981",
 "Actors" : [
 "J├╝rgen Prochnow",
 "Herbert Gr├Ânemeyer",
 "Klaus Wennemann"
 ]
}
>

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

BDD with SpecFlow and Coypu (Part 1)

Posted by Kash Farooq on August 19, 2011

I’ve been doing TDD for years and I thought it was about time I got into BDD too.

I’m going to use BDD to add a UI in front of the various implementations of Pi calculation algorithms I’ve been working on.

This post will describe what you need to install and how to get a SpecFlow feature file running via NUnit.

Prerequisites

Headless browser:

Firing up a real browser from a BDD test can be slow. So, I’m using the Selenium headless Java browser.

Download selenium-server-standalone-2.4.0.jar (and, of course, you need Java)

To start it up:


java -jar selenium-server-standalone-2.3.0.jar

SpecFlow:

Install SpecFlow with the full installer and it will integrate with Dev Studio.

You can keep your feature files in your solution and SpecFlow will automatically generate NUnit based code-behind files.

I also recommend you watch the SpecFlow Screen Cast – an excellent introduction to quickly get you up and running.

Coypu

To get my SpecFlow BDD tests to interact with the browser, I’m using Coypu.

Coypu is:

A more intuitive DSL for interacting with the browser in the way a human being would, inspired by the ruby framework Capybara.

Other software

You need NUnit (as SpecFlow creates NUnit tests).

Adding the first feature file

I’ve already got a few implementations of algorithms to calculate Pi. I just want a simple UI that allows you to select an algorithm, type how many decimal places you want Pi calculated to, and then hit “Calculate”. I want the “Calculate” link/button to call back to my application via AJAX (I want to see how the headless browser copes with Javascript).

Step 1: Add a feature file

A feature file is just a text file that describes the functionality you want to implement. It has a simple Given-When-Then structure that should be understandable by non-developers. Hence, they could be created by Business Analysts, etc.

I created a new class library called Spec and added a feature file using the “Add New Item” Dev Studio menu. You’ll see the option “SpecFlow Feature File”.

Feature: Calculate Pi using various algorithms
	I want to be able to view Pi to varying decimal places

Scenario: Display Pi using Taylor series and Bucknall's BigNumber to many decimal places
	Given I visit the Pi.NET website
	And I have selected the 'Bucknall Big Number' algorithm
	And I have entered 500 decimal places
	When I press Go
	Then Pi should be displayed to the correct number of decimal places
	And Calculation statistics should be displayed

You’ll also need to add DLL references to TechTalk.SpecFlow.dll and nunit.framework.dll

Once you’ve done this, compile and run all the unit tests in your Spec class library. You’ll see output like this:


Given I visit the Pi.NET website
-> No matching step definition found for the step. Use the following code to create one:
[Binding]
public class StepDefinitions {
   [Given(@"I visit the Pi\.NET website")]
   public void GivenIVisitThePi_NETWebsite()
   {
       ScenarioContext.Current.Pending();
   }
}
etc, etc.

SpecFlow has told you exactly what you need to do.

So, let’s copy and paste the code into a new C# file called PiNetSteps:

[Binding]
public class PiNetSteps {
    [Given(@"I visit the Pi\.NET website")]
    public void GivenIVisitThePi_NETWebsite() {
        ScenarioContext.Current.Pending();
    }

    [Given(@"I have selected the 'Bucknall Big Number' algorithm")]
    public void GivenIHaveSelectedTheBucknallBigNumberAlgorithm() {
        ScenarioContext.Current.Pending();
    }

    [Given(@"I have entered 500 decimal places")]
    public void GivenIHaveEntered500DecimalPlaces() {
        ScenarioContext.Current.Pending();
    }

    [When(@"I press Go")]
    public void WhenIPressGo() {
        ScenarioContext.Current.Pending();
    }

    [Then(@"Pi should be displayed to the correct number of decimal places")]
    public void ThenPiShouldBeDisplayedToTheCorrectNumberOfDecimalPlaces() {
        ScenarioContext.Current.Pending();
    }

    [Then(@"Calculation statistics should be displayed")]
    public void ThenCalculationStatisticsShouldBeDisplayed() {
        ScenarioContext.Current.Pending();
    }
}

Now when you run the unit tests you get the output:


Ignored: One or more step definitions are not implemented yet.

We can improve the steps code by parameterizing it with Regex. For example, rather than hard coding “500 decimal places”, let’s make this a parameter. And the algorithm name can also be a parameter.

Making these changes gives:

[Given(@"I have selected the '(.+)' algorithm")]
public void GivenIHaveSelectedAnAlgorithm(string algorithm) {
    ScenarioContext.Current.Pending();
}

[Given(@"I have entered '(.+)' decimal places")]
public void GivenIHaveEnteredTheRequiredNumberOfDecimalPlaces(int numberOfDecimalPlaces) {
    this.numberOfDecimalPlaces = numberOfDecimalPlaces; //store for a later assert
    ScenarioContext.Current.Pending();
}

We’re now at a stage that opens up lots of possibilities. You’ve gone from a feature file to a C# class and you now have options on how deep you want your tests to go. If you system under test is not a web application, you are ready to start implementing it straight away. If your system has lots of external dependencies that are not under your control, you could easily stub them out with a container. Or perhaps you want your tests to go through all the application layers and hit a database or webservice. You could easily introduce test database and webservices if you wish.

In the next post I’ll get Coypu up and running and use it to get my SpecFlow steps class to hit the Selenium headless browser.

Next: BDD with SpecFlow and Coypu (Part 2)

Posted in .NET, Behaviour Driven Development, Test Driven Development | Tagged: , , , | Leave a Comment »

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));
        return builder.ToString();
    }
}

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

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 »

Calculating Pi in C# with series algorithms

Posted by Kash Farooq on July 17, 2011

People write applications to calculate Pi to thousands of decimal places – I decided to investigate how they do that.

Google took me to a post discussing using recursion to calculate Pi. Quite ironic considering the post is on Stack Overflow… Anyway, the post did provide me with plenty of links and algorithm names for me to refine my search and find a way to do it without recursion.

I soon found this: a collection of series algorithms to calculate Pi.

So, I picked an algorithm and started coding.

To get going quickly, I decided to just use the built in .NET value types (i.e. decimal, double). These clearly are not good enough if you want to calculate Pi to hundreds of decimal places, but they would do for now.

To check my algorithm implementation worked, I got Pi to a few thousand decimal places from the interweb :

public static class Pi {
    public const string PiAsString = "3.14159265358979323846264338327...etc";
    public static string Get(int numberOfDecimalPlaces) {
        return PiAsString.Substring(0, numberOfDecimalPlaces + 2);
    }
}

Leibniz-Gregory-Madhava Series

You can calculate Pi using the following:

In the code below, my base class property “PiCalculatedToRequiredPrecision” is, as the name suggests, there stop if I’ve reached my target number of digits. The “KeepGoing” property is used to bail out of the loop if I’ve done far too many iterations (which I keep track of in the Iteration property) and I have still not managed to get the required number of digits.

public class LeibnizGregoryMadhava:SeriesAlgorithmBase {
    public LeibnizGregoryMadhava(int numberOfDecimalPlaces) : base(numberOfDecimalPlaces) {}

    // Pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 .....

    public override decimal Calculate() {
        CurrentPi = 1;
        var multiplier = 1;
        var nextNumber = 3;

        decimal result = 1;
        while (KeepGoing) {
            multiplier = multiplier * -1;
            result = result + multiplier * (decimal)1 /(nextNumber);
            CurrentPi = result*4;
            if (PiCalculatedToRequiredPrecision)
            {
                break;
            }
            Iteration++;
            nextNumber += 2;
        }
        return CurrentPi;
    }
}

And now to run my algorithm a few times specifying a different precision each time:

LeibnizGregoryMadhava took 117 iterations and 6 milliseconds to calculate PI to 2 decimal places
LeibnizGregoryMadhava took 1686 iterations and 3 milliseconds to calculate PI to 3 decimal places
LeibnizGregoryMadhava took 10792 iterations and 22 milliseconds to calculate PI to 4 decimal places
LeibnizGregoryMadhava took 136119 iterations and 290 milliseconds to calculate PI to 5 decimal places
LeibnizGregoryMadhava took 1530010 iterations and 3358 milliseconds to calculate PI to 6 decimal places

Over 1.5 million iterations (and 3.4 seconds) to get to 6 decimal places!!

Time to try another algorithm.

Euler Series

public class Euler:SeriesAlgorithmBase {
    //pi^2 / 6 = 1 + 1/4 + 1/9 + ..... + 1/k^2

    public Euler(int numberOfDecimalPlaces) : base(numberOfDecimalPlaces) {}
    public override decimal Calculate() {
        decimal result = 0;
        Iteration = 1;
        while (KeepGoing)
        {
            long squared = Iteration * Iteration;
            result = result + (decimal)1/squared;
            CurrentPi = (decimal) Math.Sqrt((double) (result * 6));
            if (PiCalculatedToRequiredPrecision())
            {
                break;
            }
            Iteration++;
        }
        return CurrentPi;

    }
}

And the results:

Euler took 600 iterations and 74 milliseconds to calculate PI to 2 decimal places
Euler took 1611 iterations and 3 milliseconds to calculate PI to 3 decimal places
Euler took 10307 iterations and 22 milliseconds to calculate PI to 4 decimal places
Euler took 359863 iterations and 819 milliseconds to calculate PI to 5 decimal places
Euler took 1461054 iterations and 3319 milliseconds to calculate PI to 6 decimal places

Hmmm. Fewer iterations (just!) and 3.3 seconds to get to 6 decimal places.

I’m not going to break any world records with this code. Clearly I need to do more research.

To be continued.

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

Creating .NET objects from JSON using DataContractJsonSerializer

Posted by Kash Farooq on January 31, 2011

Creating .NET objects from JSON using DataContract and DataMember

In a previous post and demonstraed that the RESTful Google Search API returns data as JSON. I needed a way to convert the JSON data into .NET objects and this post shows what I ended up with.

Here is an example of the JSON result set returned:

{"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
}

We can use System.Runtime.Serialization to create .NET objects from this JSON data.

For example, the top level JSON responseData can be represented by the following .NET type:

[DataContract]
public class GoogleSearchResults {
  [DataMember(Name = "responseData")]
  public ResponseData ResponseData { get; set; }
}

Note that I’ve specified the Name attribute. Without it I would have had to have a property called “responseData” rather than “ResponseData”.

The rest of the data is extracted using the classes below. Note that I can be quite selective in what data I wanted to transfer from JSON to .NET. If I don’t need, say, the “cacheUrl”, I can just omit it from my .NET objects. I can also rename data. I have put the data from “titleNoFormatting” into a property called Title:

[DataContract]
public class ResponseData
{
  [DataMember(Name="results")]
  public IEnumerable<Result> Results { get; set; }

  [DataMember(Name = "cursor")]
  public Cursor Cursor { get; set; }
}

[DataContract]
public class Cursor
{
  [DataMember(Name = "moreResultsUrl")]
  public string MoreResultsUrl { get; set; }

  [DataMember(Name = "pages")]
  public IEnumerable<Page> Pages { get; set; }
}

[DataContract]
public class Result
{
  [DataMember(Name = "url")]
  public string Url { get; set; }

  [DataMember(Name = "titleNoFormatting")]
  public string Title { get; set; }
}

[DataContract]
public class Page
{
  [DataMember(Name = "start")]
  public int Start { get; set; }

  [DataMember(Name = "label")]
  public string Label { get; set; }
}

Finally, I need a method to actually deserialize a JSON string into my .NET objects. I can use System.Runtime.Serialization.Json.DataContractJsonSerializer to do this. I have created the following generic method that takes a JSON string and the type I want it to be deserialised into, and then returns an instantiated .NET object:

public static T Deserialise<T>(string json) {
  var obj = Activator.CreateInstance<T>();
  using (var memoryStream = new MemoryStream(Encoding.Unicode.GetBytes(json))) {
    var serializer = new DataContractJsonSerializer(obj.GetType());
    obj = (T) serializer.ReadObject(memoryStream);
    return obj;
  }
}

This generic method can then be used to convert a JSON string to the specified .NET type:

string reponseJson=GetJsonDataFromGoogle("MY SEARCH TERM);
results = Deserialise<GoogleSearchResults>(responseJson);
foreach (var googleSearchResult in results.ResponseData.Results) {
  Console.WriteLine(googleSearchResult.Url);
}

Posted in .NET | Tagged: , , , | 4 Comments »

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 »

 
Follow

Get every new post delivered to your Inbox.