Fibonacci Sequence Generator generates 1 million numbers

Question

A FibonacciSequenceGenerator in C# looking for speed improvements. Currently generates 1 million numbers in 25.6 seconds.

We must use BigInteger because the millionth value of the fibonacci sequence is to large to be of type int, long or even ulong. The result is 321,851,935,320,379,656,981,593,474,058,423,769,576,631,910,586,124,350,734,165,842,941,925,697,016,841,709,864,286,954,963,999,053,893,210,468,451,823,262,689,301,306,354,971,797,888,450,164,394,326,059,611,966,197,395,383,319,235,950,480,124,291,916,245,341,634,240,900,324,421,701,713,313,536,116,741,151,743,685,386,112,679,838,085,751,595,026,298,237,888,310,581,559,936,076,376,732,277,717,878,156,239,165,063,784,311,584,934,950,615,070,580,050,766,101,316,621,663,659,924,168,685,017,274,539,048,501,732,419,659,165,366,739,643,571,036,629,605,128,578,575,406,399,390,382,232,885,973,323,204,930,777,394,811,232,955,491,515,525,136,802,939,173,659,827,568,760,916,113,567,628,946,853,363,287,878,329,995,694,272,856,105,316,964,407,030,712,526,846,366,787,342,274,072,376,747,074,044,654,480,541,848,128,317,663,973,778,045,391,111,390,939,319,791,802,953,057,217,582,860,428,225,412,543,991,616,189,585,681,051,405,547,609,150,015,743,785,653,005,260,331,629,522,108,003,916,074,509,262,836,314,172,778,883,659,535,102,587,911,419,872,025,962,380,687,123,573,280,832,406,684,390,626

---

public readonly struct FibonacciSequenceGenerator(int n) : IEnumerable<BigInteger>
{       

public readonly IEnumerator<BigInteger> GetEnumerator()
{            
    BigInteger a = 0, b = 1, next;
    for (BigInteger i = 0; i < n; i++)
    {
        yield return a;
        next = a + b;
        a = b;       
        b = next;                
    }        
}

readonly IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

Changing my GetEnumerator() to the below cuts the time to 12 seconds

public readonly IEnumerator<BigInteger> GetEnumerator()
{            
    BigInteger a = 0, b = 1, i = 0, next;
    for (; i < n; i++)
    {
        yield return a;
        next = a + b;
        a = b;       
        b = next;                
    }        
}

Answer 1

Caveat: I don't work with C# (or with its BigInteger facilities) meaning this "answer" is speculative, noting the use of 3 variables and several transfer operations during each of a million iterations. Nothing comes for free.

---

Consider a visual stepwise 'unrolling' of the formula:

                             f(n) =   f(n-1) + f(n-2); // 1st iteration
                    f(n) =   f(n-1) + f(n-2); // 2nd iteration
            f(n) =  f(n-1) + f(n-2); // 3rd iteration
    f(n) = f(n-1) + f(n-2); // 4th iteration

At each step f(n-2) contributes to the sum, but then becomes irrelevant.
Recycling that variable (a complex BigInteger) may yield value by not introducing a 3rd variable:

    f(n-2) += f(n-1); // 1st iteration
    f(n-2) += f(n-1); // 2nd iteration // note: an 'even' iteration
    f(n-2) += f(n-1); // 3rd iteration
    f(n-2) += f(n-1); // 4th iteration // another 'even' iteration
    ...

The OP's code achieves this by shuffling values between a and b while using next as a temporary buffer, and looping n times. (Likely calculating the "one million and two-th" Fib no...)

---

Consider this (low quality) representation of the effect of beginning the sequence with either 0, 1 or 1, 1:

        o   e   o   e   o   e   o
0   1   1   2   3   5   8  13  21 ... // Start with 0 & 1. f(0) & f(1)
  /   /   /   /   /   /   /   /       // shifting
1   1   2   3   5   8  13  21 ...     // Start with 1 & 1. f(1) & f(2)
        e   o   e   o   e   o

The 'e' and 'o' markings label the expected values when n is 'even' or 'odd'.
2, 5 and 13 all appear after an 'even' number (a 'pair') of iterations.

---

Given is f(0) = 0 and f(1) = 1 (and dispense with the trivial request to calculate f(2)). Then, the first interesting value will be that of f(3).

Let's also propose the body of the loop ALWAYS executes a pair of operations.

    {
        a += b;
        b += a;
    }

It's also important to distinguish the meaning of the OP's "million".
Does that mean the 1,000,000th Fibonacci number?
Or, does that mean 1,000,000 iterations (yielding the 1,000,002th number)?
For the purpose of this silly exercise, I'm using the first interpretation, as one might then be able to attach some significance to its exact value.

The simple code will run pairs of computations.
Each iteration leaves the result in the variable b.
If n is even we seed a and b with 0, 1.
If n is odd the seeds are 1, 1.
If n is odd reduce n by 1 as the starting seeds (1,1) already represent the first iteration's result. Further reduce n by 2 (for those first two seeds) and jump in (with pseudo code)...

    BigInteger a = n%2, b = 1; // 'a' begins as 0 (n is even) or 1 (n is odd)
     // Make odd even by subtracting 1 before beginning, and first 2 are given
    for( n -= (2 + a); n; n -= 2 ) {
        a += b;
        b += a;
    }
    // b now contains the result

---

The above eliminates millions of variable updates and halves the number of iterations of the loop.

Perhaps this might execute just a smidgen faster.

---

FWIW

I've a pet project utilising BCD addition (vastly simplifying the reporting of massive decimal values.) Coding it to fill 64 decimal digits reveals that the 300th Fibonacci number to be:
137347080577163115432025771710279131845700275212767467264610201
There's room for a few more iterations before I'd need to use 65 decimal digits.

Obviously, even in a binary BigInteger representation, this requires quite a few bits for each accumulator. And, this is only going to the 300th FibNo...

While I've no doubt the BigInteger routines are finely tuned for correctness and for performance, the size of the data values to reach the millionth FibNo will be cumbersome.

What's the point of writing a (long running) function to tax the CPU, then seeking to optimise that function to run faster? This answer only reveals that I have far too much time on my hands these days!

---

EDIT: the 64 digit number checks out with this OEIS list, except that I have used counting numbers to call it the 300th. The list has this FibNo at position 299 (zero based).

---

Final observations

Scanning the length of the numbers in the Fibonacci sequence, roughly every 5 numbers another decimal digit (power of 10) is required. This is corroborated by the approximate quotient of the 300th FibNo requiring 64 digits (~1/5).

From this, one can estimate that the millionth FibNo would require something more than 200,000 decimal digits to express.

Based on this, and an approximation of 3.5 bits to express each decimal digit of a large number, those approx. 200,000 decimal digits would require each BigInteger (a and b and next) to eventually store and process something like 100,000 bytes for each operation (summing or copying).

It can be safely presumed, too, that the BigInteger support grows its allocated storage to meet requirements (multiple calls to realloc()?).

In short, this feels like a frivolous expenditure of machine cycles for questionable purposes. Who would ever seek to print the entire ~200,000 digits of the millionth Fibonacci number?!

Answer 2

Iteration variable

The most obvious change is that the iteration variable itself doesn't need to be a BigInteger.

A simple int, being a signed 32-bits integer, has an upper limit of 2³¹ - 1, or 2 billions. If takes ~12s to run 1 million iterations, this single int will already be sufficient for over 6 hours.

But if you're really worried, use a long, which as a signed 64-bits integer, will be large enough to run this function until the heat death of the universe.

Or in code:

public readonly IEnumerator<BigInteger> GetEnumerator()
{            
    BigInteger a = 0, b = 1, next;
    for (long i = 0; i < n; i++)
    {
        yield return a;
        next = a + b;
        a = b;       
        b = next;                
    }        
}

(You'd need to adapt the constructor to take long n)

This simple change will already reduce one BigInteger operation per iteration, which should speed things up.

Answer 3

One of my big learning in programming was that the most elegant is not always the fastest.

If you need to frequently calculate big Fibonacci numbers, the fastest way is probably to hard code some of them in your algorithm (e.g. 50,000th, 50,001st, 100,000th, 100,001st...)

This way you'll just need to look for the last stored numbers before your target and get your target with at most 50,000 iterations of your algorithm