p1.c

#include <stdio.h>
#include <math.h>
#include <sys/time.h>

/* obtiene la hora actual en microsegundos */
double microsegundos() {
    struct timeval t;
    if (gettimeofday(&t, NULL) < 0 )
        return 0.0;
    return (t.tv_usec + t.tv_sec * 1000000.0);
}


int fib1(int n){
    if(n<2){
        return n;
    }else{
        return fib1(n-1) + fib1(n-2);
    }
}

int fib2(int n){
    int i=1;
    int j=0;
    int k;
    for(k=0;k!=n;k++){

        j=i+j;
        i=j-i;
    }
    return j;
}

int fib3(int n){
    int i = 1;
    int j = 0;
    int k = 0;
    int h = 1;
    int t = 0;

    while (n>0){

        if(n%2 != 0){
            t=j*h;
            j=i*h + j*k + t;
            i=i*k +t;
        }
        t=h*h;
        h=2*k*h + t;
        k=k*k +t;
        n=n/2;
    }
    return j;
}


void test() {
    int n;
    printf("n\tfib1(n)\tfib2(n)\tfib3(n)\n");

    for (n=0;n<=10;n++){
        printf("%d\t%d\t%d\t%d\n",n,fib1(n),fib2(n),fib3(n));
    }

}

void imprimirFib1(){
    int n, i;
    int cont;
    double t1, t2, t, x, y, z;

    printf("Fib 1\n           n           t(n)      t(n)/1,1^n      *t(n)/fi^n     t(n)/2^n\n");
    for(cont=1;cont<=3;cont++) {
        for (n = 2; n <= 32; n = n * 2) {
            t1 = microsegundos();
            fib1(n);
            t2 = microsegundos();
            t = t2 - t1;
            if(t<500){
                t1 = microsegundos();
                for(i=0;i<1000;i++) {
                    fib1(n);
                }
                t2=microsegundos();
                t=(t2-t1)/1000;
            }
            x = t / pow(1.1,n);
            y = t / pow(((1+sqrt(5))/2), n);
            z = t / pow(2, n);
            printf("%12d%15.3f%15.6f%15.6f%15.6f\n", n, t, x, y, z);
        }
        printf("\n");
    }
    printf("*fi=((1+sqrt(5))/2)\n");
}

void imprimirFib2(){
    int n, i;
    int cont;
    double t1, t2, t, x, y, z;
    printf("\nFib 2\n           n           t(n)      t(n)/n^0,8       t(n)/n      t(n)/nlogn\n");
    for(cont=1;cont<=3;cont++){
        for(n=1000;n<=10000000; n=n*10){
            t1 = microsegundos();
            fib2(n);
            t2 = microsegundos();
            t = t2-t1;

            if(t<500){
                t1 = microsegundos();
                for(i=0;i<1000;i++) {
                    fib2(n);
                }
                t2=microsegundos();
                t=(t2-t1)/1000;
            }
            x = t / pow(n,0.8);
            y = t / n;
            z = t / (n*log(n));
            printf("%12d%15.3f%15.6f%15.6f%15.6f\n", n, t, x, y, z);
        }
        printf("\n");
    }
}

void imprimirFib3(){
    int n, i;
    int cont;
    double t1, t2, t, x, y, z;

    printf("\nFib 3\n           n           t(n)    t(n)/sqrt(logn)   t(n)/logn     t(n)/n^0,5\n");
    for(cont=1;cont<=3;cont++){
        for(n=1000;n<=10000000; n=n*10){
            t1 = microsegundos();
            fib3(n);
            t2 = microsegundos();
            t = t2-t1;
            if(t<500){
                t1 = microsegundos();
                for(i=0;i<1000;i++) {
                    fib3(n);
                }
                t2=microsegundos();
                t=(t2-t1)/1000;
            }
            x = t / sqrt(log(n));
            y = t / log(n);
            z = t / pow(n, 0.5);
            printf("%12d%15.3f%15.6f%15.6f%15.6f\n", n, t, x, y, z);
        }
        printf("\n");
    }
}
int main(){
    imprimirFib1();
    imprimirFib2();
    imprimirFib3();
    test();

    return 0;
}