[C/C++] Project Euler #25 1000-digit Fibonacci Number

When learning C/C++ programming, one of the things everyone seems to try at least once is implementing the Fibonacci sequence. The Fibonacci sequence often appears in examples involving recursive functions and is also a frequent example for dynamic programming problems.

The Fibonacci sequence originated from a quiz-like scenario about the growth of a rabbit population. However, it can also be applied to problems like bacterial growth. It exhibits exponential growth, following a geometric progression.

The Fibonacci sequence is defined by a very simple recurrence relation:

\[ F_{n+2} = F_n + F_{n+1} \]

This recurrence relation is straightforward: the value of the current term is the sum of the two preceding terms.

As such, the first and second terms must be provided as initial values. The first term is 1, and the second term is also 1. The sequence progresses in the domain of natural numbers. While it is possible to extend the sequence into negative indices, we’ll only deal with positive indices here.

Although the recurrence relation is simple, finding the general term of the sequence is a bit tricky. The mathematical derivation is not our focus here, so we’ll skip it. Here’s how the general term can be derived:

\[ F_{n+2} - F_{n+1} - F_n = 0 \]
\[ z^2 - z - 1 = 0 \]
\[ (z - \alpha)(z - \beta) = 0 \]

From this, we can determine two distinct roots using the quadratic formula. These roots correspond to the values associated with the golden ratio, which might partly explain the Fibonacci sequence’s fame (along with concepts like Fibonacci primes).

\[ x = \frac{1 \pm \sqrt{1^2 + 4}}{2} = \frac{1 \pm \sqrt{5}}{2} = \phi, 1 - \phi \]

Once these roots are determined, the general term of the Fibonacci sequence can be expressed as:

\[ F_n = \frac{1}{\sqrt{5}}(\phi^n - (1-\phi)^n) \]

In cases where a program requires calculating large Fibonacci terms, this general formula is extremely useful.

A program implementing the general term of the Fibonacci sequence can handle terms within the INT64 range using this formula. However, since double precision is used, there may be minor inaccuracies for very large values.

For problems like finding the first Fibonacci term with 1000 digits, it is more practical to use this formula in combination with logarithms. Using logarithms simplifies the calculation of the number of digits. For a 1000-digit number, we need to calculate approximately \(10^{999}\).  Additionally, when looking at the Fibonacci sequence, the powers of the golden ratio become dominant compared to the second term as n grows larger.  This is because the golden ratio (approximately 1.618) minus 1 is 0.618, a value less than 1 that approaches 0 as n increases.

Using this insight, the program becomes very simple and extremely fast. If we attempted to calculate everything manually using a big integer library, it would require significantly more computational time compared to standard integer operations (though still manageable).

 

Fibonacci sequences

The code provided below is for reference only. It may be difficult to understand just by looking at the source code because it incorporates mathematical concepts.

//------------------------------------------------
//    Project Euler #25 - 1000-digit Fibonacci Number
//        - by Aubrey Choi
//        - created at 2015-01-26
//------------------------------------------------
#include <stdio.h>
#include <math.h>

int main()
{
    double logphi = log10((1.0+sqrt(5.0))/2);
    double log5 = 0.5*log10(5);

    printf("Ans = %d\n", (int)((999.0+log5)/logphi)+1);
}