cubbi.com: fibonacci numbers in c
C
Date: 1972 (Standards: ANSI X3.159-1989, ISO/IEC 9899:1990, ISO/IEC 9899:1999)
Type: Imperative low-level language
Usage: Everything written for UNIX-based operating systems, and the majority of system and application software everywhere. This language also influenced the majority of languages after it, most notably C++ and Java.

ALGORITHM 1A: NAIVE BINARY RECURSION
/* This program calculates the nth fibonacci number
 * using alrogirhtm 1A: naive binary recursion
 *
 * compiled: gcc -O2 -Wall -std=c99 -march=native -o f1a f1a.c
 * executed: ./f1a n
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>

/* Naive binary recursion: F(n) = F(n-1) + F(n-2) */
int64_t fib(int n) {
    return n<2 ? n : fib(n-1) + fib(n-2);
}
/* Function f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1) */
int64_t f(int n) {
    if(n<0)
       return n%2 ? fib(-n) : -fib(-n);
    else
       return fib(n);
}
/* Function f_print(n) prints the n'th Fibonacci number */
void f_print(int n) {
    printf("%dth Fibonacci number is %" PRId64 "\n",n,f(n));
}
/* entry point: check the number of commandline arguments, fail if
 * the argument is not a number */
int main(int argc, char** argv) {
    if (argc!=2 || (atoi(argv[1])==0 && strcmp(argv[1],"0")!=0)) {
        printf("Usage: f1a <n>\n");
    else
        f_print(atoi(argv[1]));
}

ALGORITHM 1B: CACHED BINARY RECURSION / MEMOIZATION
/* This program calculates the nth fibonacci number
 * using alrogirhtm 1B: cached binary recursion
 *
 * compiled: gcc -O2 -Wall -std=c99 -march=native -lgmp -o f1b f1b.c
 * executed: ./f1b n
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>

/* cleanup of a malloc'ed mpz_t pointer variable */
void free_mpzp(mpz_t* mp) {
    mpz_clear(*mp);
    free(mp);
}

/* Naive binary recursion: F(n) = F(n-1) + F(n-2) with memoization
 * First checks if the answer is known, reports it if it is known,
 * then recurses twice, saves the new answer, and returns it. */
mpz_t* fib_m(int n, mpz_t** m) {
    if(m[n]) return m[n];
    mpz_t *r=malloc(sizeof(mpz_t));
    if(n<2) {
        mpz_init_set_si(*r, n); 
    } else {
        mpz_init(*r);
        mpz_t* f1 = fib_m(n-1, m);
        mpz_t* f2 = fib_m(n-2, m);
        mpz_add(*r, *f1, *f2);
    /* without memoization, here would be free_mpzp(f1); free_mpzp(f2); */
    }
    m[n]=r;
    return r;
}

/* Function fib initializes the memoization array, calls fib_m,
 * and cleans up afterwards. Note that the last element of the memo array
 * is not freed because it is a copy of the pointer that this function 
 * returns, and it will be freed by the called (f_print) */
mpz_t* fib(int n) {
    mpz_t** m = calloc(n+1,sizeof(mpz_t*)); /* array from [0...n] */
    mpz_t* r = fib_m(n, m);   
    for(int i=0; i<n; i++) /* do not clean up the last value, m[n] */
        if(m[i]) free_mpzp(m[i]);
    free(m);
    return r;
}

/* Function f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1) */
mpz_t* f(int n) {
    if(n>=0) return fib(n);
    mpz_t* f = fib(-n);
    if(n%2) return f;
    mpz_t* ng = malloc(sizeof(mpz_t));
    mpz_init(*ng);
    mpz_neg(*ng, *f);
    free_mpzp(f);
    return ng;
}
/* Function f_print(n) prints the n'th Fibonacci number */
void f_print(int n) {
    mpz_t* f_n = f(n);
    char* result = mpz_get_str(NULL, 10, *f_n);
    printf("%dth Fibonacci number is %s\n", n, result);
    free_mpzp(f_n);
    free(result);
}
/* entry point: check the number of commandline arguments, fail if
 * the argument is not a number */
int main(int argc, char** argv) {
    if (argc!=2 || (atoi(argv[1])==0 && strcmp(argv[1],"0")!=0)) {
        printf("Usage: f1b <n>\n");
        return 1;
    } else {
        f_print(atoi(argv[1]));
        return 0;
    }
}

ALGORITHM 2A-3: DATA STRUCTURE - SIMPLE LIST
#include <stdio.h>      /* Required to use printf() */
#include <stdlib.h>     /* Required to use calloc() */
/* struct FL is a node of a linked list */
struct FL {
    unsigned int f;
    struct FL* next;
};
/* Function fl_init() initializes the linked list fl with two ones */
struct FL* fl_init(void) {
    struct FL* fl_h;
    fl_h       = (struct FL*)calloc(1,sizeof(struct FL));
    fl_h->next = (struct FL*)calloc(1,sizeof(struct FL));
    fl_h->f = fl_h->next->f = 1;
    return fl_h;
}
/* Function fl_get returns the n'th Fibonacci number from the list fl.
 * It uses ALGORITHM 2A-3: DATA STRUCTURE - SIMPLE LIST
 */
unsigned int fl_get(struct FL* fl_h, int n)
{
    int i;
    struct FL* fl; 
    /* Start with the head of the list */
    fl=fl_h;
    /* Traverse fl until n'th Fibonacci number is found or end of list is reached */
    for(i=0; (fl->next!=NULL) && (i<n); i++, fl=fl->next);
    /* End of list was reached but the requested Fibonacci number was not found.
       Continue traversing the list from the current position i untill the requested number n */
    for(; i<n; i++, fl=fl->next) {
        /* At each step calculate next uncalculated Fibonacci number and append it to fl */
        fl->next=(struct FL*)calloc(1,sizeof(struct FL));
        fl->next->f=fl_get(fl_h,i-1)+fl_get(fl_h,i);
    }
    return fl->f;
}
/* Function f_print(n) prints the n'th Fibonacci number */
void f_print(int n) {
    struct FL* fl;
    fl=fl_init();
    printf("%dth Fibonacci number is %lu\n",n,fl_get(fl,n));
}
/* Function main() is the program entry point in C */
int main(void) {
    f_print(46);
    return 0;
}

ALGORITHM 2B: LINEAR RECURSION WITH ACCUMULATORS
/* This program calculates the nth fibonacci number
 * using alrogirhtm 2B: inear recursion with accumulators
 *
 * compiled: gcc -O2 -Wall -std=c99 -march=native -lgmp -o f2b f2b.c
 * executed: ./f2b n
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>

/* cleanup of a malloc'ed mpz_t pointer variable */
void free_mpzp(mpz_t* mp) {
    mpz_clear(*mp);
    free(mp);
}

/* Function fib_rec adds and swaps the two accumulator arguments, and
 * calls itself with decremented counter */
mpz_t* fib_rec(mpz_t* x1, mpz_t* x2, int n) {
     mpz_add(*x1,*x1,*x2);
     mpz_swap(*x1,*x2);
     if(n<2) {
         free_mpzp(x1);
         return x2;
     } else
         return fib_rec(x1, x2, n-1);
}

/* Function fib calls fib_rec with the initial values of the accumulators
 */
mpz_t* fib(int n) {
    mpz_t* x1 = malloc(sizeof(mpz_t));
    mpz_init_set_si(*x1, 0);
    if(!n) return x1; /* if n is zero, return mpz_t* zero now */

    mpz_t* x2 = malloc(sizeof(mpz_t));
    mpz_init_set_si(*x2, 1);

    return fib_rec(x1, x2, n-1);
}
/* Function f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1) */
mpz_t* f(int n) {
    if(n>=0) return fib(n);
    mpz_t* f = fib(-n);
    if(n%2) return f;
    mpz_t* ng = malloc(sizeof(mpz_t));
    mpz_init(*ng);
    mpz_neg(*ng, *f);
    free_mpzp(f);
    return ng;
}
/* Function f_print(n) prints the n'th Fibonacci number */
void f_print(int n) {
    mpz_t* f_n = f(n);
    char* result = mpz_get_str(NULL, 10, *f_n);
    printf("%dth Fibonacci number is %s\n", n, result);
    free_mpzp(f_n);
    free(result);
}
/* entry point: check the number of commandline arguments, fail if
 * the argument is not a number */
int main(int argc, char** argv) {
    if (argc!=2 || (atoi(argv[1])==0 && strcmp(argv[1],"0")!=0)) {
        printf("Usage: f2b <n>\n");
        return 1;
    } else {
        f_print(atoi(argv[1]));
        return 0;
    }
}

ALGORITHM 2C: IMPERATIVE LOOP WITH MUTABLE VARIABLES
/* This program calculates the nth fibonacci number
 * using alrogirhtm 2C: imperative loop with mutable variables
 *
 * compiled: gcc -O2 -Wall -std=c99 -march=native -lgmp -o f2c f2c.c
 * executed: ./f2c n
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>

/* cleanup of a malloc'ed mpz_t pointer variable */
void free_mpzp(mpz_t* mp) {
    mpz_clear(*mp);
    free(mp);
}

/* Function fib calculates F(n) by repeating x1=x1+x2; swap(x1,x2)
 * starting with 0 and 1 */
mpz_t* fib(int n) {
    mpz_t* x1 = malloc(sizeof(mpz_t));
    mpz_init_set_si(*x1, 0);
    if(!n) return x1;

    mpz_t* x2 = malloc(sizeof(mpz_t));
    mpz_init_set_si(*x2, 1);

    for(int i=1; i<n; i++) {
        mpz_add(*x1,*x1,*x2);
        mpz_swap(*x1,*x2);
    }

    free_mpzp(x1);
    return x2;
}
/* Function f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1) */
mpz_t* f(int n) {
    if(n>=0) return fib(n);
    mpz_t* f = fib(-n);
    if(n%2) return f;
    mpz_t* ng = malloc(sizeof(mpz_t));
    mpz_init(*ng);
    mpz_neg(*ng, *f);
    free_mpzp(f);
    return ng;
}
/* Function f_print(n) prints the n'th Fibonacci number */
void f_print(int n) {
    mpz_t* f_n = f(n);
    char* result = mpz_get_str(NULL, 10, *f_n);
    printf("%dth Fibonacci number is %s\n", n, result);
    free_mpzp(f_n);
    free(result);
}
/* entry point: check the number of commandline arguments, fail if
 * the argument is not a number */
int main(int argc, char** argv) {
    if (argc!=2 || (atoi(argv[1])==0 && strcmp(argv[1],"0")!=0)) {
        printf("Usage: f2c <n>\n");
        return 1;
    } else {
        f_print(atoi(argv[1]));
        return 0;
    }
}

ALGORITHM 3A: MATRIX EQUATION
#include <stdio.h>    /* Required to use printf() */
/* struct M2x2 is a 2x2 square matrix */
struct M2x2 { unsigned int a[2][2]; };
/* Function m_mult multiplies two 2x2 matrices */
struct M2x2 m_mult(struct M2x2 M1, struct M2x2 M2) {
    int i,j,k;
    struct M2x2 R;
    for(i=0; i<2; i++)
        for(j=0; j<2; j++) {
            R.a[i][j]=0;
            for(k=0; k<2; k++)
                R.a[i][j]+=M1.a[i][k]*M2.a[k][j];
        }
    return R;
}
/* Function m_copy makes a copy of a 2x2 matrix */
struct M2x2 m_copy(struct M2x2 s) {
    struct M2x2 d;
    int i,j;
    for(i=0; i<2; i++)
        for(j=0; j<2; j++)
            d.a[i][j]=s.a[i][j];
    return d;
}
/* Function m_pow raises a 2x2 matrix to nth power */
struct M2x2 m_pow(struct M2x2 a, int n) {
    struct M2x2 b;
    b=m_copy(a);
    if(n>1) {
        a=m_pow(a,n/2);
        a=m_mult(a,a);
        if(n%2) a=m_mult(a,b);
    }
    return a;
}
/* Function f(n) returns the n'th Fibonacci number
 * It uses ALGORITHM 3A: MATIX EQUATION
 */
unsigned int f(int n) {
    struct M2x2 a;
    unsigned int r;

    a.a[0][0]=a.a[0][1]=a.a[1][0]=1; a.a[1][1]=0;
    a=m_pow(a,n);
    r=a.a[0][0];
    return r;
}
/* Function f_print(n) prints the n'th Fibonacci number */
void f_print(int n) {
    printf("%dth Fibonacci number is %lu\n",n,f(n));
}
/* Function main() is the program entry point in C */
int main(void) {
    f_print(46);
    return 0;
}

ALGORITHM 3B: FAST RECURSION
#include <stdio.h>    /* Required to use printf() */
/* Function l(n1,n2,n) calculates n'th Fibonacci number using n1 and n2
   to store intermediate results */
void l(unsigned int* n1, unsigned int* n2, int n) {
    unsigned int k1,k2;
    if(n<=1) { *n1=1; *n2=1; return; }
    if(n==2) { *n1=2; *n2=1; return; }
    if(n%2) {    /* n is odd */
        l(&k1,&k2,(n-1)/2);
        *n1 = k1*(k1+k2) + k1*k2;
        *n2 = k1*k1 + k2*k2;
    } else {    /* n is even */
        l(&k1,&k2,(n/2)-1);
        *n1 = (k1+k2)*(k1+k2) + k1*k1;
        *n2 = (k1+k2)*k1 + k1*k2;
    }
}
/* Function f(n) returns the n'th Fibonacci number
 * It uses ALGORITHM 3B: FAST RECURSION
 */
unsigned int f(int n) {
    unsigned int n1, n2;
    l(&n1,&n2,n);
    return n1;
}
/* Function f_print(n) prints the n'th Fibonacci number */
void f_print(int n) {
    printf("%dth Fibonacci number is %lu\n",n,f(n));
}
/* Function main() is the program entry point in C */
int main(void) {
    f_print(46);
    return 0;
}

ALGORITHM 3C: BINET'S FORMULA
#include <stdio.h>      /* Required to use printf() */
#include <math.h>       /* Required to use pow() and sqrt() */
/* Function f(n) returns the n'th Fibonacci number
 * It uses ALGORITHM 3C: BINET'S FORMULA
 */
unsigned int f(int n) {
    if (n<2) return 1;
    double phi  = (1+sqrt(5))/2;
    return (pow(phi, n+1) - pow(1-phi, n+1)) / sqrt(5);
}
/* Function f_print(n) prints the n'th Fibonacci number */
void f_print(int n) {
    printf("%dth Fibonacci number is %lu\n",n,f(n));
}
/* Function main() is the program entry point in C */
int main(void) {
    f_print(46);
    return 0;
}