Everyone loves Fibonacci

Question

I was bored and burnt out on more serious projects.... until I saw this Computerphile video on YouTube. Now I'm inspired again. Now I feel like spending some time implementing that recursive algorithm in a little console program. Fortunately, recursion is unbearably slow in this case. So, I ended up writing a small class that implements a loop algorithm to find any \$F_n\$.

I'm just learning C#, so I'm most concerned with best practices and style. I want to get a good foundation though, so all feedback is welcome.

Particular Concerns

• Is my indentation correct?
• Have I named my variables horribly? (I think they smell a bit.)
• Which implementation is better? I'm feeling like it's six of one or a half doz. of the other.
• Should I be concerned about hitting the upper boundary of the ulong type? Fibonacci numbers grow very quickly. Is there a better representation of very large numbers?

Fibonacci

class Fibonacci
{
    private int _n;
    private ulong _value;
    private ulong _FnMinus1;
    private ulong _FnMinus2;

    public int n 
    {
        get { return _n; }
        set { _n = value; } 
    }

    public ulong Value 
    { 
        get {return _value;}
        //set { _value = value; }
    }

    public void Calculate() 
    { 
        if (n <= 0)
        {
            throw new ArgumentOutOfRangeException("n","Can't calculate Fn when n is less than or equal to zero.");
        }
        else if (n == 1 || n == 2)
        {
            _value = 1;
        }
        else
        {
            //initialize previous results
            _FnMinus1 = 1;
            _FnMinus2 = 1;

            for (int i = 0; i <= (n - 2) ; i++)
            {
                _value = _FnMinus1 + _FnMinus2;
                _FnMinus2 = _FnMinus1;
                _FnMinus1 = _value;
            }
        }
    }

    //constructors
    public Fibonacci(int n)
    {
        _n = n;
        Calculate();
    }

    public Fibonacci() { }

}

Implementation1

class Program
{
     static void Main(string[] args)
    {

        Fibonacci fib = new Fibonacci();
        for (int i = 1; i <= 50; i++)
        {
            fib.n = i;
            fib.Calculate();
            Console.WriteLine(fib.Value);
        }

        Console.WriteLine("Press enter to close...");
        Console.ReadLine();
    }
}

Implementation2

class Program
{
     static void Main(string[] args)
    {

        for (int i = 1; i <= 50; i++)
        {
            Fibonacci fib = new Fibonacci(i);
            Console.WriteLine(fib.Value);
        }

        Console.WriteLine("Press enter to close...");
        Console.ReadLine();
    }
}

Update: Follow up question here.

Answer 1

Indentation and formatting are fine, as is the algorithm itself.

Your naming is inconsistent, compare n and Value; _value and _FnMinus1. There are a variety of conventions to follow, but consistency is the most important thing.

_FnMinus1 and _FnMinus2 are only used in one method, so they can be made local to that method.

The API is a little odd:

fib.n = i;
fib.Calculate();
int result = fib.Value;

It would be more convenient if I could do this with one line, like int result = fib.Calculate(i), which would return the value. Then it seems that n and Value are unnecessary.

Furthermore, right now there is nothing that keeps n and Value synchronized. The class should maintain the invariant that Value is always the nth Fibanacci number. You could do the work in the n assignment or mark Value as dirty when n changes. Either way you essentially get rid of Calculate, so that's another approach. I prefer getting rid of n and Value, I just mention this in case you think it makes sense to keep them.

Between Implementation 1 and Implementation 2, it's pretty much a wash. 1 has the benefit of only making one allocation. Since the class is (going to be) stateless, it's perfectly reusable. On the other hand 2 declares fib inside the loop, which minimizes its scope (which is good).

Answer 2

Microsoft's .NET style guide recommends against the use of underscores or any Hungarian notation in identifiers.

You're right that overflow will occur for large enough values of n. It is possible to avoid overflow by using System.Numerics.BigInteger. However, that adds a lot of clutter to your program, and is more tedious than you would probably like for a simple educational project.

I think you've missed an important point about object-oriented programming, which is that objects should keep themselves in a self-consistent state. You've exposed Calculate() as a public method, and you expect callers to call Calculate() before fetching .Value. That's an unfair burden on callers, and they may neglect to do so. Rather, a better design would have the .Value getter automatically recalculate if necessary. (The Calculate() method should be private.) An even smarter design would continue where the previous calculation left off (rather than starting from scratch) if n has not decreased since the previous call to .Value.

Answer 3

Class Design

Some of class design is a matter of doing what will cause the least surprise to others. There is nothing functionally wrong with passing the value into the constructor and reading the answer from a value, or in explicitly setting the count, can calculating; they both work; but a more expected shape would be along the lines of

public class Maths {
    public long CalculateFibbonacci(int count){
      // return the calculated value
    }
}

which would make the usage

class Program {
    static void Main(string[] args) {
        var fib = new Fibbonacci();
        for (var i = 1; i <= 50; i++) {
           Console.WriteLine(fib.Calculate(i));
        }
        Console.WriteLine("Press enter to close...");
        Console.ReadLine();
    }
}    

Or one could make it a static function in a static class (though, I tend to avoid these as they hinder unit testing). The class as designed (adding extra steps to use class members - n, value) smacks of It's an OO language so one should use a class.

NOTE:

Although there is nothing functionality wrong with either, if used properly, the

fib.n = i;
fib.Calculate();
Console.WriteLine(fib.Value);

usage has so many dependent steps that it is very error prone in usage and I would really push for not using it.

Coding Style

Indentation, spacing, bracket position et al. can be considered religious issues that cause endless bickering. There is a value to having a single style across a codebase because it makes things simpler for reading/reviewing. It is also tedious when two team members have different styles set in their editors and keep changing spacing, bracket position for the whole file every time they make any change, but THERE IS NO ONE TRUE STYLE many different styles have developed and the most popular mainstream ones all have their pluses and minuses.

So, if one is working with other people and the majority/consensus style is not totally ludicrous, one should suck it up and use the common style.

That all said, the current code style looks good. It is clear and readable.

Public members of a class should be Pascal Cased and descriptive. n is a bad name for a public member. It tells the user nothing about its meaning or usage.

Hitting Limits

For what do you want to use this code?

If it is a programming exercise to check coding styles and designs then unless 'dealing with large numbers' is one of the design aspects that you wish to address, I wouldn't worry about the result getting too large.

If it has some real world usage then check this usage, to see if it is likely to overflow and if it is, then worry about it. Worrying about it unless there is a solid need can be considered a form of Premature Optimization

Answer 4

The answers to most of your questions have been given and aside from consistency in naming and using BigInteger there's not much more to say to the questions however A more general comment would be that Fibonacci sequences makes for an odd class. It's a function more than a class and what you've implemented is basically a way to curry the argument to the function and that leeds to a somewhat odd class design. Not because your design is odd but because the tool is not the best one for the task. If you are modelling a function as a class where does the result then go? as a calculated property or the return value of the single method?

So instead of modelling a function that returns the n-th number you could create a class that represents a fibonacci sequence

class FibonacciSequence : IEnumerable<BigInteger>
{

    IEnumerator<BigInteger> IEnumerable<BigInteger>.GetEnumerator()
    {
        BigInteger prev1 = 1;
        BigInteger prev2 = 1;
        yield return 1;
        yield return 1;
        while (true)
        {
            var next = prev1 + prev2;
            yield return next;
            prev1 = prev2;
            prev2 = next;
        }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return ((IEnumerable<BigInteger>)this).GetEnumerator();
    }
}

you could then use it like this

new FibonacciSequence().Take(2).Last();

to get the second number in the sequence. Of course you could use memoization and an indexer to speed up consequetive calls. The below does that (not thread safe)

class FibonacciSequence : IEnumerable<BigInteger>
{
    List<BigInteger> list = new List<BigInteger> { 1, 1 };

    IEnumerator<BigInteger> IEnumerable<BigInteger>.GetEnumerator()
    {
        return list.Concat(iterate()).GetEnumerator();   
    }

    IEnumerable<BigInteger> iterate()
    {
        BigInteger prev1;
        BigInteger prev2;
        prev1 = list[list.Count - 2];
        prev2 = list[list.Count - 1];
        while (true)
        {
            var next = prev1 + prev2;
            list.Add(next);             
            yield return next;
            prev1 = prev2;
            prev2 = next;

        }
    }

    public BigInteger this[int index]
    {
        get
        {
            if (index >= list.Count)
            {
                list.AddRange(iterate().Take(index - list.Count + 1));
            }
            return list[index];
        }

    }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return ((IEnumerable<BigInteger>)this).GetEnumerator();
    }
}