kostenloser Webspace werbefrei: lima-city


Rekursion schnell berechnen

lima-cityForumProgrammiersprachenJava

  1. Autor dieses Themas

    jonas-bayer

    jonas-bayer hat kostenlosen Webspace.

    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:

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

    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

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

    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. Ich kann bei dem Problem nicht ganz folgen, das beginnt schon bei der Definition der rekursiven Funktion:
    jonas-bayer schrieb:
    Formel: x(n+1,w)= 2*w*x(n,w)-x(n-1)
    Was bedeutet Formel: x(n-1)? x ist doch für zwei Argumente definiert. Meintest du Formel: x(n-1,w)?

    jonas-bayer schrieb:
    Formel: x(n,w)=1/2*((w+sqrt(w^2-1)^n+(w-sqrt(w^2-1)^n)
    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 Formel: w eine sehr große Zahl sein, ohne groß Probleme zu verursachen. Wenn aber Formel: k 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

    jonas-bayer

    jonas-bayer hat kostenlosen Webspace.

    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 Formel: w eine sehr große Zahl sein, ohne groß Probleme zu verursachen. Wenn aber Formel: k 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. 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 Formel: n und Formel: w, bei dem Formel: n 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 Formel: (w-sqrt(w^2-1))^n 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?

Über lima-city

Login zum Webhosting ohne Werbung!