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 <stdio.h>
#include <stdlib.h>
#include <sys/types.h>

#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<n; i++)
    {
        _fib(i, &fn, &fn_1);
        DBGMSG(("i=%u, n=%u, fn=%llu, fn+1=%llu\n", i, n, fn, fn_1));
        s[i] = fn;
    }
    return s[n];
}

/*
 * This is base on matrix exponentiation algorithm:
 * where:
 *  f(2k) = f(k)*{ 2*f(k+1) - f(k)}         ---> 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<n; i++)
   printf("%llu ", result[i]);
  printf("\n");
        if (result)
      free(result);
    }
}
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)