提高递归的性能

Question

我想计算一个序列的大数，它由以下递归描述：

x(0,w)=1
x(1,w)=w
x(n+1,w)= 2*w*x(n,w)-x(n-1)

我的项目已经在 Java 中实施，也就是说我需要 Java 解决这个问题。

目的是计算x(k,w)，其中w之前已经计算过了，k,w都是BigIntegers。由于k和w很大，计算需要很多时间。

我已经使用 BigIntegers 的 ArrayList 实现了一个解决方案，该解决方案仅适用于小数字。然后，因为我只需要 x(k,w) 而不是序列的所有数字，我可以想出以下解决方案，这仍然很慢：

BigInteger TWO = new BigInteger("2");

BigInteger x_2 = BigInteger.ONE;
BigInteger x_1 = w;

BigInteger x_0 = BigInteger.ZERO;

for(BigInteger i = BigInteger.ONE; i.compareTo(k) < 0; i = i.add(BigInteger.ONE)) {
        x_0 = w.multiply(TWO).multiply(x_1).subtract(x_2);

        x_2 = x_1;
        x_1 = x_0;

    }

return x_0;

你知道提高该算法速度的方法吗？

一个想法是为序列计算一个显式函数，应该是

x(n,w)=1/2*((w+sqrt(w^2-1)^n+(w-sqrt(w^2-1)^n)

但是 Java 没有提供计算 BigInteger/BigDecimal-objects 的幂或平方根的实现方法。人们可以完全避免计算平方根，因为它们稍后会抵消。但是，必须计算二项式系数。因此，我不确定应该实施哪些方法。

你能告诉我，你认为哪种方法是（准确）计算 x(k,w) 的最快最有效的方法吗？

Answer 1

第n项是前两项的线性组合，所有n的系数都相同，所以可以求n次方矩阵 [[2 * w, -1], [1, 0]] 并将其乘以向量 [x_1, x_0]。如果您使用二进制矩阵求幂，则需要 O(log n) 次乘法和加法。此解决方案仅使用整数，因此绝对精确。

提高递归的性能

Improve performance of a recursion

java

algorithm

recursion

performance

biginteger