calculating fibonacci(1000)

[chorei]

hey all
i have a real problem with fibonacci numbers

i have calculated max fib(47) with my codes but i have a project that i need to calculate the n'th fib number which is get from the user and print the fib valu to the screen

the numbers must be up to fib(1000) and while calculating this i have to use a look up table for not to calculate the fib numbers again and again

pls help me about my prob....

[bleonard989]

I just got done working on my own fib project. I wrote a post about it looking for help as well. You can check out my thread that I have about this project, I used a function, but only had to go up to a fib number of 96

Write your ideas on paper. Then put them into practice!

[Duoas]

To calculate Fibonacci numbers you don't need a lookup table... Remember, each successive term is the sum of the previous two. Hence, you only need to remember two numbers at a time. Use a loop to find the nth term you want.

if n == 0 return 0
if n == 1 return 1
prev = 0
curr = 1
for i = 2 to n:
  temp = prev + curr
  prev = curr
  curr = temp
return curr

This is fairly quick for terms under several hundred thousand...

If you want to get fancy, you can use something of a modulo table to store the prev and curr for every 1000th term or something, just to keep calculation times down if you are calling your Fibonacci function fairly often.

Hope this helps.

[EDIT] too slow again...

[chorei]

my idea is to store the fib numbers in dynamic 2d array and read from this array but i couldnt do :(

[chorei]

To calculate Fibonacci numbers you don't need a lookup table... Remember, each successive term is the sum of the previous two. Hence, you only need to remember two numbers at a time. Use a loop to find the nth term you want.

if n == 0 return 0
if n == 1 return 1
prev = 0
curr = 1
for i = 2 to n:
  temp = prev + curr
  prev = curr
  curr = temp
return curr

This is fairly quick for terms under several hundred thousand...

If you want to get fancy, you can use something of a modulo table to store the prev and curr for every 1000th term or something, just to keep calculation times down if you are calling your Fibonacci function fairly often.

Hope this helps.

[EDIT] too slow again...

yes you are right but the 1000 th fib number is too big to make calculations or store

[chorei]

#include <stdio.h>


int main (int argc, const char * argv[]) {

     int numToPrint, i;
     double num1, num2, ans;

     num1 = 0;
     num2 = 1;

     printf("How many numbers would you like to print?\t");
     scanf("%d", &numToPrint);

     printf("1\t%.0f\n2\t%.0lf\n", num1, num2);

     for(i = 0; i < (numToPrint - 2); ++i){

          ans = (num1 + num2);

          printf("%d\t%.0lf\n", i+3, ans);

          num1 = num2;
          num2 = ans;
     }


    return 0;
}

here is my code but doesnt work

>for not to calculate the fib numbers again and again

Maybe you could make use of the following known fact:

[tex]F_{n}=\frac{(1+sqrt{5})^{n}-(1-sqrt{5})^{n}}{2^{n}sqrt{5}}[/tex]

Which doesn't rely on previous Fibonacci calculations...

[Duoas]

> yes you are right but the 1000 th fib number is too big to make calculations or store
Er, if you are playing with Fibonacci numbers surely you are using some sort of bignum library?

> yes you are right but the 1000 th fib number is too big to make calculations or store
Er, if you are playing with Fibonacci numbers surely you are using some sort of bignum library?

That's true although it would be trivial enough to write your own just for the fib sequence.