DEV Community

Discussion on: Solving Puzzles With High-Performance JavaScript

View post

Replies for: 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) { ...

Collapse
 
abhishek97 profile image
Abhishek Gupta • • 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 ab (which is log(n))