On a recently snowboarding holiday I found myself having some decidedly geeky conversations with a good friend of mine, Giles Knap. Giles is currently learning F# and was extolling its virtues while I did my best to defend C#, explaining to him that C# 3.0 included most of the functional language constructs that I was interested in.

At the end of the holiday the two of us came up with an idea. We both wanted to better understand each other’s chosen programming language, and Giles wanted something that would help him learn F#. We were both familiar with a website called ProjectEuler.net which presents a number of mathematical questions and challenges people to solve them – generally be writing a small amount of code. So, we picked 6 questions from the ProjectEuler.net site and each coded up a solution; mine in C# and Giles’ in F#.

What we were looking for was the descriptive power of the languages. The questions on ProjectEuler.net quite often have several solutions, where the most efficient solution is based upon knowing some mathematical shortcut (e.g. calculation of Fibonacci sequence is very much quicker if you happen to know about the golden ratio) but we weren’t particularly interested in writing the very best performing code – rather, we wanted to write code that showed the language off in its best light and described to a reader exactly what was going on. That said, if the code wasn’t able to generate an answer in a few seconds then it wasn’t considered.

So, here are the 6 problems, from ProjectEuler.net, that Giles chose for us:

Problem 10 – Calculate the sum of all the primes below 2 million.

Problem 12 – What is the value of the first triangle number to have over five hundred divisors?

Problem 25 – What is the first term in the Fibonacci sequence to contain 1000 digits?

Problem 40 – Finding the nth digit of the fractional part of the irrational number.

I’ll cover problems 10 and 12 here, and the others in subsequent posts. The source code for our solutions can be found at http://FSharpCSharp.codeplex.com. If you want to play along then you’ll need to get the September 2008 CTP for F#.

## Problem 10: Calculate the sum of all the primes below 2 million.

*Full details of problem 10 can be found here. *

To solve this problem you first need something that can generate primes. Then, with this, you can start summing them. The Sieve of Eratosthenes is a simple technique for finding all the prime numbers up to a specified integer, so in both the C# and F# solution we use this technique.

### C# Solution

To generate primes I created a type that returned an **IEnumerable<long>**. This method returns an enumerator that will supply prime numbers up to some given maximum value:

The sieve works by creating **nonprimes**, an array of **bool**, and marking each position in the array as being a prime or not. All values are assumed to be prime (i.e. **nonprime[n] = false**) until marked as nonprimes **(nonprime[n] = true**). Whenever we find a prime then we mark all the multiples of that prime as being non-prime. We start marking multiples of the prime from the square of the prime because we can assume all other numbers below that value will have already been marked.

With this Prime number generator in place, the C# solution to problem 10 looks pretty simple:

By making use of the extension method Sum on **IEnumerable<T>** I can write a single line of code that creates my sieve, gets an enumeration of primes up to 2 million, and then sums them. This approach of writing sequence generators (methods that return **IEnumerable<T>**) is something that I’ve used throughout the C# solutions because it results in very simple and easy to understand solutions.

### F# Solution

The F# solution to this problem takes the exact same approach:

In my opinion this solution benefits from a number of F# features. Firstly, it’s way more compact. All those opening and closing brackets in the C# solution are missing. Yes, I could have dropped a number of them, but I tend to stick to StyleCop’s rules for C# formatting. Secondly, the way that sequence expressions and sequences in general work in F# make it a very powerful language for solving any problem that deals with a sequence of numbers, such as those generated by the Sieve of Eratosthenes.

So, apart from some stylistic differences there isn’t much difference between the C# and F# solutions to this problem.

## Problem 12: What is the value of the first triangle number to have over five hundred divisors?

*Full details of problem 12 can be found here. *

Problem 12 deal with triangle numbers, and then working out how many divisors each of these numbers has.

### C# Solution

The first thing I did was write code that generated triangle numbers. As with Problem 10, I did this by writing code that returned an IEnumerable<T>. Here is my Triangle Number generator:

This simple code will yield each a triangle number when the called “pulls” in the enumerator. Next, I needed something that would tell me each of the divisors that a given integer had. I did this by writing an extension method on the Int32 type that returned an IEnumerable<int> containing each divisor:

With my Triangle Number generator, and my GetDivisors extension method, I was finally able to solve this problem with the following code:

This comprehension syntax query is, in my opinion, pretty simple to read and does a good job of describing the solution to the problem.

### F# Solution

Giles’ F# solution also follows the same strategy as mine. Here is the code:

## Conclusions (so far)

Maybe it’s because we both chose similar ways of solving these problems, or maybe it’s because these questions don’t lend themselves to showing the language differences, but to me Problems 10 and 12 have equally readable and understandable representations in both C# and F#.

One big difference that we found between the C# and F# solutions was the performance. Using some simple timing code we observed that for Problem 10 the F# solution was approx 5 time slower than the C# solution. In addition the F# solution used a pretty large amount of memory. Why is this?

The F# collection types all support IEnumerable and you can build them with a sequence generating pattern which uses yield, just like C#. However, it turns out that there are some performance overheads with this approach. These sequence iterator blocks are compiled into state machines in C# (Jon Skeet has an article that explains how this happens) but in F# they use lambda functions. Using this approach in a nested loop is therefore very expensive!

The HubFS site proved invaluable in resolving this issue, for the full thread see http://cs.hubfs.net/forums/thread/9149.aspx. A total of 4 different solutions were suggested and tested. We selected the solution that had reasonable performance but still demonstrated an elegant way of using the F# sequence type (thanks to ‘kvb‘ for the suggested code). We did find a solution that gives the same performance as C# but it was rejected as being too ugly! It’s understood that this perf issue with sequence blocks will be addressed in a future release of F#.

## Next Time

In the next post I’ll be looking at 25 and 27. 25 is a particularly interesting Problem in that solving it in C# was tricky and, in fact, required a little help from F#. In the mean time, feel free to play with our code, make it better, show us the error of our ways, or come up with even more elegant solutions that show one or other of the languages in their best light.

In problem 10, have you considered using the Aggregate operator? IIRC, you should be able to use it to do the equivalent of F#’s fold, passing in an object to represent the calculation state. The difficulty is in trying to get your sieve and the prime split apart, but it could be interesting seeing you can do it.

http://msdn.microsoft.com/en-us/library/system.linq.enumerable.aggregate.aspx

See also the Range operator: http://msdn.microsoft.com/en-us/library/system.linq.enumerable.range.aspx

One (top of my head) that doesn’t use Aggregate:

var nonPrimes = new bool[max + 1];

Enumerable

.Range(2, max – 1)

.Where(i => !nonPrimes[i])

.Select(i =>

{

for (var j = i * i; j <= max; j += i) { nonPrimes[j] = true; }

return i;

});

I think this should be another way to cast GetDivisors, and should be able to take advantage of the Parallel Extensions (adding .AsParallel() after the call to .Range):

var max = (int)Math.Sqrt(value);

Enumerable

.Range(0, max)

//.Select(x => max – x) // not needed, since algorithm is order independent .. parallelizable with PLINQ

.Where(i => value % i == 0)

.SelectMany(i => new[] { i, value / i });

And maybe this for your triangle function:

Enumerable

.Range(0, int.MaxValue)

.Aggregate(0, (total, i) => total + i)

I haven’t actually tested any of these (juggling), but they should work, or be close to working. Of course, it brings you closer to functional programming, which is of course F#’s realm.

Thank you for submitting this cool story – Trackback from DotNetShoutout

@kfarmer. Thanks for the ideas.

Re your Enumerable.Range suggestion: It looks good, and I like the style of the code. I’ve written a version of GetPrimes that uses this code. It annoys me that Enumerable.Range only deals with int as I need to work with long here. I might create my own version of Range.

Any code that gets rid of the for loops is good for me.

This week we have MapReduce, WebTools and yet another F# to C# language comparison. I spent yesterday

This is part one of a three part post where myself and Giles Knap play around with C# and F# to see if

RE: Solutions to Euler Problem 10…

While this study is interesting as a comparison between the languages, neither version is really efficient as to maximum speed. The choice to use the bit packed array of BitArray for both solutions for the prime sieve is one made to save space (by a factor of eight in this case), where for this problem of the primes up to two million, the use of two million bytes for modern machines is not a consideration. If space were a consideration, one would at least do the slight modifications so that one only sieves for the odd primes of three and up for a saving of half the space. BitArray operations are about 3.5 times slower than byte boolean operations.

If elegance of code is a consideration, one would likely write the F# code more in line with that of the current C# code as in;

let Solve () = GetPrimes 1999999 |> Seq.sum

Further, if speed and elegance were desired, one would only run the Sieve culls up to the square root of the maximum number tested, as there will be no culling of composite numbers done past that point, and all prime finding operations may as well be in 32-bits with only the summing taking place for 64-bits.

If general speed, space requirements, and elegance are all to to satisfied, one might use the following F# code, which solves the problem 10 using about one million bytes of memory in a small fraction of a second on a modern personal computer:

let GetOddPrimes max =

let LSTNDX = (max – 3) / 2

let LSTCULNDX = (int (sqrt (double max)) – 3) / 2

let inline prime i = i + i + 3

let inline strtndx i = ((prime i * prime i) – 3) >>> 1

let buf = Array.create (LSTNDX + 1) true

seq {0 .. LSTCULNDX}

|> Seq.filter (fun i -> buf.[i])

|> Seq.iter (fun j -> seq {strtndx j .. prime j .. LSTNDX} |> Seq.iter (fun j -> buf.[j] <- false))

seq {0 .. LSTNDX} |> Seq.filter (fun i -> buf.[i]) |> Seq.map (fun i -> i + i + 3)

let Solve () = (GetOddPrimes 1999999 |> Seq.map uint64 |> Seq.sum) + 2UL

Although small, simple and elegant, the above code is still many times slower than using a pure imperative code solution using loops rather than IEnumerable (as implied by using sequences) due to the extra overhead of calling the methods of the interfaces; this is even worse for the current CTP 2.0 version of F#, which still has a very inefficient Core run time library that implements these interface methods with multiple extra virtual method calls in order to generalize the use of the sequence objects; C#, while still slower than using loops, is considerably more optimized. While this isn't so important for a trivial problem such as this, larger problems such as calculating the number of primes in the 32 bit number range would be quite slow compared to using imperative techniques.

Write, compile, and test a program that displays a person's full name, street address, and city and state on three separate lines on the screen. Save the program as Address.cs.

write, compile,and test a program that displays a person's first name on the screen. Save the program as Name.cs.

Write, compile, and test a program that displays a person's full name, street address, and city and state on three separate lines on the screen. Save the program as Address.cs.

Write, compile, and test a program that displays your favorite quotation on the screen. Include the name of the person to whom the quote is attributed. Use as many display lines as you feel are appropriate. Save the program as Quotation.cs.

string connectionString = ConfigurationManager.ConnectionStrings["ConnectionString"].ConnectionString;

in above line code show following error plz solve it now

System.NullReferenceException: Object reference not set to an instance of an object.

In continuation to Animals exercise we did in OOPs session, we move to the next level where we have a Jungle where these animals live. My jungle contains these animals with following count –

Total animals = 200

Carnivorous = 50

Herbivorous = 150

Lions = 10 (with weight 100,110,120,130…)

Cats = 20 (with weight 10,15,20,25,30…)

Dogs = 20 ( Bulldog – 5, Chihuahua – 5, Labrador – 10)

Goats = 50 (with weight 20,21,22,23…..)

Cows = 50 (with weight 120,121,122,123…..)

Elephants = 50 (with weight 420,421,422,423…..)

When a carnivorous eats any other animal, the count changes for that animal and total number of animals in the Jungle. Same is the case when a new one is born in any species. Write a program which does the following –

1. Displays the count for each animal in the Jungle.

2. Asks for input – <Carnivore> ate <Animal> with weight <weight>. When user presses enter, it displays the remaining animals of that species and the total number of animals in Jungle left. There are certain rules though –

a. No one can eat Elephants.

b. Any carnivore can eat animal less that its own weight.

c. If there is no animal with the specified weight, show a message accordingly.

2. Asks for input – <Animal> gave birth to a new one. When user presses enter, it displays the new count of animals of that species and the total number of animals in Jungle left.

please mail me the solution of this problem as soon as possible using oops concept and collections. my email id is rockygupta762@gmail.com