# Profifrage:  java.lang.StackOverflowError bei BigInteger



## tconz (25. Okt 2005)

Hi
wir haben folgenden Code, der bis G = 400 ohne Probleme funktioniert. Jedoch soll er bis 4.000.000 funktionieren. Wir bekommen jedoch beim Starten sofort die Meldung "StackOverflow".


```
public class Aufgabe4 {
static int betrag [] = {0, 3, 5, 7, 13, 17, 29};
// Muenz-Nummern : 0 1 2 3 4 5 6 7
static long Tab [][];
    public static BigInteger w (double G, int i)
    { 
        return (G == 0) ? 
                new BigInteger("1"):
                    ((G < 0)||i == 0) ?
                            new BigInteger("0"):
                                (w(G,i-1)).add(w (G-betrag[i],i));
    }
    public static void main (String[] args)
    {
        double G = 4000000;
        //Tab = new long [G+1][6];
        System.out.println("Den Betrag von "+G+" kann man auf "+
                w (G,6)+ " verschiedene Arten herausgeben.");
    }
}
```

Thx Tobi[/code]


----------



## Tobias (25. Okt 2005)

Da wird wohl die maximal mögliche Rekursionstiefe überschritten:



```
public static BigInteger w (double G, int i)
    {
        return (G == 0) ?
                new BigInteger("1"):
                    ((G < 0)||i == 0) ?
                            new BigInteger("0"):
                                (w(G,i-1)).add(w (G-betrag[i],i));
    }
```

Sollte ich richtig liegen, reicht der zugewiesene Arbeitsspeicher für die JVM nicht aus - werdet ihr euch wohl ein effizienteres Verfahren überlegen müssen.

mpG
Tobias


----------



## tconz(unlogged) (25. Okt 2005)

Hi,

hast du uns einen Tipp in welche Richtung das gehen könnte?

Thx Tobi


----------



## bygones (25. Okt 2005)

versucht es mit einer Iterativen Lösung....


----------



## Bleiglanz (25. Okt 2005)

```
return (G == 0) ?
// doubles mit == vergleichen??
                new BigInteger("1"):
// warum mit new, ist doch schon da (BigInteger.ONE)
                    ((G < 0)||i == 0) ?
                            new BigInteger("0"):
// warum: ist doch schon da BigInteger.ZERO
                                (w(G,i-1)).add(w (G-betrag[i],i)); 
// jetzt kommts: eine Doppelrekursion, braucht man die wirklich?
```
kannst du mal erklären, was der Code genau machen soll


----------



## tconz (25. Okt 2005)

Hi,
du hast einen Betrag z.B. 100xx und man soll jetzt herausbekommen wie viele Möglichkeiten es gibt, den Betrag auszubezahlen, wenn man 3, 5, 7, 13, 17, 29.xx hat.

xx = Währung


----------



## Mag1c (26. Okt 2005)

Moin,

jaja, die Aufgabe ist schon klar. Aber wie funktioniert der Algorithmus, den ihr da benutzt ? Erklär das doch mal 

Gruß
Mag1c


----------



## Bleiglanz (26. Okt 2005)

G=4.000.000 

mit Beträge wie

3, 5, 7, 13, 17, 29

???

habt ihr auch nur eine UNGEFÄHRE Vorstellung davon, wie gross diese Zahl sein wird? Am besten ihr besorgt euch BigBigInteger und einen Rechner mit 40000000000 RAM 

und:

der Algo ist doch falsch? 

[edit] das nehm ich zurück, das folgende ist Quatsch: die Rekursion ist schon OK  [/edit]

(w(G,i-1)).add(w (G-betrag_,i)); 

es wird immer nur G-betrag getestet, man sollte doch wohl für jedes j zwischen 0 und i jeweils G-betrag[j] testen?

genauso bei w(G,i-1): es wird nur getestet, wie man ohne Münze i klar kommt, auch hier sollte doch jede Teilmenge mit i-1 Münzen getestet werden

warum ist 0 im betragsarray -> wegschmeissen, ist doch sinnlos

und: wie und wo wird bei der Zählung berücksichtigt, dass 29 17 29 das gleiche ist wie 17 29 29?_


----------



## tconz (26. Okt 2005)

Hi,
also der algo bringt bis 400 richtige Ergebnisse. 

mathematisch sieht das so aus:


W(G,i) = W(G-Betrag_,i) + W(G, i-1)

Ergebniss bei G = 4000000 ist 12681167118690474858926434 (aus Aufgabe)

_


----------



## KISS (26. Okt 2005)

tconz hat gesagt.:
			
		

> mathematisch sieht das so aus:
> W(G,i) = W(G-Betrag_,i) + W(G, i-1)
> _


_

also mathematisch wuerde ich sagen



		Code:In die Zwischenablage kopieren


h(n)=1 //hilfsfunktion, 1 reciht erstmal foellig

           / a=0  1
f(a,n)= | n=0   0
           \ f(a,n-1) + f(a-h(n),n)  // kann reduziert werden zu f(a,n-1) + f(a-1,n)


das erinnert doch stark an peters definition der ackermann funktion



		Code:In die Zwischenablage kopieren


a(0,m)=m+1
a(n+1,0)=a(n,1)
a(n+1,m+1)=a(n,a(n+1,m))


das verhalten ist sogar aehnlich

f(2,5)=		15
a(2,5)=		13
f(2,10)=		55
a(2,10)=		23
f(3,5)=		35
a(3,5)=		253
f(3,10)=		220
a(3,10)=		8189

ich gehe also mal davon aus das diese problem nicht turing-loesbar ist (also ab bestimmten groessen von a,n), den beweis will ich aber nicht fuehren, wenn es dich interessiert hole dir den schöning aus der bibliothek, da ist ei beweis mittels struktureller induktion das die ackermann funktion nicht primitiv rekursiv ist_


----------



## 0xdeadbeef (26. Okt 2005)

BigInteger sollte nicht das Problem sein, also liegt's wohl an der Rekursionstiefe, bzw. was pro Rekursion auf den Stack gelegt werden muß.
Ein Anfang wäre schon mal, die statischen Elemente BigInteger.ONE und BigInteger.ZERO zu benutzen anstatt andauernd neue Instanden von 0 und 1 anzulegen.

Eine Rekursionsteife von 4 Millionen (wenn ich das richtig verstanden habe), kannst Du Dir allerdings in die Haare schmieren. 
-> iterativ implementieren


----------



## KISS (26. Okt 2005)

0xdeadbeef hat gesagt.:
			
		

> -> iterativ implementieren


geht imho nicht, siehe vorheriges post


----------



## Bleiglanz (26. Okt 2005)

die iterationANZAHL ist ja viel viel grösser:

nur im Fall G==0 wird ja genau 1 addiert - sonst passiert nämlich überhaupt nix - d.h. wenn das Ergebnis 

12681167118690474858926434 

lautet, dann wird genausooft die Funktion w mit G==0 aufgerufen...

@KISS: da ist nix Ackermannisches dabei, sonste wären die Zahlen nicht so "klein"


----------



## KISS (26. Okt 2005)

Bleiglanz hat gesagt.:
			
		

> @KISS: da ist nix Ackermannisches dabei, sonste wären die Zahlen nicht so "klein"



bei der ackermann funktion geht es nicht im die groesse der zahlen sondern um die anzahl der rekursionen. siehe auch rekursiv, mu-rekursiv und primitiv-rekursiv.

wie schon gesagt, den beweis das die funktion nicht primitv-rekursiv ist will ich mir nicht antun, aber sieht imho ganz danach aus


----------



## Bleiglanz (26. Okt 2005)

imho überhaupt nicht 

nur O(2^n), das ist alles


----------



## Johanness (26. Okt 2005)

KISS hat gesagt.:
			
		

> 0xdeadbeef hat gesagt.:
> 
> 
> 
> ...



Na ja, gehen tut das immer, jede rekursive Funktion lässt sich auch iterativ programmieren - ob das ein elegantes Programm wird, ist eine andere Frage.

Johannes


----------



## KISS (26. Okt 2005)

Johanness hat gesagt.:
			
		

> KISS hat gesagt.:
> 
> 
> 
> ...



sorry, aber das ist nun wirklich unsinn (nimmt man mal lookup tables raus).


----------



## Bleiglanz (26. Okt 2005)

Den Betrag von 800000 kann man auf 4058724244674144189174 verschiedene Arten herausgeben

stimmt das?


----------



## bygones (26. Okt 2005)

Johanness hat gesagt.:
			
		

> Na ja, gehen tut das immer, jede rekursive Funktion lässt sich auch iterativ programmieren - ob das ein elegantes Programm wird, ist eine andere Frage. Johannes


hoffe bring das jetzt nicht durcheinander.... alles iterative kann rekursiv gelöst werden, aber nicht alles rekursiv iterativ (z.b. KochKurve) - oh man Studium ist zu lange weg ^^


----------



## Bleiglanz (26. Okt 2005)

Hmmpf

Den Betrag von 1600000 kann man auf 129864160114100245938027 verschiedene Arten herausgeben 

weiter gehts nicht

irgendwie funktioniert weder -Xss (auch nicht mit  ulimit -s als root), kennt jemand eine "zuverlässige" Methode wie man unter Linux die Stackgrösse für die JVM hochsetzen kann??


----------



## KISS (26. Okt 2005)

Bleiglanz hat gesagt.:
			
		

> Hmmpf
> Den Betrag von 1600000 kann man auf 129864160114100245938027 verschiedene Arten herausgeben
> weiter gehts nicht
> irgendwie funktioniert weder -Xss (auch nicht mit  ulimit -s als root), kennt jemand eine "zuverlässige" Methode wie man unter Linux die Stackgrösse für die JVM hochsetzen kann??



ich dachte ulimit wirkt sich aus sicherheitsgruenden sowieso nicht mehr auf alle parameter aus.
und wieso Xss, die rekursion soll doch raus *g*

nebenbei, der algo falsch ist  w(7,6)=1 aber aus  { 0, 3, 5, 7, 13, 17, 29 } laesst sich 7 nicht loesen, ebendso 11.


----------



## KISS (26. Okt 2005)

Bleiglanz hat gesagt.:
			
		

> Den Betrag von 800000 kann man auf 4058724244674144189174 verschiedene Arten herausgeben
> 
> stimmt das?



sieht so aus, aber der algo ist immer noch falsch und ich habe immer noch keine wirklich iterative loesung *grmbl*

f(800000,6)=4058724244674144189174


----------



## KISS (26. Okt 2005)

mit falschem algo

f(3999999,6)=12681151267386126258831799


----------



## Bleiglanz (27. Okt 2005)

w(3999999,6) = 12681151267386126258831799 stimmt schon

w(7,6)=1 ist klar, weil die 7er Münze dabei ist

w(11,6)=1 ist auch klar, ist ja 5+3+3

w(4000000,6) = 12681167118690474858926434 stimmt wohl auch

w(10000000,6) = 1238360861741281125040952761

dann reicht der Speicher nicht mehr


----------



## KISS (27. Okt 2005)

Bleiglanz hat gesagt.:
			
		

> w(3999999,6) = 12681151267386126258831799 stimmt schon
> w(7,6)=1 ist klar, weil die 7er Münze dabei ist
> w(11,6)=1 ist auch klar, ist ja 5+3+3



verdammt, lesen muss man koennen



			
				Bleiglanz hat gesagt.:
			
		

> w(4000000,6) = 12681167118690474858926434 stimmt wohl auch
> w(10000000,6) = 1238360861741281125040952761
> dann reicht der Speicher nicht mehr



wieso speicher? der specherverbrauch ist bei mir relativ konstant, es dauert nur saulange (laut performance monitor gehen 90% der zeit bei new BigInteger und add drauf)


----------



## Bleiglanz (27. Okt 2005)

> der specherverbrauch ist bei mir relativ konstant,


wie geht das mit konstantem Speicherverbrauch?

ich hab mich eben für die "Schnell-und-Speicherfresser" Lösung entschieden; d.h. um w(G,6) zu berechnen, berechne ich effektiv ALLE werte w(a,b) mit a<=G und b<=6; merke mir aber immer nur den mit einer Münze weniger

hat aber trotzdem den 10Mio Wert in 234 Sekunden ausgespuckt


```
public static BigInteger compute(final int fullAmount, final int[] coinValues) {
        
        final int numCoins = coinValues.length;
        
        BigInteger[] oneCoinLess = new BigInteger[fullAmount + 1];
        Arrays.fill(oneCoinLess, BigInteger.ZERO);

        final BigInteger[] current = new BigInteger[fullAmount + 1];
        oneCoinLess[0] = current[0] = BigInteger.ONE;

        for (int coin = 0; coin < numCoins; coin++) {
            for (int amount = 1; amount <= fullAmount; amount++) {
                current[amount] = (amount >= coinValues[coin]) ? 
                        oneCoinLess[amount].add(current[amount - coinValues[coin]]) : oneCoinLess[amount];
            }
            oneCoinLess = current;
        }
        return current[fullAmount];
    }
```

EDIT (nur der Vollständigkeit halber): dieser Code ist vollkommen verbumfeit -> das Array oneLessCoin ist überflüssig, man muss die "Beträge mit einer Münze weniger" überhaupt nicht aufbewahren 

```
public static BigInteger compute(final int fullAmount, final int[] coinValues) {
        final int numCoins = coinValues.length;
        final BigInteger[] current = new BigInteger[fullAmount + 1];
        Arrays.fill(current, BigInteger.ZERO);
        current[0] = BigInteger.ONE;
        for (int coin = 0; coin < numCoins; coin++) {
            final int coinValue = coinValues[coin];
            for (int amount = coinValue; amount <= fullAmount; amount++) {
                current[amount] = current[amount].add(current[amount - coinValue]);
            }
        }
        return current[fullAmount];
    }
```


----------



## Johanness (27. Okt 2005)

deathbyaclown hat gesagt.:
			
		

> Johanness hat gesagt.:
> 
> 
> 
> ...



Doch, Rekursion und Iteration sind äquivalente Lösungsverfahren.

Anschauliche Erklärung für die Richtung Rekursion --> Iteration:
Jedes rekursive Programm wird vom Compiler in ein iteratives Programm umgewandelt - u.a. unter Verwendung eines Stacks. Und genau das könnte man direkt so programmieren.
Auch unsere Hardware ist nicht rekursiv - spätestens hier muß jede Rekursion aufgelöst werden.

Hier noch ein Zitat aus http://www.rebolforces.com/articles/ria1.html:
In theory, recursion and iteration are equivalent; anything we can do with one, we can do with the other.  In practice, this is like saying that all loops can be written using only WHILE.  That may be true, but having LOOP, REPEAT, and FOREACH certainly makes programming more convenient! Each is the best tool for some purposes, which is also true for recursion and iteration.

Johannes


----------



## Bleiglanz (28. Okt 2005)

Nachtrag:

meine beiden obigen Fragmente sind beide suboptimal :-(

bei 6 Münzen und einem Maximalwert von 29 reicht es, wenn man 6*30=180 BigIntegers beim der Iteration mitschleppt!

(vom Platz mal abgesehen ist der Zeitaufwand dann O(n))


```
w(40000000,6)=1268063927968388376702968894171 
w(400000000,6)=126805864966686262787621629990600834
```


----------

