#include <stdio.h>      /* Required to use printf() */
/* Function f(n) returns the n'th Fibonacci number
 * It uses ALGORITHM 1A: BINARY RECURSION
 */
unsigned int f(int n) {
    return n<2 ? 1 : f(n-1)+f(n-2);
}
/* 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;
}

#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;
}

#include <stdio.h>    /* Required to use printf() */
/* Function l(n1,n2,n) calculates f(n) using parameters n1 and n2
 * to store the two previously calculated Fibonacci numbers */
unsigned int l(unsigned int n1,unsigned int n2,int n) {
    return n<2 ? n1 : l(n1+n2, n1, n-1);
}
/* Function f(n) returns the n'th Fibonacci number
 * It uses ALGORITHM 2B: SIMPLE RECURSION
 */
unsigned int f(int n) {
    l(1,1,n);
}
/* 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;
}

#include <stdio.h>      /* Required to use printf() */
/* Function f(n) returns the n'th Fibonacci number
 * It uses ALGORITHM 2C: NON-RECURSIVE LOOP
 */
unsigned int f(int n) {
    int i;
    unsigned int n1=1,n2=1;

    for(i=1; i<=n; i++) {
        n1+=n2;
        n1^=n2^=n1^=n2; /* C trick to swap n1 and n2 */
    }
    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;
}

#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;
}

#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;
}

#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;
}