stackOverFlowError

[andreas2505]

Hallo,

habe bei folgender Methode einen StackOverflowError, wenn ich sie in einer anderen Methode aufrufe.
Weiß aber nicht warum.
Kann mir wer helfen?

static BigInteger binom(BigInteger n, BigInteger k) {
	    if (k.compareTo(n.divide(Big2)) == 1) {
	        k = n.subtract(k);
	    }
	    if (k.compareTo(Big0) < 1 || n.compareTo(Big0) < 1) {
	        return Big1;
	    }
	    else {//rekursiver Aufruf
	        return binom(n.subtract(Big1), k.subtract(Big1)).multiply(n).divide(k);
	    }
	}

Die Methode berechnet übrigens den Binomialkoeffizienten

 

[AmunRa]

Was bitte ist Big0,Big1 und Big2

vl ist das der Fehler

 

[andreas2505]

Big0, ... sind die BigIntegerWerte von 0,1,2

das ist auf keinen fall der fehler

 

[Final_Striker]

wahrscheinlich weil die abbruchbedingung nie ausgeführt wird da nur der else fall vorkommt.

edit:

tipp: konstanten schreibt man groß z.b.: ICH_BIN_EINE_KONSTANTE

 

[javimka]

k und n werden einfach immer grösser als Big1 bleiben

 

[maki]

Es gibt da einen Bug unter Windows im Zusammenhang mit Rekursion welche schnell zu einer StackOverflowException führt: http://www.java-forum.org/allgemeine-java-themen/64258-rekursion-stackoverflow.html

 

[javimka]

Ich habs jetzt mal bei mir ausprobiert und es funktioniert! Habe verschiedenes versucht, auch n=10000 und k = 5000 sind kein Problem. Wenn du allerdings noch grösser gehst, dann kommt irgendwann tatsächlich ein StackOverflow, weil du einfach unzählige mal rekursiv in die Methode eintauchen musst. Das Resultet für n=10000 und k=5000 hat übrigens bereits über 3000 Stellen. Was für Zahlen lässt du denn da rein?

 

[andreas2505]

da werden sehr große zahlen (ca. 1024 bit) getestet. Wie kann ich denn das Problem am besten lösen?

 

[javimka]

Grob geschätzt also Zahlen mit 300 Stellen. Da brauchst du ja eine externe Festplatte für das Resultat

Gemäss oben genannten Link kannst du der VM mit dem Parameter -Xms10m angeben, 10000 Rekursionsschritte zu erlauben. Kannst ja mal ausprobieren, wie weit du den Stack erhöhen musst/kannst.

 

[andreas2505]

und wie gebe ich das ein, bzw. schreibe ich das hin?

 

[javimka]

So wie du dein Programm auch sonst startest, einfach noch mit dem Parameter:
java -Xms10m myClass

 

[javimka]

Ich habe das mal analysiert (geschätzt). Für ein festes n erhälst du den höchsten Binomialkoeffizient, wenn das k gerade die Hälfte ist. In diesem Fall ist das Resultat ungefähr n/3.3 Stellen lang.
Beispiel: ncr(64,32) ist eine Zahl mit 19 Ziffern, weil 64/3.3 = 19.
Angenommen du startest dein Programm tatsächlich mit zwei Zahlen mit 300 Stellen, wobei k halb so gross ist, wie n, dann hat das Resultat n/3.3 Stellen, das sind (10^300)/3.3, was immer noch 299 oder 300 Stellen sind.
Die Anzahl Ziffern deines Resultats hat also etwa 300 Ziffern!
Das heisst, dein Resultat wird etwa die Grösse 10^(10^300) haben. Berechnest du den zweier Logarithmus davon erhälst du log2(10^(10^300)) = 10^300*log2(10) > 10^300. Um das Resultat abzuspeichern brauchst du also über 10^300 Bits. Ein Terabyte sind gerade mal 8*1024^4 = 10^13 Bits.

Nicht mal, wenn du jedes Proton im Universums in eine externe-TB-Festplatte verwandeln würdest, hättest annähernd genügend Platz um dein Resultat zu speichern!

(Falls ich in meiner gewagten These Fehler gemacht habe, bitte drauf hinweisen )