Martin Peck

The Infrequent Ramblings of a Software Engineer

Solving Problems in C# and F# – Part 2


UPDATE: It’s been pointed out that the extension method RaiseToThePowerOf isn’t required. I’ve updated the C# solution to Problem 25 here, but left this post “as is”.

This is part one of a three part post where myself and Giles Knap play around with C# and F# to see if we find anything useful or interesting in the comparison. You can find Part 1 of this series here.

Thanks for Playing Along


First up, I’d like to say thanks to those of you who commented on Part 1. KFarmer gave some great comments, and in particular I liked his suggestion for implementing GetPrimes in my C# SieveOfEratosthenes type. I’ve implemented GetPrimes2 and you can find this in the code on Codeplex.

I’d also like to thank Rick for his write-up. I’d like to respond to a few of Rick’s comments. First up, I admit to being a “die hard C# fan” but I want to believe in F# too. Don’t hold back – tell us where we can make the F# code look better or run faster – we want your input! Rick also mentions that we’ve written single core code. That’s “by design”. We wanted to concentrate on the latest RTM version of C# and the “out of the box” install of F#. Parallel coding practices are definitely important, but we’re going to leave C# and F# parallel extensions to one side for the moment. We may well revisit this area in the future.

Limitations with Enumerable.Range


While implementing KFarmer’s suggestions I reminded myself of something that annoys me with Enumerable.Range. I’ve had several situations where I’d like to create a range of something other than int. Also, I’d sometimes like to express my ranges in some other way than by saying “start at i and generate n integers”. Sometimes I want to say “start at i and keep going until you get to j“. Yes, I know that a for loop would do this for me, but I long for something like range expressions in F#.

OK, Back to the Problems


So, as you know from the previous post we’re working our way though 6 problems from ProjectEuler.net. In this post we’re going to look at the just one problem:

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

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 25: What is the first term in the Fibonacci sequence to contain 1000 digits?


Full details of problem 25 can be found here.

To solve this problem you first need something that generates numbers from the Fibonacci sequence. Then, you want to find the first value in this sequence that’s bigger than or equal to 10999 (the first number with 1000 digits). At least, that’s what I set out to try and do, but with C# this proved to be a bit tricky. Let’s start with Giles’ F# solution.

F# Solution


Giles writes a function that generates numbers from the Fibonacci sequence, and keeps pulling on this until he finds a number that’s bigger than 10999 and then returns the length of that sequence (plus one) to determine the answer to the problem:

   1:  #light
   2:   
   3:  open Microsoft.FSharp.Math
   4:   
   5:  let fibonacci =
   6:      let rec fibonacciInner (a:BigInt) (b:BigInt) =
   7:          seq { let c = a + b   
   8:                yield c  
   9:                yield! fibonacciInner b c }
  10:      seq { yield 1I  
  11:            yield 1I  
  12:            yield! fibonacciInner 1I 1I }  
  13:            
  14:  let answerProblem (upto:BigInt) =
  15:          ( fibonacci  
  16:          |> Seq.take_while (fun (elem) -> elem < upto)   // The take_while stops one short
  17:          |> Seq.length ) + 1                             // so increment result
  18:          
  19:  let solve() = answerProblem (10I ** 999I)

A simple solution to this problem. Giles had to explicitly type some variables as BigInt to ensure that they weren’t inferred to be regular integer values, but other than that it pretty much reads as you’d expect it to.

C# Solution


I stumble at the first hurdle in C#. I want to define a variable that holds a value of 10999 but which type can I use? Int32 and Int64 (unsigned or otherwise) are inadequate. System.UInt64 will cater for a maximum value of 18,446,744,073,709,551,615. System.Decimal also falls short of the mark. Decimal can cope with a maximum value of 296-1.

So, what can you do if you need to deal with really large numbers in C#? Well, it turns out you can’t. You’re left with working around the problem, writing a type that can deal with large numbers, or borrowing a type from some language that does support really big numbers. J# is one such language, but we know F# is another. So, I ended up referencing FSharp.Core.dll and using the Microsoft.FSharp.Math.BigInt type in my solution!

   1:  public IEnumerable<BigInt> BigSequence
   2:  {
   3:      get
   4:      {
   5:          var a = BigInt.Zero;
   6:          var b = BigInt.One;
   7:          var c = a + b;
   8:   
   9:          while (true)
  10:          {
  11:              yield return c;
  12:   
  13:              c = a + b;
  14:              a = b;
  15:              b = c;
  16:          }                
  17:      }
  18:  }

So, I’ve managed to write a Fibonacci generator. But this isn’t the end of my problems. I want to keep pulling values from this generator until I get a value that’s bigger than 10999, but it’s not clear how I go about defining a value of 10999. Math.Pow is the normal way of doing this, but Math.Pow deals with doubles and doesn’t know how to deal with BigInt. So, I had to write my own function to raise a BigInt by a given power. I used a fast exponentiation method (rather than just performing n-1 multiplications) and defined it as an extension method on BigInt…

 


   1:  public static BigInt RaisedToThePowerOf(this BigInt value, int power)
   2:  {
   3:      if (power == 0)
   4:      {
   5:          return BigInt.One;
   6:      }
   7:   
   8:      // recursive call
   9:      var x = RaisedToThePowerOf(value, power / 2);
  10:   
  11:      if (power % 2 == 0)
  12:      {
  13:          return x * x;
  14:      }
  15:      
  16:      return value * (x * x);
  17:  }

 


… and from this was able to write my solution to the problem…


 



   1:  var ten = BigInt.FromInt32(10);
   2:  var first1000DigitNumber = ten.RaisedToThePowerOf(999);
   3:   
   4:  var answer = new Fibonacci().BigSequence
   5:                      .TakeWhile(x => x < first1000DigitNumber)
   6:                      .Count() + 1;



Phew! I got there in the end!


Conclusion


This isn’t a competition – we’re not looking for winners and losers. However, if this was a competition then it has to be a win for F#. The C# solution works, and I made it as pretty as possible, but it’s a butt-ugly hack compared to F# where dealing with large numbers works out of the box. C# just wasn’t up to the job when it came to dealing with big integers.

The one cool thing here is that I was able to borrow a type from F# very easily and with it get myself out of a sticky situation.

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.

Skip to main content
  1. bistok

    You don’t need to write the RaisedToThePowerOf the BigInt have the Method Pow 😉

  2. @bistok – Thanks! I hadn’t spotted it because it’s a static method on BigInt and not an instance method.

  3. Thank you for submitting this cool story – Trackback from DotNetShoutout

Comments are closed.