Thread: The highest Fibonacci number ever calculated

I calculated the 20,000th number on my computer, and it took 9 seconds. Is my program slow, or just my computer?

Code:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

/* number of max three digits (max digits = MAX3DIGITS*3) */
#define MAX3DIGITS 100000

/* struct that holds three digits (like 503) */
struct three {
    unsigned n : 10;
};

/* a whole number made up of struct threes */
struct num {
    struct three n[MAX3DIGITS];
} number[2];

int main() {
    int x, y, n = 0;  /* temp/loop vars and # of calculations (loop count) */
    int naim, prev = 0;  /* the aim number and which number is current */
    int digits = 2;  /* digits taken (in threes) */

    fprintf(stderr, "\nEnter the fibonacci number to compute:\n");
    scanf("%i", &naim);

    number[0].n[0].n = 0;
    number[1].n[0].n = 1;

    while(!kbhit() && ++n < naim && digits <= MAX3DIGITS) {
        //fprintf(stderr, "\r%i", n);

        prev = !prev;

        for(x = 0; x < digits; x ++) {
            y = number[!prev].n[x].n + number[prev].n[x].n;
            number[!prev].n[x].n = (y%1000);
            number[!prev].n[x+1].n += (y/1000);
        }
        if(number[!prev].n[digits-1].n) digits ++;
    }

    printf("\nfib(%i) = %i", n, number[!prev].n[digits-2].n);
    for(x = digits-3; x >= 0; x --) {
        printf(",%03i", number[!prev].n[x].n);
    }
    printf("\n");

    if(n>1) {
        printf("\nfib(%i) = %i", n-1, number[prev].n[digits-2].n);
        for(x = digits-3; x >= 0; x --) {
            printf(",%03i", number[prev].n[x].n);
        }
        printf("\n");
    }

    if(kbhit()) getche();
    return 0;
}

The commented-out fprintf() slows it down a lot, but shows the program is doing something.

The reason all the prompts and stuff are printed to stderr is that I usually redirect stdout to a file to save the result.

200,000th in 1.7 seconds? How fast is your computer?

Thanks for pointing that out . . . I didn't know that. But is my program slow for that way of doing it? (Like, add the first two numbers . . . .)

I was talking to a math major at MIT the other day, he had an intersting scope on this. As N approches infinity, Vn being the Nth term, Vn / V(n-1) becomes (1+ sqrt(5))/2. That is, the ratio between the terms aproaches that value, or "PHI" (The Golden Ration).

Maybe that idea could help with something, google it, there's a lot out there.