Fibonacci Sequence

Posted on | In ,

Definition

The Fibonacci sequence is defined by each number being the sum of the two preceding ones. Formally, the Fibonacci sequence $a$ is defined as follows.

$a_1 = a_2 = 1$, $a_n = a_{n - 1} + a_{n - 2} \forall n \ge 3$.

The Fibonacci sequence has the following closed form.

$a_n = a_{n-1} + a_{n-2}$

$\Leftrightarrow a_n + (\frac{\sqrt{5}-1}{2})a_{n-1} = (\frac{\sqrt{5} + 1}{2})(a_{n-1} + (\frac{\sqrt{5}-1}{2}) a_{n-2})$

$\Leftrightarrow a_{n+1} + (\frac{\sqrt{5}-1}{2})a_n = (\frac{\sqrt{5} + 1}{2})^{n - 1}(a_2 + (\frac{\sqrt{5}-1}{2})a_1) = (\frac{\sqrt{5} + 1}{2})^n$

$\Leftrightarrow a_{n+1} - \frac{1}{\sqrt{5}}(\frac{\sqrt{5} + 1}{2})^{n+1} = -(\frac{\sqrt{5}-1}{2})(a_n - \frac{1}{\sqrt{5}}(\frac{\sqrt{5} + 1}{2})^n)$

$\Leftrightarrow a_n - \frac{1}{\sqrt{5}}(\frac{\sqrt{5} + 1}{2})^n = (-(\frac{\sqrt{5}-1}{2}))^{n-1}(a_1 - \frac{1}{\sqrt{5}}(\frac{\sqrt{5} + 1}{2})) = -\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$

As a result, $\Leftrightarrow a_n = \frac{1}{\sqrt{5}}(\frac{\sqrt{5} + 1}{2})^n - \frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$

or

$a_n = a_{n-1} + a_{n-2}$

$\Leftrightarrow a_n - (\frac{\sqrt{5}+1}{2})a_{n-1} = (\frac{1 - \sqrt{5} }{2})(a_{n-1} - (\frac{\sqrt{5}+1}{2}) a_{n-2})$

$\Leftrightarrow a_{n+1} - (\frac{\sqrt{5}+1}{2})a_n = (\frac{1 - \sqrt{5}}{2})^{n-1}(a_2 - (\frac{\sqrt{5}+1}{2})a_1) = (\frac{1 - \sqrt{5}}{2})^n$

$\Leftrightarrow a_{n+1} - (\frac{\sqrt{5}+1}{2})a_n = (\frac{1 - \sqrt{5}}{2})^n$

$\Leftrightarrow a_{n+1} + \frac{1}{\sqrt{5}}(\frac{1 - \sqrt{5}}{2})^{n+1}= (\frac{\sqrt{5}+1}{2})(a_n + \frac{1}{\sqrt{5}}(\frac{1 - \sqrt{5}}{2})^n)$

$\Leftrightarrow a_n + \frac{1}{\sqrt{5}}(\frac{1 - \sqrt{5}}{2})^n = (\frac{\sqrt{5}+1}{2})^{n-1}(a_1 + \frac{1}{\sqrt{5}}(\frac{1 - \sqrt{5}}{2})) = \frac{1}{\sqrt{5}}(\frac{\sqrt{5}+1}{2})^n$

$\Leftrightarrow a_n = \frac{1}{\sqrt{5}}(\frac{\sqrt{5}+1}{2})^n - \frac{1}{\sqrt{5}}(\frac{1 - \sqrt{5}}{2})^n$

As a result, $a_n = \frac{1}{\sqrt{5}}((\frac{\sqrt{5}+1}{2})^n - (\frac{1 - \sqrt{5}}{2})^n)$

Implementation

Recursion

The most naive and simplest implementation.

1
2
3
4
unsigned int fib(unsigned int x){
   if(x == 1 || x == 2) return 1;
   return fib(x - 1) + fib(x - 2);
}

Dynamic programming

Top-down approach

1
2
3
4
5
6
7
8
9
10
11
12
//Top-down approach
vector<unsigned int> lst;//3 <= 0
unsigned int fib(unsigned int x){
    if(x == 1 || x == 2) return 1;
    if(x - 3 < lst.size() && lst[x-3] != 0){
        return lst[x-3];
    }
    for(int i = lst.size(); i < x; ++i)
        lst.push_back(0);
    lst[x-3] = fib(x - 1) + fib(x - 2);
    return lst[x-3];
}

Bottom-up approach

1
2
3
4
5
6
7
8
9
10
//Bottom-up approach
unsigned int fib(unsigned int x){
  unsigned int lst[x];
  lst[0] = 1;
  lst[1] = 1;
  for(int i = 2; i < x; ++i){
    lst[i] = lst[i - 1] + lst[i - 2];
  }
  return lst[x - 1];
}

Mathematical Analysis

From the closed form $a_n = \frac{1}{\sqrt{5}}!\left(!\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right)$, we can compute Fibonacci numbers in $O(\log n)$ time with constant space. The implementation uses the following key observations. First, exponentiation is computed with binary exponentiation (repeated squaring). Second, the computation exploits the symmetry: $(a + b\sqrt{5})^x = c + d\sqrt{5}$ and $(a - b\sqrt{5})^x = c - d\sqrt{5}$ share the same $c$ and $d$, so only one side needs to be tracked. The proof is as follows.

$(a+b\sqrt{5})(c+d\sqrt{5}) = ac +5bd + (ad+bc)\sqrt{5}$

$(a-b\sqrt{5})(c-d\sqrt{5}) = ac +5bd - (ad+bc)\sqrt{5}$.

Therefore, this program computes only $\frac{1}{\sqrt{5}}({\frac{1 + \sqrt{5}}{2}})^n$. Notice that if the $\frac{1}{\sqrt{5}}(\frac{1 + \sqrt{5}}{2})^n$ is $\frac{1}{\sqrt{5}}(a + b\sqrt{5})$ then answer should be \(2b\) because answer is an integer and it has the same value from the other side.

Finally, program doesn’t compute $({\frac{1 + \sqrt{5}}{2}})^n$ but $\frac{(1 + \sqrt{5})^n}{2^n}$. This result in separate computation for $(1 + \sqrt{5})^n$ and ${2^n}$. Therefore, there couldn’t be a floating-point error. In the program below, it uses $a$ as an index of $1$, $b$ as an index of $\sqrt{5}$ and $div$ as an index of power of $2$. At the last step, it avoided division but used shift operation to reduce overhead. Notice that $a$ and $b$ will be divided in to two and $div$ will be subtracted by 1 if both $a$ and $b$ is even and $div$ is bigger than 1 to avoid overflow. $div$ will not go below 1 because it will be subtracted by one at the last step because the answer is $2b$ not $b$. Notice that it uses a logarithmic power operation to compute. In other world to compute $a^x$, it computes $a^1 + a^2 + a^4 + a^8 + \cdots$ depending on the binary digit of $x$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
unsigned int fib(unsigned int x){
    unsigned int a, b;
    unsigned int div = 1;
    unsigned int res_a = 1;
    unsigned int res_b = 0;
    unsigned int res_div = 0;
    a = 1;
    b = 1;
    for(unsigned int bit = 1; bit <= x; bit <<= 1){
        if(bit & x){
            {
                unsigned int  tra, trb;
                tra = a * res_a + 5 * b*res_b;
                trb = b * res_a + a * res_b;
                res_a = tra;
                res_b = trb;
                res_div += div;
                while(((res_a % 2) == 0) && ((res_b % 2) == 0) && (res_div > 1)){
                    res_a /= 2;
                    res_b /= 2;
                    res_div -= 1;
                }
            }
        }
        {
            unsigned int ta, tb;
            ta = a*a + 5*b*b;
            tb = 2*a*b;
            a = ta; b = tb;
        }
        div *= 2;
        if(((a % 2) == 0) && ((b % 2) == 0)){
            a /= 2;
            b /= 2;
            div -= 1;
        }
    }
    return res_b >> (res_div-1);
}

Performance Comparison

The mathematical approach is the fastest, followed by bottom-up dynamic programming, top-down memoization, and finally pure recursion. Detailed test results are below.

Normal scale Logarithmic scale
NMathematicalBottom-upTop-downRecursionMathematicalBottom-upTop-downRecursionLocal best
1102358792685166309.233579.08168.832158.79936Recursion
2116308312670864619.361349.025468.811068.77354Recursion
31416998764961380549.558819.1978610.8128.99392Recursion
413645110525046296089.521139.3103710.8299.17035Recursion
5162421192768208117209.695369.3865611.13039.36905Recursion
6113054190691154772440711.63569.8558211.656810.1026Bottom-up
727275202901478613396010.21379.9178811.90410.4329Bottom-up
824092218901587355001910.08969.9937911.97510.8202Bottom-up
927424231292216698079510.219210.048812.308911.2997Bottom-up
10274082446020456912568410.218610.104812.228711.7415Bottom-up
11304272609322942123629510.323110.169412.343312.3728Bottom-up
12272032724025801033314110.211110.212412.460812.7163Mathematical
13528872888628553465605810.875910.271112.562113.394Bottom-up
14311113144833271792134410.345310.356112.71513.7336Mathematical
153420331631343148141158010.440110.361912.745914.1602Bottom-up
162714832943351717156842410.209110.402512.770614.2656Mathematical
17209802318226303725472179.9513210.051112.4814.7505Mathematical
18208692461134043740604249.9460210.110912.73815.2168Mathematical
192292625102261359646535110.0410.130712.473715.682Mathematical
202066725864280550105011189.9362910.160612.544516.167Mathematical
2122812270242934021698543810.03510.204512.589316.6479Mathematical
2223184278353013262737238710.051210.23412.615917.125Mathematical
2325186288323244354411021910.13410.269212.689817.6022Mathematical
242088829794348050713777229.9469310.302112.760118.0835Mathematical
25228663059135469411548483110.037410.328512.77918.5646Mathematical
26236693161035943418685534510.071910.361212.792319.0458Mathematical
27250913248240004830210956610.130310.388412.899319.5263Mathematical
28227173374138608548855006210.030910.426512.863820.007Mathematical
29246683448341293279014193610.113310.448212.93120.4877Mathematical
302546135500423788127929087110.144910.477312.95720.9696Mathematical
312731638959443156...10.215210.570313.0017...Mathematical
321988937064449541...9.8979210.520413.016...Mathematical
332259138108487450...10.025310.548213.0969...Mathematical
342246238795478228...10.019610.56613.0778...Mathematical
352495041350479806...10.124610.629813.0811...Mathematical
362250342648523592...10.021410.660713.1685...Mathematical
372314743608518030...10.049610.68313.1578...Mathematical
382459144482555361...10.110110.702813.2274...Mathematical
392735245739638874...10.216510.730713.3675...Mathematical
402270346887647076...10.030310.755513.3802...Mathematical
412459147835624376...10.110110.775513.3445...Mathematical
422433047897596579...10.099510.776813.299...Mathematical
432627548889591725...10.176410.797313.2908...Mathematical
442449749961767949...10.106310.81913.5515...Mathematical
452683451646648048...10.197410.852213.3817...Mathematical
462683751758739262...10.197510.854313.5134...Mathematical
472903453703679719...10.276210.891213.4294...Mathematical
482236954462698451...10.015410.905313.4566...Mathematical
492498155278719724...10.125910.920113.4866...Mathematical
502488855849704200...10.122110.930413.4648...Mathematical
512675773331797662...10.194611.202713.5894...Mathematical
522433558261738002...10.099710.972713.5117...Mathematical
532632659784785202...10.178310.998513.5737...Mathematical
542650859313856402...10.185210.990613.6605...Mathematical
552853661089791912...10.258911.020113.5822...Mathematical
562446561904788354...10.10511.033313.5777...Mathematical
5726499100568803439...10.184911.518613.5967...Mathematical
582616363054841987...10.172111.051713.6435...Mathematical
592894463964920700...10.273111.066113.7329...Mathematical
602718565499957073...10.210411.089813.7716...Mathematical
612812866336866843...10.244511.102513.6726...Mathematical
622903467246904581...10.276211.116113.7152...Mathematical
6331755144641918552...10.365811.88213.7306...Mathematical
642264877184912849...10.027811.253913.7243...Mathematical
652444769598929568...10.104311.150513.7425...Mathematical
662453679183919052...10.107911.279513.7311...Mathematical
672702871351940495...10.204611.175413.7542...Mathematical
684188272961955236...10.642611.197713.7697...Mathematical
692745074149989970...10.220111.213813.8054...Mathematical
702694074165987940...10.201411.21413.8034...Mathematical
7129203846651004979...10.28211.346513.8205...Mathematical
7225054760111133138...10.128811.238613.9405...Mathematical
7326823866821028957...10.19711.3713.8441...Mathematical
7426832879211043417...10.197411.384213.858...Mathematical
7528852888491165512...10.269911.394713.9687...Mathematical
7627107899611071402...10.207511.407113.8845...Mathematical
7728693908881079024...10.264411.417413.8916...Mathematical
7829072919621123328...10.277511.429113.9318...Mathematical
7930962834071174810...10.340511.331513.9766...Mathematical
8024316841631141752...10.098911.340513.9481...Mathematical
8126752960531272064...10.194411.472714.0562...Mathematical
8227068969591178098...10.206111.48213.9794...Mathematical
8328685984791262305...10.264111.497614.0484...Mathematical
8426923984631290894...10.200711.497414.0708...Mathematical
8529018890351187264...10.275711.396813.9872...Mathematical
86282391012751243807...10.248511.525614.0337...Mathematical
87309811016611282043...10.341111.529414.064...Mathematical
88269101036271273582...10.200311.548614.0573...Mathematical
8928589919621242803...10.260811.429114.0329...Mathematical
90287591048861352592...10.266711.560614.1175...Mathematical
91307961066851380392...10.335111.577614.1379...Mathematical
92282221075921310485...10.247911.586114.0859...Mathematical