2

I am currently doing program 2 for the startup engineering course offered on coursera

I'm programming using and ubuntu instance using Amazon web services and my programming is constantly hanging. There might be something wrong with my node.js program but I can't seem to locate it.

This program is meant to produce the first 100 Fibonacci numbers separated with commas. 

    #! /usr/bin/env node

    //calculation

    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);}
            };

    //put in array

    var firstkfib = function(k){
                    var i;
                    var arr = [];
                    for(i = 1; i <= k; i++){
                            arr.push(fibonacci(i));
                    }
            return arr

            };

    //print

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

    var k = 100;
    console.log("firstkfib(" + k +")");
    console.log(format(firstkfib(k)));

The only output I get is 

    ubuntu@ip-172-31-30-245:~$ node fib.js
    firstkfib(100)

and then the program hangs

verybadalloc
  • 5,768
  • 2
  • 33
  • 49
Liondancer
  • 15,721
  • 51
  • 149
  • 255
  • 1
    The program doesnt hang.. your loop just gets progressively slower – Duncan_m Jun 25 '13 at 23:49
  • 1
    How long does it hang? That style of Fibonacci has an O(n^2) I believe. So, for just the fib of 100, it'll do 10000 runs through that loop. For 99, it'll be pretty close to another 10000 and so on. – asafreedman Jun 25 '13 at 23:49

3 Answers3

4

I don't know if you are familiar with Time complexity and algorithmic analysis, but, it turns out that your program has an exponential running time. This basically means that, as the input increases, the time it takes to run your program increases exponentially. (If my explanation is not very clear, check this link)

It turns out that this sort of running time is extremely slow. For example, if it takes 1 ms to run your program for k=1, it would take 2^100 ms to run it for k=100. This turns out to be a ridiculously big number.

In any case, as Zhehao points out, the solution is to save the value of fib(n-1) and fib(n-2) (in an array, for example), and reuse it to compute fib(n). Check out this video lecture from MIT (the first 15 mins) on how to do it.

Community
  • 1
  • 1
verybadalloc
  • 5,768
  • 2
  • 33
  • 49
1

You may want to try printing out the numbers as they are being computed, instead of printing out the entire list at the end. It's possible that the computation is hanging somewhere along the line.

On another note, this is probably the most inefficient way of computing a list of fibonacci numbers. You compute fibonacci(n) and then fibonacci(n+1) without reusing any of the work from the previous computation. You may want to go back and rethink your method. There's a much faster and simpler iterative method.

Zhehao Mao
  • 1,789
  • 13
  • 13
0

writing intense computational code in nodeJS leads to blocking. since Fibonacci is an intense computational code so might end up blocking.

I'M IRONMAN
  • 5
  • 3