# Thread: The highest Fibonacci number ever calculated

1. 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?

2. Originally Posted by dwks
200,000th in 1.7 seconds? How fast is your computer?
It's a P4 3.0. Your computer is not slow, your program is. The program I use is many many times more efficient. Take a look at http://en.wikipedia.org/wiki/Fibonac...onacci_numbers

3. 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 . . . .)

4. 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.

5. the pooper already mentioned Binet's formula:

Code:
`(pow(1 + sqrt(5), n) - pow(1 - sqrt(5), n)) / (sqrt(5) * pow(2, n))`
Though it could be optimized towards:

Code:
`(pow((1 + sqrt(5)) / 2, n) - pow((1 - sqrt(5)) / 2, n) / sqrt(5)`
Now, since pow((1 - sqrt(5)) / 2, n) approaches zero as n grows large, for large values of n (and all but the smallest values of n), using pow((1 + sqrt(5)) / 2, n) / sqrt(5) and rounding works, with some variant of pow that uses arbitrary precision numbers.

So, there are a lot of algorithms. The ones that use f(n) = f(n - 1) + f(n - 2) in a while loop run in O(n*n) time. The ones that use exponentiation (whether it be matrices or a special datatype for storing the x and y of (x + y*sqrt(5)) should run in O(n*log n) time.

This is if my math was correct. I don't know if it is.

I don't know what the runtime for calculating logarithms of an arbitrary precision floating point number is, so I can't comment if logarithms are used for exponentiation.