Which fibonacci function will evaluate faster?

Question

I am trying to get the first 100 fibonacci numbers to output to a .txt file. I got it to run, but it's taking a while. Will fibonacci or fibonacci2 be faster? The code below uses the first one.

#!/usr/bin/env node

var fs = require('fs');

// Fibonacci
// http://en.wikipedia.org/wiki/Fibonacci_number
var fibonacci = function(n) {
    if(n < 1) { return 0;}
    else if(n == 1 || n == 2) { return 1;}
    else if(n > 2) { return fibonacci(n - 1) + fibonacci(n - 2);}
};

// Fibonacci: closed form expression
// http://en.wikipedia.org/wiki/Golden_ratio#Relationship_to_Fibonacci_sequence
var fibonacci2 = function(n) {
    var phi = (1 + Math.sqrt(5))/2;
    return Math.round((Math.pow(phi, n) - Math.pow(1-phi, n))/Math.sqrt(5));
};

// Find first K Fibonacci numbers via basic for loop
var firstkfib = function(k) {
    var i = 1;
    var arr = [];
    for(i = 1; i < k+1; i++) {
        var fibi = fibonacci(i);
        arr.push(fibi);

        // Print to console so I can monitor progress
        console.log(i + " : " + fibi); 
    }
    return arr;
};

var fmt = function(arr) {
    return arr.join(",");
};

var k = 100;

// write to file
var outfile = "fibonacci.txt";
var out = fmt(firstkfib(k));
fs.writeFileSync(outfile, out);
console.log("\nScript: " + __filename + "\nWrote: " + out + "\nTo: " + outfile);

I think to get an accurate comparison you need to write a simple bit of script which answers your question. — Ronnie, Jul 02 '13 at 15:47

score 1 · Answer 1 · answered Jul 02 '13 at 15:52

In general, recursive function are "cleaner" and "easier" to write, but are often requiring more ressources (mostly memory due to an accumulation of stacks). in your case the best way to get the 100 first would be to programit using a simple loop that will compute the next number of the fibonacci series and add it to a list.

double a[100];
a[0] = 1;
a[1] = 1;
K=2;
Do{ 

{
 a[k] = a[k - 2] + a[k- 1];
 k++;
}While (k!=100)

AJMansfield · Answer 2 · 2013-07-02T17:50:48.267

The recursive fibonacci function is implemented the wrong way. The correct way to implement it recursively is discussed in this article Recursion and Fibonacci Numbers. For those too lazy to read, here is their code (it's in C, but it shouldn't be too hard to translate):

unsigned long fib(unsigned int n)
{
  return n == 0 ? 0 : fib2(n, 0, 1);
}

unsigned long fib2(unsigned int n, unsigned long p0, unsigned long p1)
{
  return n == 1 ? p1 : fib2(n - 1, p1, p0 + p1);
}

An even more efficient implementation would cache the values of the fibonacci sequence as it computes them:

var cache = [];

var fibonacci = function(n) {
  if(cache.length > n) return cache[n];
  return (cache[n] = fib2(n, 0, 1));
};

var fib2 = function(n, p0, p1) {
  if(cache.length > n) return cache[n];
  return n == 1 ? p1 : (cache[n] = fib2(n - 1, p1, p0 + p1));
};

I don't really know the language, so there might be some problems with the code, but this is at least the gist of it.

score 1 · Answer 3 · answered Jul 12 '13 at 00:43

For your question, we can't do better than O(n) since you need to produce all of the first n (n=100) numbers.

Interestingly, if you just need the nth fib number, there exists an O(log n) solution as well.

The algorithm is simple enough: Find the nth power of matrix A using a Divide and Conquer approach and report (0,0)th element, where

 A = |1     1 |
     |1     0 |

The recursion being

 A^n = A^(n/2) * A^(n/2)

Time complexity:

T(n) = T(n/2) + O(1) = O(logn)

If you think about it with a piece of paper, you'd find that the proof is simple and is based upon the principle of induction. If you still need help, refer to this link

NOTE: Of course you could iteratively calculate A, A^2, A^3 and so on. However, it wouldn't make sense to use it compared to the other simpler solutions described in the other answers. (Because of sheer code complexity)

score 0 · Answer 4 · answered Jul 02 '13 at 15:49

This is a very naive way to do this calculation. try to do something like:

long[] a = new long[100];
a[0] = 1;
a[1] = 1;
for (int i = 2; i < 100; ++i)
{
    a[i] = a[i - 2] + a[i - 1];
}

for (int i = 0; i < 100; ++i)
Console.WriteLine(a[i]);

This way you are getting a linear time O(n)

Which fibonacci function will evaluate faster?

4 Answers4