は、私は以下の再帰で記述された配列の大きな数字を計算したい再帰

Question

のパフォーマンスを向上させますこの問題。

目的は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の-オブジェクトの権限やsquarerootsを計算するための実装方法を提供していないシーケンスのための明示的な関数を計算することでした。彼らは後で相殺するので、平方根を計算することを避けることができます。しかし、2項係数を計算する必要があります。したがって、どの方法を実装すべきかはわかりません。

あなたは、（正確に）x（k、w）を計算する最も速く効率的な方法だとお考えですか？

Answer 1

n番目の項は、前の両者の線形結合であり、係数は全てnについて同じであるので、あなたは、マトリックス[[2 * w, -1], [1, 0]]のn乗を見つけ、ベクター[x_1, x_0]を掛けすることができます。バイナリ行列累乗を使用する場合は、O(log n)の乗算と加算が必要です。この解は整数だけを使用するので、絶対に正確です。