Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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.

share|improve this question
    
Check out this Fibonacci implementation while you are at it :) –  Alexei Levenkov Jun 20 at 1:01
3  
For big integers indeed us BigInteger class. –  Alexei Levenkov Jun 20 at 1:03
    
Interesting @AlexiLevenkov. I wonder how well it performs. –  ckuhn203 Jun 20 at 1:10
6  
This one has to be be nominated in the Best Question Title category! –  Mat's Mug Jun 20 at 11:36
1  
@Vogel612 Of course integer (ulong that is) overflow: System.OverflowException: Arithmetic operation resulted in an overflow. Just change the limit in the for loop in the implementation 1 and you will get an exception; unless it's run in an unchecked environment, in which case it overruns happily and silently and just gives out a wrong answer. –  abuzittin gillifirca Jun 20 at 12:04

4 Answers 4

up vote 21 down vote accepted

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).

share|improve this answer
    
Yeah. I broke a golden rule. I implemented features before they were actually needed. Thank you. –  ckuhn203 Jun 19 at 23:53
2  
If you're going to have a stateless class, you might as well make it static. –  svick Jun 20 at 2:02
1  
@svick I agree in this specific case. In general making classes/functions static can prevent DI or other types of polymorphism, so I don't think it's a rule that should be stressed to novices. –  Pierre Menard Jun 20 at 15:24

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.

share|improve this answer
    
The underscores I get, but I haven't used any Hungarian notation. Fn is mathematical notation. I still don't like those names though. I do need something better. –  ckuhn203 Jun 20 at 2:38
1  
Your question didn't contain Hungarian notation. I mentioned Hungarian notation pre-emptively, in case you had the idea of using prefixes, as in mValue instead of _value. –  200_success Jun 20 at 2:41
    
Ahhh. Ok. Thank you. I was obviously confused. –  ckuhn203 Jun 20 at 2:41
1  
Careful with recommending against Hungarian. The practice being frowned upon is embedding type name in variable name, and the original Hungarian (the actually useful one) was about embedding logical meaning in the name. en.wikipedia.org/wiki/Hungarian_notation –  Kos Jun 20 at 14:23
    
@Kos according to that link, Hungarian notation was originally conceived as a solution for type less languages. In fact, the only time I recommend it myself is for VBScript. Hungarian notation should be burnt with fire. –  ckuhn203 Jun 20 at 22:20

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

share|improve this answer
    
I'll be using this in some puzzles later, so large numbers are a concern. I agree that n is a bad name, but it's not Hungarian notation. It's mathematical notation. F sub n. I'm open to suggestions for a better one. –  ckuhn203 Jun 20 at 11:09
1  
I was actually thinking of the _FnMinus1, _FnMinus2 for the Hungarian, but it looks like I was off - they are just abbreviations. My Bad. I'll update the answer. As for n: that there is no better name for it does give a hint that it is not a great fit for a member. If we take it out and use the function version of calculate long Calculate(int n), then n as a the name of a parameter to the function comes under 'the sort of thing people expect' –  AlanT Jun 20 at 11:55
    
I think I've got a good one. Ordinal Position, but I need to think about how I want the API to work. I'm wondering if there's ever a need to expose N to anything outside of Fibonnacci. –  ckuhn203 Jun 20 at 11:59
1  
As I said, splitting the API into too many steps is dubious and there is no need for it here. Instead of { Create, Set OrdinalPostion, Invoke Calculate, Read Result}, we can {Create, Invoke Calculate Passing in Ordinal Position and Reading result } This way, there is no need to store / expose either Ordinal Position or Value(Result) in the class –  AlanT Jun 20 at 12:03
    
I took care of the issue where the class expects its client to keep it in sync. I'm thinking now of whether or not to keep OrdinalPosition and Value hidden away or to implement just a public Calculate() function. Thank you for your input. I'll probably post a follow up once I've figured out how I want to handle it. –  ckuhn203 Jun 20 at 15:28

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();
    }
}
share|improve this answer
    
That is absolutely fantastic advice. Thanks. –  ckuhn203 Jun 24 at 13:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.