代码之家 › 专栏 › 技术社区 › zero_cool

bin(n)[3:]中i的等价物是什么:在Javascript中?

modulo fibonacci python javascript

zero_cool · 技术社区 · 7 年前

我正在研究一个返回大斐波那契数模的算法。我发现了一种快速高效的算法,可以使用以下python确定值:

def fib(n):
    v1, v2, v3 = 1, 1, 0    # initialise a matrix [[1,1],[1,0]]
    for rec in bin(n)[3:]:  # perform fast exponentiation of the matrix (quickly raise it to the nth power)
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec == '1':    
            v1, v2, v3 = v1+v2, v1, v2
    return v2

我很想了解如何在javascript中实现这一点,而二进制转换行让我很头疼。这里for循环使用每个整数的二进制转换,我假设从0到n,并将结果截断到3个位置。在循环体内部,还针对1的字符串表示形式对“rec”进行等式检查。有人能打破这个吗?任何洞察都将不胜感激。谢谢

1 回复 | 直到 7 年前

trincot Jakube 7 年前

这是JavaScript(ES6)的等效版本:

function fib(n) {
    let [v1, v2, v3] = [1, 1, 0]; // initialise a matrix [[1,1],[1,0]]
    for (i of (n).toString(2).slice(1)) {  // perform fast exponentiation of the matrix (quickly raise it to the nth power)
        let calc = v2*v2;
        [v1, v2, v3] = [v1*v1+calc, (v1+v3)*v2, calc+v3*v3];
        if (i === '1')
            [v1, v2, v3] = [v1+v2, v1, v2];
    }
    return v2;
}

// Demo
console.log(fib(15));