7
\$\begingroup\$

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?

\$\endgroup\$
11
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Why not yield return as soon as you calculate next? \$\endgroup\$ – svick Oct 15 '14 at 19:46
4
\$\begingroup\$

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, …

\$\endgroup\$
  • \$\begingroup\$ for(BigInteger a = 0,b = 1;;b = a + (a = b)) yield return b; \$\endgroup\$ – Raz Megrelidze Oct 15 '14 at 13:06
  • \$\begingroup\$ No, that for loop implements the opposite of my suggestions. I don't like it. \$\endgroup\$ – 200_success Oct 15 '14 at 14:31
  • \$\begingroup\$ I didn't know about other fibonnaci sequences. \$\endgroup\$ – Raz Megrelidze Oct 15 '14 at 15:06
  • \$\begingroup\$ I like your review. \$\endgroup\$ – Raz Megrelidze Oct 15 '14 at 15:52
  • \$\begingroup\$ 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). \$\endgroup\$ – svick Oct 15 '14 at 19:48
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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