高效计算Lucas序列

Question

我正在实现p+1分解算法。为此，我需要计算lucas序列的元素，其定义如下：

(1) x_0 = 1, x_1 = a
(2) x_n+l  =  2 * a * x_n - x_n-l

我递归地实现了它(C#)，但是对于更大的索引来说效率很低。

static BigInteger Lucas(BigInteger a, BigInteger Q, BigInteger N)
    {
        if (Q == 0)
            return 1;
        if (Q == 1)
            return a;
        else
            return (2 * a * Lucas(a, Q - 1, N) - Lucas(a, Q - 2, N)) % N;
    }

我也知道

(3) x_2n = 2 * (x_n)^2 - 1
(4) x_2n+1 = 2 * x_n+1 * x_n - a
(5) x_k(n+1) = 2 * x_k * x_kn - x_k(n-1)

(3)和(4)应该有助于计算更大的Qs。但我不确定是怎么做到的。不知何故，我想是Q的二进制形式。

任何帮助都是非常感谢的。

Answer 1

Here可以看到如何使用矩阵的幂来求出第N个Fibbonaci数

      n
(1 1)
(1 0)

您可以利用这种方法来计算卢卡斯数，使用矩阵(对于您的情况是x_n+l = 2 * a * x_n - x_n-l)

        n
(2a -1)
(1   0)

注意，矩阵的N次方可以通过exponentiation by squaring的对数(N)矩阵乘法来求出

Answer 2

(3) x_2n = 2 * (x_n)^2 - 1
(4) x_2n+1 = 2 * x_n+1 * x_n - a

每当你看到2n时，你应该认为“这可能表示一个偶数”，同样，2n+1很可能意味着“这是一个奇数”。

您可以修改x索引，以便在左边有n (为了更容易理解这与递归函数调用的对应关系)，只是要注意四舍五入。

3) 2n     n
=> n      n/2

4) it is easy to see that if x = 2n+1, then n = floor(x/2)
     and similarly n+1 = ceil(x/2)

因此，对于#3，我们有：(在伪代码中)

if Q is even
   return 2 * (the function call with Q/2) - 1

对于#4：

else // following from above if
   return 2 * (the function call with floor(Q/2))
            * (the function call with ceil(Q/2)) - a

然后，我们还可以加入一些memoization，以防止多次计算相同参数的返回值：

• 保存Q值到返回值的映射。
• 在函数开始处，检查映射中是否存在Q的值。如果存在，则返回相应的返回值。
• 返回时，将Q的值和返回值添加到映射中。<代码>H218<代码>F219

Answer 3

第n个Lucas数的值为：

​

​

可以使用Exponentiation by squaring来评估函数。例如，如果为n=1000000000，则n= 1000 * 1000^2 = 10 * 10^2 * 1000^2 = 10 * 10^2 * (10 * 10^2 )^2。通过这样简化，可以大大减少计算次数。