Tutorials MySQL & C, C++ Fastest Fibonacci Sequence/Number Computation - tutorial advanceThe fastest way (in O(n)) of calculating Fibonacci sequence is by using matrix multiplication approach using following relation.
\[\begin{bmatrix}0 & 1 \\ 1 & 1 \end{bmatrix}^n = \begin{bmatrix} F_{n – 1} & F_n \\ F_n & F_{n + 1}\end{bmatrix}\]
Calculating $F_{34}$ is, therefore, multiplying the matrix $\begin{bmatrix}0 & 1 \\ 1 & 1\end{bmatrix}$ 34 times. The $a_{01}$ or $a_{10}$ gives the right fibonacci number. In fact $F_{34}$ can be calculated in less than 34 multiplication in following away.
\[ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^2 = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix} X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix} \\
\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^4 = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^2 X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^2 \\
\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^8 = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^4 X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^4 \\
\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{16} = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^8 X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^8 \\
\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{32} = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{16} X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{16} \\
\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{34} = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{32} X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{2} \\\]
This means, the multiplication can be done in logarithmic time. The C code for this computation is given below (also available on GitHub).
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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | #include <stdio.h> #include <stdlib.h> void mat_product(unsigned long long a[], unsigned long long b[], unsigned long long result[]) { // assuming matrix is always 2 x 2 result[0] = a[0] * b[0] + a[1] * b[2]; result[1] = a[0] * b[1] + a[1] * b[3]; result[2] = a[2] * b[0] + a[3] * b[2]; result[3] = a[2] * b[1] + a[3] * b[3]; } int main(int argc, char* argv[]) { int n, i, temp, len; unsigned long long bin[1000], **fib; unsigned long long result[4]; if (argc != 2) { printf("Usage: outputfile n\n"); exit(1); } n = atoi(argv[1]); temp = n; len = 1; while(n / 2 > 0) { bin[len - 1] = n % 2; n = n/2; len++; } if (n == 1) { bin[len - 1] = 1; } fib = (unsigned long long**) malloc(sizeof(unsigned long long*) * len); for (i = 0; i < len; i++) { fib[i] = (unsigned long long*) malloc(sizeof(unsigned long long*)*4); } fib[0][0] = 0; fib[0][1] = 1; fib[0][2] = 1; fib[0][3] = 1; for (i = 1; i < len; i++) { mat_product(fib[i - 1], fib[i - 1], fib[i]); } result[0] = fib[len - 1][0]; result[1] = fib[len - 1][1]; result[2] = fib[len - 1][2]; result[3] = fib[len - 1][3]; for(i = 0; i < len - 1; i++) { if (bin[i] == 1) { mat_product(fib[i], result, result); } } printf("F(%d) => %llu\n", temp, result[1]); return 0; } |
Related Article
destination source:https://www.programming-techniques.com/?p=29
