Leistung einer Rekursion

Question

Ich mag große Zahlen von einer Sequenz berechnen, die durch die folgende Rekursion beschrieben wird:

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

Mein Projekt bereits in Java implementiert ist, das heißt ich brauche eine Java-Lösung dieses Problem.

Ziel ist es, x (k, w) zu berechnen, wobei w vorher berechnet wurde und k, w BigIntegers sind. Da k und w so große Zahlen sind, benötigt die Berechnung viel Zeit.

Ich habe bereits eine Lösung mit einer ArrayList von BigIntegers implementiert, die nur für kleine Zahlen gut funktioniert. Dann, als ich nur x (k, w) müssen und nicht alle Zahlen der Folge konnte ich mit der folgenden Lösung kommen, die noch viel war zu langsam:

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; 

Kennen Sie irgendeine Art und Weise um die Geschwindigkeit dieses Algorithmus zu verbessern?

Eine Idee war es, eine explizite Funktion für die Sequenz zu berechnen, die

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

sein sollte Aber Java bietet keine implementierten Methoden Befugnisse oder Quadratwurzeln von BigInteger/BigDecimal-Objekten zu berechnen. Man kann akut vermeiden, die Quadratwurzeln zu berechnen, da sie sich später aufheben. Aber dann muss man Binomialkoeffizienten berechnen. Daher bin ich mir nicht sicher, welche Methoden ich umsetzen sollte.

Können Sie mir sagen, welche Ihrer Meinung nach der schnellste und effizienteste Weg ist, x (k, w) genau zu berechnen?

Answer 1

Die n -te Begriff ist eine lineare Kombination der beiden vorhergehenden und der Koeffizient sind die gleichen für alle n, so können Sie die n -te Leistung der Matrix [[2 * w, -1], [1, 0]] und multiplizieren sie mit dem Vektor [x_1, x_0] finden. Wenn Sie die Potenzierung der binären Matrix verwenden, benötigen Sie O(log n) Multiplikationen und Additionen. Diese Lösung verwendet nur ganze Zahlen, ist also absolut präzise.