Calculating Fibonnaci sequence lazily

Question

Implementation:

IEnumerable<BigInteger> Fibs()
{
 BigInteger a = 0;
 BigInteger b = 1;
 while(true)
 {
 b = a + (a = b);
 yield return a;
 }
}

Usage:

void Main()
{
 // take first 100 fib numbers
 var fibs = Fibs().Take(100);
}

How can I improve this?

Answer 1

That's a pretty clever implementation. To improve this, I would take some of the cleverness out of it. In particular:

while (true)
{
 BigInteger next = a + b;
 a = b;
 b = next;
 yield return next;
}

2 lines longer, but no unnecessary cleverness. Perfectly clear, nice and simple, and should be just as efficient. It's good general rule to not try to be too clever. Keep it simple.

Also, FibonacciSequence would be a better name than Fibs.

Finally, as a tiny remark, put a space before opening parenthese of the while condition (like I did above, different from the original code).

• svick: Why not yield return as soon as you calculate next?

Answer 2

The Fibonacci sequence is just one of many generalized Fibonacci sequences. You can get extra flexibility for the same amount of work by taking default parameters.

IEnumerable<BigInteger> Fibs(BigInteger a=0, BigInteger b=1)
{
 while(true)
 {
 b = a + (a = b);
 yield return a;
 }
}

Bonus: you've saved two lines of code — whether or not you take @janos's advice to reduce the cleverness. ☺

However, it would be awkward to yield the sum of the parameters a and b as the first result. I'd expect it to yield a, then b, as the first two results.

IEnumerable<BigInteger> Fibs(BigInteger a=1, BigInteger b=1)
{
 while(true)
 {
 yield return a;
 b = a + (a = b);
 }
}

With that, you can use Fibs(0, 1) to obtain a Fibonacci sequence starting with 0:

0, 1, 1, 2, 3, 5, ...

Also, while Fibonacci numbers famously appear in plant growth patterns, it's less well known that sometimes other sequences appear, such as Fibs(1, 3):

1, 3, 4, 7, 11, 18, ...

• Rezo Megrelidze: for(BigInteger a = 0,b = 1;;b = a + (a = b)) yield return b
• 200_success: No, that for loop implements the opposite of my suggestions. I don't like it.
• Rezo Megrelidze: I didn't know about other fibonnaci sequences.
• Rezo Megrelidze: I like your review.
• svick: You can't set parameter defaults like that: "A value of type 'int' cannot be used as a default parameter because there are no standard conversions to type 'System.Numerics.BigInteger'." I would probably use Nullable: IEnumerable<BigInteger> Fibs(BigInteger? a = null, BigInteger? b = null).

Answer 3

Agree with the other answers here, but one more thing to add:

Are you sure you want to use while(true)? The answer may very well be yes, but this StackOverflow answer highlights some things to consider when using an "infinite" enumerator.

For example, Min, Max, Average, etc. methods will not fail gracefully. In the linked answer, Marc suggests adding a SanityCheck extension method that just puts an upper limit on how many iterations it'll process before throwing its hands in the air and calling it an invalid operation (or simply taking a max iterations argument to the method).

Answer 4

In case you need random access to Fibonacci numbers, one approach is to calculate them once and store them in an array for fast access later on.

public static BigInteger[] GetFibonacciArray(int n) 
{
 BigInteger[] a = new BigInteger[n];
 a[0] = new BigInteger(0);
 a[1] = new BigInteger(1);
 for (int i = 2; i < n; i++)
 a[i] = BigInteger.Add(a[i-1], a[i-2]);
 return a;
}