matoski.com

As an avid foodie, I want to eat Fibonachos. I want to see a program that will print the Fibonacci sequence described below so that I can assess how many I can fit on a plate, and assess basic to moderate programming skills in a language of the candidate’s choice.

Fibonacci numbers or Fibonacci sequence are the numbers in the following integer sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987

The program should print the first 30 Fibonacci numbers where the definition of a Fibonacci number is

• f(0) = 0
• f(1) = 1
• f(n) = f(n-1) + f(n-2)
• n > 0

Calculating Fibonacci is quite easy as the formula is quite simple, there are several ways to implement the calculations, Recursive algorithm (extremely slow), Dynamic programming (slow), Matrix exponentiation, Fast doubling.

One thing to note is that because JavaScript uses floating points for integers, after n=78, the results are not correct.

For example Fibonacci(80) = 23416728348467685 but we get 23416728348467684.

• Recursive algorithm (extremely slow)

We can directly execute the recurrence as given in the mathematical definition of the Fibonacci sequence. But it’s extremely slow: It uses O(n) stack space and O(?n)) arithmetic operations, where ?=5?+12?=5+12 (the golden ratio). In other words, the number of operations to compute F(n) is proportional to the resulting value itself, which grows exponentially.

function fibonacci(n) {
    if (n < 0 || isNaN(parseInt(n))) {
        throw new Error("Invalid number or less than zero");
    }
    if (n === 0 || n === 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

• Iterative (slow)

It should be clear that if we’ve already computed F(n-2) and F(n-1), then we can add them to get F(n). We repeat until we reach i=n.

function fibonacci(n) {
    if (n < 0 || isNaN(parseInt(n))) {
        throw new Error("Invalid number or less than zero");
    }
    if (n === 0 || n === 1) {
        return n;
    }
    var seq = [0, 1];
    for (i = 2; i <= n; i++) {
        seq[i] = seq[i - 1] + seq[i - 2];
    }
    return seq[n];
}

• With memoization (Dynamic Programming)

This is quite simple as you can see, but using it on bigger numbers will be slower on repetitive calculations, one thing we can do is do memoization of the number, so the next calculations are faster.

function Fibonacci() {
    return {
        dictionary: [0, 1],
        recursive: function(n) {
            if ( n < 0 || isNaN(parseInt(n)) ) {
                throw new Error("Invalid number or less than zero");
            }
            if (n === 0 || n === 1) {
                return n;
            }
            if (this.dictionary[n]) {
                return this.dictionary[n];
            }
            this.dictionary[n] = this.recursive(n - 1) + this.recursive(n - 2);
            return this.dictionary[n];
        },
        iterative: function(n) {
            if ( n < 0 || isNaN(parseInt(n)) ) {
                throw new Error("Invalid number or less than zero");
            }
            if (n === 0 || n === 1) {
                return n;
            }
            if (this.dictionary[n]) {
                return this.dictionary[n];
            }
            for (i = 2; i <= n; i++) {
                this.dictionary[i] = this.dictionary[i - 1] + this.dictionary[i - 2];
            }
            return this.dictionary[n];
        }
    };
}

• Fast doubling method

The fast doubling method is even better, running in O(log(n)) time.

It’s defined like

F(2n)   = F(n) * (2*F(n+1) - F(n))
F(2n+1) = F(n+1)^2 + F(n)^2

And here is a sample implementation of the code

function fibonacci(n) {

    if ( n < 0 || isNaN(parseInt(n)) ) {
        throw new Error("Invalid number or less than zero");
    }

    if ( n == 0 ){
        return 0;
    }
    
    return fibonacci_tuple(n-1)[1];
}

function fibonacci_tuple(n) {

    if ( n < 0 || isNaN(parseInt(n)) ) {
        throw new Error("Invalid number or less than zero");
    }

    if (n == 0)
        return [0, 1];
    
    var result = fibonacci_tuple(Math.floor(n/2));
    var a = result[0], b = result[1];
    
    c = a * ( b * 2 - a );
    d = a * a + b * b;
    if ( n % 2 == 0 ) {
        return [c, d];
    } else {
        return [d, c + d];
    }
}

• Matrix exponentiation

[1 1]^n   [F(n+1) F(n)  ]
[1 0]   = [F(n)   F(n-1)]