Discussion on: Solving Puzzles With High-Performance JavaScript

View post

For the fibonacci puzzle, here is a solution that runs in a constant time using little math 😄

// 0(1) time complexity
var fib = function(N) {
    return Math.round(
        (Math.pow((1 + Math.sqrt(5)) / 2, N) - 
        Math.pow(-2 / (1 + Math.sqrt(5)), N)) / 
        Math.sqrt(5)
    );
}

Damian Rivas • May 23 '19

Came here to say this! Did you also learn this from a discrete mathematics class? 😄

StefanT123 • May 23 '19

I did, long time ago and it was forgotten until I saw this function somewhere (might be on dev.to) and that stuck in my brain, so every time I see a fibonacci I get a flash of this solution.😄

Andrew Healey • May 21 '19

Thanks for sharing this cool solution! I actually found this was slower on LeetCode than the post’s iterative solution. Crazy right? They must use low values of N in the test cases. I wonder if it’s quicker in other languages 🤔.

StefanT123 • May 21 '19

Hmm, I've run some benchmark tests (I ran them online on Chrome so I don't know how reliable they are) and I got two different results on two different sites. On the first site (jsben.ch/) it seems that for smaller numbers, the iterative way is faster, the real power of the pure math function is when the N >= 200. While on the other site (perf.zone/), the math function is way faster even for smaller numbers. I got this results on the perf.zone/quick:

for N = 20, math -> 705,738,258 op/second; iterative -> 66,518,777 op/second
for N = 50, math -> 725,140,230 op/second; iterative -> 16,581,587 op/second
for N = 100, math -> 700,447,370 op/second; iterative -> 5,875,773 op/second
for N = 200, math -> 706,141,355 op/second; iterative -> 2,562,412 op/second

But anyway I wonder what time complexity does Javascript Math functions have 🤔.

Andrew Healey • May 21 '19

The variance is very interesting. I wonder if Chrome throttles certain calculations.

StefanT123 • May 21 '19

I think it does.

Abhishek Gupta • Oct 19 '19 • Edited

This solution is faster for large N, slower for small N.
jsben.ch/mOl4l


/**
 * @param {number} N
 * @return {number}
 */

const pow = function (base, n) {
    if (n==0)
        return 1

    if (n==1)
        return base

    if (n&1) 
        return base*pow(base, n-1)
    else {
        const half = pow(base, Math.floor(n/2))
        return half*half
    }
}

var fib = function(N) {
    const sqrt5 = 2.23606797749979
    const num = 1.618033988749895
    const num2 = -0.6180339887498948
    return Math.round(
        ( pow(num, N) - pow(num2, N) ) / sqrt5
    )
};

fib(NUM);

Using precomputed values for constants and using matrix expo for calculating a^b (which is log(n))