## Thursday, October 2, 2014

### Fastest Fibonacci Sequencer

This algorithm is based on Fast-doubling  as explained in Fast Fibonacci algorithms.

Given F(k) and F(k+1), we can calculate these equations:

F(2k) = F(k)[2F(k+1)−F(k)]
F(2k+1) = F(k+1)2+F(k)2.

 ``` 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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117``` ```#include #include #include #ifdef DEBUG #define DBGMSG(x) printf x #else #define DBGMSG(x) #endif typedef unsigned long long num_type; void _fib(int n, num_type *fn, num_type *fn_1); num_type fibonacci(uint n, num_type *s) { int i; num_type fn=0, fn_1=1; if (!s) return 0; if (n < 2) { return 1; } for(i=1; i c * f(2k+1) = f(k)^2 + f(k+1)^2 ---> s * * if we plugin k = n/2, we get f(n) and f(n+1) */ void _fib(int n, num_type *fn, num_type *fn_1) { num_type c,d; num_type a, b; DBGMSG( ("%s: Initially n=%u, fn=%llu, fn_1=%llu\n", __FUNCTION__, n, *fn, *fn_1) ); if (n==0) { *fn = 0; // fn *fn_1 = 1; // fn+1 return; } else { a = *fn; b = *fn_1; } _fib(n>>1, &a, &b); DBGMSG (("%s: local fn=%llu, fn_1=%llu\n", __FUNCTION__, a, b)); c = a * (2*b - a); d = b*b + a*a; DBGMSG( ("%s: c=%llu, d=%llu\n", __FUNCTION__, c, d) ); if (n % 2 == 0) { // n is even *fn = c; *fn_1 = d; } else { *fn = d; *fn_1 = c+d; } } int main(int argc, char *argv[]) { uint n; uint f; int i; num_type *result; char *sbuf; int status = 0; if (argc > 1) n = atoi(argv[1]); else { printf("Enter a number: "); sbuf = (char *)malloc(50); status = (getline(&sbuf, &n, stdin) > 0); if (status == 0) { n = atoi(sbuf); free(sbuf); } else { printf("Error in input\n"); return (1); } } if (n <= 0) { printf("What have yo done???\n"); return(0); } if (status == 0) { result = (num_type *)malloc(n*sizeof(unsigned long long)); f = fibonacci(n, result); printf("Fibonacci sequence: "); for(i=0; i