不同种子的 O log(N) 中的斐波那契数列

Question

此代码是从数学 wiki 中的伪代码翻译而来，用于解决 O log(n) 中的斐波那契问题。

当你想改变斐波那契 (1,0) 的种子时，问题就来了，这是最数学的问题，也是比编程更复杂的问题...

所以...将 A 和 B 放在哪里开始，例如种子 5,6？

感谢您的宝贵时间！

public static BigInteger Fib(int A, int B, int n)
        {
            if (n <= 0)
                return 0;

            n = n - 1;
            _auxOne = 0;
            _auxTwo = 1;

            Matrix[0, 0] = _auxTwo; //a
            Matrix[0, 1] = _auxOne; //b
            Matrix[1, 0] = _auxOne; //c
            Matrix[1, 1] = _auxTwo + _auxOne; //d

            while (n > 0)
            {
                if (n % 2 != 0)
                {
                    _auxOne = Matrix[1, 1] * Matrix[0, 1] + Matrix[1, 0] * Matrix[0, 0]; //(db+ca)
                    _auxTwo = Matrix[1, 1] * (Matrix[0, 1] + Matrix[0, 0]) + Matrix[1, 0] * Matrix[0, 1]; //(d(b+a)+cb)
                    Matrix[0, 0] = _auxOne;
                    Matrix[0, 1] = _auxTwo;
                }
                _auxOne = BigInteger.Pow(Matrix[1, 0], 2) + BigInteger.Pow(Matrix[1, 1], 2); //(c²+d²)
                _auxTwo = Matrix[1, 1] * (2 * Matrix[1, 0] + Matrix[1, 1]); //(d*(2c+d))
                Matrix[1, 0] = _auxOne;
                Matrix[1, 1] = _auxTwo;

                n = n / 2;
            }
            return Matrix[0, 0] + Matrix[0, 1];
        }

Answer 1

好的，正如我之前在评论中所写的，实际上我们只需要 "normal" 斐波纳契矩阵乘以我们修改后的带种子矩阵，所以我的代码的一部分是现有 OP 代码的突变。我只做了 2 处更改——我需要整个矩阵而不是计算结果，并将 BigInteger 替换为 Int64 以避免额外的引用。

public static Int64 PerversationFib(int A, int B, int n) 
{
    if (n <= 0)
        return 0;

    if (n == 1)
        return A + B;
    else 
    {
        Int64[,] myMatrix = new Int64[2, 2] { { A , B }, { B, A+B} };
        Int64[,] fibMatrix = Fib(n);

        //a11·b11 + a12·b21
        return myMatrix[0, 0] * fibMatrix[0, 0] + myMatrix[0, 1] * fibMatrix[1, 0];  

    }

}

public static Int64[,] Fib( int n)
{
    if (n <= 0)
        return null;

    //n = n - 1;
   Int64 _auxOne = 0, _auxTwo = 1;
   Int64[,] Matrix = new Int64[2, 2]; 

   Matrix[0, 0] = _auxTwo; //a
   Matrix[0, 1] = _auxOne; //b
   Matrix[1, 0] = _auxOne; //c
   Matrix[1, 1] = _auxTwo + _auxOne; //d


    while (n > 0)
    {
        if (n % 2 != 0)
        {
            _auxOne = Matrix[1, 1] * Matrix[0, 1] + Matrix[1, 0] * Matrix[0, 0]; //(db+ca)
            _auxTwo = Matrix[1, 1] * (Matrix[0, 1] + Matrix[0, 0]) + Matrix[1, 0] * Matrix[0, 1]; //(d(b+a)+cb)
            Matrix[0, 0] = _auxOne;
            Matrix[0, 1] = _auxTwo;
        }
        _auxOne = Matrix[1, 0] * Matrix[1, 0]  +Matrix[1, 1]*Matrix[1,1]; //(c²+d²)
        _auxTwo = Matrix[1, 1] * (2 * Matrix[1, 0] + Matrix[1, 1]); //(d*(2c+d))
        Matrix[1, 0] = _auxOne;
        Matrix[1, 1] = _auxTwo;

        n = n / 2;
    }
    Matrix[1, 0] = Matrix[0, 1];
    Matrix[1, 1] = Matrix[0, 0]+Matrix[0,1] ;
    return Matrix;
}

不同种子的 O log(N) 中的斐波那契数列

Fibonacci in O log(N) with different seeds

c#

algorithm

big-o

time-complexity

space-complexity