Fibonacci sequence

Posted on | In

Definition

Fibonacci sequence is a sequence that generats numbers from previous two numbers. In other world, Fibonacci sequence $a$ is a a sequence defined by follows.

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

Fibonacci sequence can be changed to simple form as follows.

$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

It is the most naive and simplest implementation among all.

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 formula $a_n = \frac{1}{\sqrt{5}}( ({\frac{1 + \sqrt{5}}{2}})^n - ({\frac{1 - \sqrt{5}}{2}})^n)$, Fibonacci sequence can be computed in logarithmic time with constant space. To apply this to the program, the following techniques have been used. First of all, it uses Multiply operation with the logarithmic algorithm. Secondly, it ignores one side of algorithm because it is Symmetry between and . This means it always has the same value for and . 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 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, the bottom-up approach is the second, top-down is the third, recursion is the last. 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