Refactoring Fibonacci Algorithm

Question

Hi, I haven't used a statically typed language in many years and have set myself the task of getting up to speed with C#. I'm using my usual trick of following the fifteen exercises here http://www.jobsnake.com/seek/articles/index.cgi?openarticle&8533 as my first task.

I've just finished the second Fibonacci task which didn't take to long and works just fine but in my opinion looks ugly and I'm sure could be achieved in far fewer lines of more elegant code.

I usually like to learn by pair programming with someone who already knows what they're doing, but that option isn't open to me today, so I'm hoping posting here will be the next best thing.

So to all the C# Jedi's out there, if you were going to refactor the code below, what would it look like?

using System;
using System.Collections;

namespace Exercises
{
 class MainClass
 {
  public static void Main(string[] args)
  {
   Console.WriteLine("Find all fibinacci numbers between:");
   int from = Convert.ToInt32(Console.ReadLine());
   Console.WriteLine("And:");
   int to = Convert.ToInt32(Console.ReadLine());
   Fibonacci fibonacci = new Fibonacci();
   fibonacci.PrintArrayList(fibonacci.Between(from, to));

  }
 }

 class Fibonacci
 { 
  public ArrayList Between(int from, int to)
  {    
   int last = 1;
   int penultimate = 0;
   ArrayList results = new ArrayList();
   results.Add(penultimate);
   results.Add(last);

   while(last<to)
   {
    int fib = last + penultimate;
    penultimate = last;
    last = fib;
    if (fib>from && fib<to) results.Add(fib.ToString());
   }
   return results;
  }

  public void PrintArrayList(ArrayList arrayList)
  {
   Console.WriteLine("Your Fibonacci sequence:");
   Console.Write(arrayList[0]);
   for(int i = 1; i<arrayList.Count; i++)
   {
    Console.Write("," + arrayList[i]);
   }
   Console.WriteLine("");
  }

 }
}

Regards,

Chris

Answer 1

As an iterator block:

using System;
using System.Collections.Generic;
using System.Linq;

static class Program {
    static IEnumerable<long> Fibonacci() {
        long n = 0, m = 1;

        yield return 0;
        yield return 1;
        while (true) {
            long tmp = n + m;
            n = m;
            m = tmp;
            yield return m;
        }
    }

    static void Main() {
        foreach (long i in Fibonacci().Take(10)) {
            Console.WriteLine(i);
        }
    }
}

This is now fully lazy, and using LINQ's Skip/Take etc allows you to control the start/end easily. For example, for your "between" query:

foreach (long i in Fibonacci().SkipWhile(x=>x < from).TakeWhile(x=>x <= to)) {...}

Answer 2

For those who haven't yielded to Linq-ed in like me, the 'Simple Jack' Version. i'm SO banned out of the Jedi club ;)

static List<int> GetAllFibonacciNumbersUpto(int y)
{
   List<int> theFibonacciSeq = new List<int>();

   theFibonacciSeq.Add(0);   theFibonacciSeq.Add(1);

   int F_of_n_minus_2 = 0;   int F_of_n_minus_1 = 1;
   while (F_of_n_minus_2 <= y)
   {
      theFibonacciSeq.Add(F_of_n_minus_1 + F_of_n_minus_2);

      F_of_n_minus_2 = F_of_n_minus_1;
      F_of_n_minus_1 = theFibonacciSeq.Last<int>();
   }
   return theFibonacciSeq;
}

now that we have that out of the way...

// read in some limits
int x = 0; int y = 6785;

foreach (int iNumber in GetAllFibonacciNumbersUpto(y).FindAll(element => (element >= x) && (element <= y)))
    Console.Write(iNumber + ",");
Console.WriteLine();

Answer 3

If you prefer recursion instead of the loop:

public static void Main(string[] args)
{
    Func<int, int> fib = null;
    fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;

    int start = 1;
    int end = 10;
    var numbers = Enumerable.Range(start, end).Select(fib);
    foreach (var number in numbers)
    {
        Console.WriteLine(number);
    }
}

Answer 4

I would change the IEnumerable<int> type to IEnumerable<Int64> as it will start to overflow from 50