2010-11-28 Performance in C# recursion vs. F#

2010-11-28 performance-in-csharp-recursion-vs-fsharp

# Title: Performance in C# recursion vs. F#
# Author: Mikael Lundin
# Link: http://blog.mikaellundin.name/2010/11/28/performance-in-csharp-recursion-vs-fsharp.html

E016.cs

private List<int> EvenOut(IEnumerable<int> numbers, int overflow)
{
    Func<IEnumerable<int>, bool> empty = list =>
        {
            var enumerator = list.GetEnumerator();
            return !enumerator.MoveNext();
        };
 
    if (empty(numbers))
    {
        if (overflow > 0)
            return new List<int> { overflow };
 
        return new List<int>();
    }
 
    var head = numbers.First();
    var n = (overflow + head) % 10;
    var newOverflow = (overflow + head) / 10;
 
    var result = EvenOut(numbers.Skip(1), newOverflow);
    result.Insert(0, n);
    return result;
}
 
private IEnumerable<int> Calc(IEnumerable<int> numbers, int exp)
{
    if (exp == 1)
        return numbers;
 
    return Calc(EvenOut(numbers.Select(n => n * 2), 0), exp - 1);
}
 
[Test]
public void Pe16()
{
    Assert.That(this.Calc(new[] { 2 }, 1000).Sum(), Is.EqualTo(1366));
}

E016.fs

let rec calc list exp =
    let rec evenOut overhead l =
        match (l, overhead) with
        | [], 0 -> []
        | [], _ -> [overhead]
        | head :: tail, _ -> ((overhead + head) % 10) :: (evenOut ((overhead + head) / 10) tail)
 
    match exp with
    | 1 -> list
    | _ -> calc (list |> List.map (fun x -> x * 2) |> evenOut 0) (exp - 1)
 
calc [2] 1000 |> List.sum

Whettingstone.cs

public static void Run()
{
 /*2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
   What is the sum of the digits of the number 2^1000?*/
 
 StringBuilder allDigits = new StringBuilder("1");
 int carryOver = 0;
 int temp;
 
 for (int i = 0; i < 1000; i++)
 {
  for (int index = 0; index < allDigits.Length; index++)
  {
   //Multiply the digit by two
   temp = int.Parse(allDigits[index].ToString()) * 2;
 
   if (temp > 9)
   {
    //The result is 10 or larger so add digit and set carryOver
    allDigits.Remove(index, 1);
    allDigits.Insert(index, (temp % 10) + carryOver);
    carryOver = 1;
   }
 
   if (temp <= 9)
   {
    //The result is less than 10 so add digit and reset carryOver
    allDigits.Remove(index, 1);
    allDigits.Insert(index, temp + carryOver);
    carryOver = 0;
   }
 
   if ((index == allDigits.Length - 1) && carryOver == 1)
   {
    //This is the last index so add the carryOver to the StringBuilder and break the loop
    allDigits.Append(carryOver);
    carryOver = 0;
    break;
   }
  }
 }
 
 //Calculation is done, let's sum it up
 int sum = 0;
 
 for (int i = 0; i < allDigits.Length; i++)
 {
  sum += int.Parse(allDigits[i].ToString());
 }
 
 Console.WriteLine("Sum of 2^1000: {0}", sum);
}