kostenloser Webspace werbefrei: lima-city

Rekursion schnell berechnen

lima-city → Forum → Programmiersprachen → Java

1. Autor dieses Themas

   j*********r

   22:20, 22.5.2017

   Hallo zusammen!
   Für ein Projekt muss ich ein großes Folgenglied k einer rekursiven Funktion möglichst schnell berechnen. Das Projekt ist bereits fast fertig und vollkommen in Java implementiert, weshalb mir auch nur Implementierungen in Java helfen.
   Die Rekursion definiert sich so:
   
   
   
   
   
   Ich suche dann x(k,w), wobei ich w bereits vorher bestimme. Das Problem ist aber: k und w sind beides sehr große Zahlen und dementsprechend lange dauert das.
   Mein erster, mittlerweile verworfener Ansatz führte die Rekursion einfach nach und nach durch und schrieb alle Rekursionsschritte in eine ArrayList<BigInteger>. Das war jedoch sehr ineffizient und sehr langsam und außerdem ist die Größe von ArrayLists auf die Größe von Integern beschränkt.
   Der nächste Ansatz verzichtete auf die Liste und speicherte einfach nur x(n-1) und x(n-2), was auch genügt, weil ich ja nur das k-te Folgenglied benötige. Aber auch das ist deutlich zu langsam für die Größenordnung, in der sich die Variablen befinden.
   Gibt es eine Möglichkeit, diese Rekursion schneller zu machen? Im Folgenden mal der bisherige Source-Code:
   
   

   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;

   
   
   Eine naheliegende Lösung wäre natürlich einfach eine explizite Funktion für die Rekursion zu finden. Das ist auch weiter kein Problem, diese kann durch
   
   
   
   bestimmt werden. Der Haken: In Java sind keine Methoden zur Potenzierung für die BigInteger / BigDecimal-Objekte implementiert. Es ist unerlässlich, dass der Algorithmus eine exakte Ausgabe macht. Mit welchen Algorithmen lässt sich die explizite Funktion also für große Zahlen dennoch effizient und schneller als die Rekursion selber berechnen?
   
   
   mfg
   Jonas
   
   Edit: Variablenchaos beseitigt
   
   Beitrag zuletzt geändert: 23.5.2017 12:36:03 von jonas-bayer

2. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

   lima-city: Gratis werbefreier Webspace für deine eigene Homepage

3. fuerderer

   fuerderer hat kostenlosen Webspace.

   7:32, 23.5.2017

   Ich kann bei dem Problem nicht ganz folgen, das beginnt schon bei der Definition der rekursiven Funktion:
   

   jonas-bayer schrieb:
   

   Was bedeutet ? x ist doch für zwei Argumente definiert. Meintest du ?
   
   

   jonas-bayer schrieb:
   

   Und hier werden zwei geöffnete Klammern nicht wieder geschlossen.
   
   

   jonas-bayer schrieb:
   Der Haken: In Java sind keine Methoden zur Potenzierung für die BigInteger / BigDecimal-Objekte implementiert.

   Ich sehe bei BigInteger eine Methode namens "pow". Richtig, sie nimmt ein Argument vom Typ int als Exponent entgegen, aber generell sollte das reichen. Wenn du noch größere Exponenten hast, wirst du das Ergebnis auch kaum noch abbilden können.
   
   So wie ich das einschätze, darf eine sehr große Zahl sein, ohne groß Probleme zu verursachen. Wenn aber ebenfalls "sehr groß" wird, also allerspätestens bei ca. 12 Dezimalziffern, wird die ganze Berechnung unpraktikabel, weil dann das Ergebnis einfach viel zu groß wird.
   
4. Autor dieses Themas

   j*********r

   12:50, 23.5.2017

   So, die Typos hätte ich jetzt beseitigt.
   
   Die Methode pow war mir tatsächlich auch schon aufgefallen - weil meine Zahlen Integer.MAX_VALUE deutlich überschreiten, nützt sie mir aber wenig. Meine Ergebnisse (zumindest den Teil, der unabhängig von der Folge ist) kann ich mit BigInteger-Objekten dennoch aber problemlos abbilden. Das sind dann teilweise Zahlen über 10^5000
   
   

   fuerderer schrieb:
   So wie ich das einschätze, darf eine sehr große Zahl sein, ohne groß Probleme zu verursachen. Wenn aber ebenfalls "sehr groß" wird, also allerspätestens bei ca. 12 Dezimalziffern, wird die ganze Berechnung unpraktikabel, weil dann das Ergebnis einfach viel zu groß wird.
   

   
   Und genau deshalb suche ich ja nach einer Lösung, um das ganze doch noch möglichst effizient zu berechnen.
   
   mfg
   Jonas
   
   Beitrag zuletzt geändert: 23.5.2017 12:51:23 von jonas-bayer

5. fuerderer

   fuerderer hat kostenlosen Webspace.

   15:47, 23.5.2017

   jonas-bayer schrieb:
   Die Methode pow war mir tatsächlich auch schon aufgefallen - weil meine Zahlen Integer.MAX_VALUE deutlich überschreiten, nützt sie mir aber wenig.

   Hättest du ein konkretes Beispiel für und , bei dem den Wert Integer.MAX_VALUE überschreitet? Ehrlich gesagt glaube ich kaum, dass das Ergebnis dann noch annähernd in der Größenordnung 10^5000 liegt.
   
   Theoretisch gibt es auch noch die Möglichkeit, die Potenz bitweise durchzuführen.
   Pseudocode zur Berechnung von a^b:
   

   e = a
   Stelle b binär dar
   Ignoriere die 1 ganz vorne bei b
   Iteriere von links nach rechts über die restlichen Bit von b:
       e = e * e
       Falls Bit = 1:
           e = e * a
   Gib e zurück

   
   
   Ein anderes Problem ist aber noch die Berechnung der Wurzel, denn dabei kommt kein ganzzahliger Zwischenwert heraus. Erst das Endergebnis ist wieder eine Ganzzahl.
   
   Man könnte jetzt durch vorheriges Multiplizieren und anschließendes Dividieren auch "Nachkommastellen" in die BigInteger Objekte einfügen, muss aber aufpassen, dass die Genauigkeit am Ende auch ausreicht um auf den richtigen Ganzzahlwert runden zu können.
   
   Dann ist mir noch aufgefallen, dass schon sehr früh kleiner als 1 ist und sich bei größeren Argumenten sehr schnell immer mehr der 0 annähert. In der Praxis wird man diesen Teil der Formel also ignorieren können.

6. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

   lima-city: Gratis werbefreier Webspace für deine eigene Homepage

Dir gefällt dieses Thema?