Project Euler Attack #2

Question

This is my implementation of Project Euler #2 in C#. It takes 0 milliseconds to run, and I believe it is correct - I have seen nothing to indicate otherwise!

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

static void GetFibos(ref List<int> nums, int maxVal)
{
    nums.Add(1);
    int lastNum = 2;

    while (lastNum <= maxVal)
    {
        nums.Add(lastNum);
        lastNum = nums[nums.Count - 2] + nums[nums.Count - 1];
    }
}

static void Main(string[] args)
{
    Stopwatch s = new Stopwatch();
    s.Start();

    List<int> fiboNums = new List<int>();
    GetFibos(ref fiboNums, 4000000);

    int sumEvenFibos = 0;

    foreach (int i in fiboNums) { if (i % 2 == 0) sumEvenFibos += i; }

    s.Stop();

    Console.WriteLine(sumEvenFibos);
    Console.WriteLine(s.ElapsedMilliseconds);
}

Is there anything I should be doing different?

Answer 1

Why do you need the actual list of Fibonacci numbers? That just requires space, and time.

Believe it or not, you have over-thought this problem. Additionally, your code style is off.

C# Code conventions always use braces for single-statement blocks, and the brace should open at the start of a new line. Code like:

foreach (int i in fiboNums) { if (i % 2 == 0) sumEvenFibos += i; }

should be:

foreach (int i in fiboNums)
{
    if (i % 2 == 0)
    {
        sumEvenFibos += i;
    }
}

As for the list, you don't need it:

int current = 1;
int previous = 0;
int sum = 0;
while (current <= 4000000)
{
    if ((current % 2) == 0)
    {
        sum += current;
    }
    int tmp = current + previous;
    previous = current;
    current = tmp;
}

Now, that whole thing should be put in its own function, and your main method with a parameter for the upper limit (4,000,000) and it becomes:

static void Main(string[] args)
{
    Stopwatch s = new Stopwatch();
    s.Start();

    int sumEvenFibos = GetFiboSum(4000000);

    s.Stop();

    Console.WriteLine(sumEvenFibos);
    Console.WriteLine(s.ElapsedMilliseconds);
}

Answer 2

1. This:

   List<int> fiboNums = new List<int>();
   GetFibos(ref fiboNums, 4000000);
   

   looks like a C++-ism. In C# you have value types (struct) and reference types (class). List<T> is a class and thus passing it by ref doesn't gain you anything unless you want to replace the list object with a different one. If anything GetFibos should create the list, fill it and then return it.

2. GetFibos could be better named like GetFibonacciNumbers.

3. As @rolfl pointed out you don't actually need to store all the numbers - you can just generate them as a sequence with an enumerator and then do your processing on the resulting sequence:

   public IEnumerable<int> GetFibonacciNumbers(int max)
   {
       int current = 1;
       int previous = 0;
       while (current <= max)
       {
           yield return current;
   
           int tmp = current + previous;
           previous = current;
           current = tmp;
       }
   }
   

   Now you can combine this with some LINQ in order to calculate what you want:

   var sumOfAllEven = GetFibonacciNumbers(4000000).Where(n => n % 2 == 0).Sum();