How to generate Fibonacci faster

Question

Hello! I am a CSE student and preparing myself for programming contest.Now I am working on Fibonacci series. I have a input file of size about some Kilo bytes containing positive integers. Input formate looks like

3 5 6 7 8 0

A zero means the end of file. Output should like

2 
5 
8 
13 
21 

my code is

#include<stdio.h>

int fibonacci(int n) {
  if (n==1 || n==2)
    return 1;
  else
    return fibonacci(n-1) +fibonacci(n-2);
}
int main() {
  int z;
  FILE * fp;    
  fp = fopen ("input.txt","r");    
  while(fscanf(fp,"%d", &z) && z) 
   printf("%d \n",fibonacci(z));
  return 0;
}

The code works fine for sample input and provide accurate result but problem is for my real input set it is taking more time than my time limit. Can anyone help me out.

Answer 1

You should probably look into memoization.

http://en.wikipedia.org/wiki/Memoization

It has an explanation and a fib example right there

Answer 2

Can you post input.txt file and time limits? btw: This task is well know. Did you read the following http://www.ics.uci.edu/~eppstein/161/960109.html ?

Answer 3

Use memoization. That is, you cache the answers to avoid unnecessary recursive calls.

Here's a code example:

#include <stdio.h>

int memo[10000]; // adjust to however big you need, but the result must fit in an int
                 // and keep in mind that fibonacci values grow rapidly :)

int fibonacci(int n) {
  if (memo[n] != -1)
    return memo[n];

  if (n==1 || n==2)
    return 1;
  else
    return memo[n] = fibonacci(n-1) +fibonacci(n-2);
}
int main() {
  for(int i = 0; i < 10000; ++i)
    memo[i] = -1;
  fibonacci(50);
}

Answer 4

Your algorithm is recursive, and approximately has O(2^N) complexity.

This issue has been discussed on stackoverflow before: http://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence

There is also a faster implementation posted in that particular discussion.

Answer 5

Build an array Answer[100] in which you cache the results of fibonacci(n). Check in your fibonacci code to see if you have precomputed the answer, and use that result. The results will astonish you.

Answer 6

Google is your friend:

http://www.chaos.org.uk/~eddy/craft/Fibonacci.html

Answer 7

You can reduce the overhead of the if statement: http://stackoverflow.com/questions/2170276/calculating-fibonacci-numbers-recursively-in-c/2170308#2170308

Answer 8

First of all, you can use memoization or an iterative implementation of the same algorithm.

Consider the number of recursive calls your algorithm makes:

fibonacci(n) calls fibonacci(n-1) and fibonacci(n-2)
fibonacci(n-1) calls fibonacci(n-2) and fibonacci(n-3)
fibonacci(n-2) calls fibonacci(n-3) and fibonacci(n-4)

Notice a pattern? You are computing the same function a lot more times than needed.

An iterative implementation would use an array:

int fibonacci(int n) {
    int arr[maxSize + 1]; 
    arr[1] = arr[2] = 1; // ideally you would use 0-indexing, but I'm just trying to get a point across
    for ( int i = 3; i <= n; ++i )
        arr[i] = arr[i - 1] + arr[i - 2]; 

    return arr[n];
}

This is already much faster than your approach. You can do it faster on the same principle by only building the array once up until the maximum value of n, then just print the correct number in a single operation by printing an element of your array. This way you don't call the function for every query.

If you can't afford the initial precomputation time (but this usually only happens if you're asked for the result modulo something, otherwise they probably don't expect you to implement big number arithmetic and precomputation is the best solution), read the fibonacci wiki page for other methods. Focus on the matrix approach, that one is very good to know in a contest.

Answer 9

You can do this by matrix multiplictation, raising the matrix to power n and then multiply it by an vector. You can raise it to power in logaritmic time.

I think you can find the problem here. It's in romanian but you can translate it with google translate. It's exactly what you want, and the solution it's listed there.

Answer 10

Look in Wikipedia, there is a formula that can gives the number in the fibbonacci sequence with no recursion at all

http://en.wikipedia.org/wiki/Fibonacci_number

Answer 11

Are you guaranteed that, as in your example, the input will be given to you in ascending order? If so, you don't even need memoization; just keep track of the last two results, start generating the sequence but only display the Nth number in the sequence if N is the next index in your input. Stop when you hit index 0.

Something like this:

int i = 0;
while ( true ) {
    i++; //increment index
    fib_at_i = generate_next_fib()
    while ( next_input_index() == i ) {
        println fib_at_i
}

I leave exit conditions and actually generating the sequence to you.

Answer 12

Use the golden-ratio

Answer 13

#include<stdio.h>

 int g(int n,int x,int y)
   {
   return n==0 ? x : g(n-1,y,x+y);}

 int f(int n)
   {
   return g(n,0,1);}

 int main (void)
   {  
   int i;
   for(i=1; i<=10 ; i++)
     printf("%d\n",f(i)
   return 0;
   }

Answer 14

You could simply use a tail recursion version of a function that returns the two last fibonacci numbers if you have a limit on the memory.

int fib(int n)
{
    int a = 0;
    int b = 1;
    while (n-- > 1) {
        int t = a;
        a = b;
        b += t;
    }
    return b;
}

This is O(n) and needs a constant space.

Answer 15

In the functional programming there is a special algorithm for counting fibonacci. The algorithm uses accumulative recursion. Accumulative recursion are used to minimize the stack size used by algorithms. I think it will help you to minimize the time. You can try it if you want.

int ackFib (int n, int m, int count){
    if (count == 0)
        return m;
    else
        return ackFib(n+m, n, count-1);
}



int fib(int n)
{
 return ackFib (0, 1, n+1);
}