Profifrage: java.lang.StackOverflowError bei BigInteger

Status
Nicht offen für weitere Antworten.

tconz

Mitglied
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".

Code:
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

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


Code:
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
 
T

tconz(unlogged)

Gast
Hi,

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

Thx Tobi
 

Bleiglanz

Gesperrter Benutzer
Code:
        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

Mitglied
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

Top Contributor
Moin,

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

Gruß
Mag1c
 

Bleiglanz

Gesperrter Benutzer
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

Mitglied
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

Bekanntes Mitglied
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:
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:
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

Top Contributor
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
 

Bleiglanz

Gesperrter Benutzer
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

Bekanntes Mitglied
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
 

KISS

Bekanntes Mitglied
Johanness hat gesagt.:
KISS hat gesagt.:
0xdeadbeef hat gesagt.:
-> iterativ implementieren
geht imho nicht, siehe vorheriges post
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

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

Bleiglanz

Gesperrter Benutzer
Den Betrag von 800000 kann man auf 4058724244674144189174 verschiedene Arten herausgeben

stimmt das?
 
B

bygones

Gast
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

Gesperrter Benutzer
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

Bekanntes Mitglied
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

Bekanntes Mitglied
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
 

Bleiglanz

Gesperrter Benutzer
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

Bekanntes Mitglied
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

Gesperrter Benutzer
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

Code:
    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 :)
Code:
    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];
    }
 
J

Johanness

Gast
deathbyaclown hat gesagt.:
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 ^^

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

Gesperrter Benutzer
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))

Code:
w(40000000,6)=1268063927968388376702968894171 
w(400000000,6)=126805864966686262787621629990600834
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
D Hat Java eine Library um JavaScript auszuwerten? Allgemeine Java-Themen 2
Zrebna Wieso sind eigentlich JUnit-Tests in src/test/java platziert - nur Konvention? Allgemeine Java-Themen 7
N LlaMA, KI, java-llama.cpp Allgemeine Java-Themen 39
V Java-Codierungsherausforderung: Navigieren durch die Macken der Datumsmanipulation Allgemeine Java-Themen 2
E Output Fehler (Java-Programm Kuchen) Allgemeine Java-Themen 11
M java: unexpected type Allgemeine Java-Themen 2
harrytut Java Input/Output Tests Junit Allgemeine Java-Themen 3
B Java Discord bot auf ein Root Server? Allgemeine Java-Themen 1
BetziTheRealOne Java PKIX path building failed as non Admin Allgemeine Java-Themen 15
D Linux, Java-Version wird nicht erkannt bzw. welche Einstellung fehlt noch? Allgemeine Java-Themen 19
KonradN Java 21 Release Allgemeine Java-Themen 5
V Umgang mit fehlenden Daten in einer Java-Datenanalyseanwendung Allgemeine Java-Themen 5
P Fehler: Hauptklasse Main konnte nicht gefunden oder geladen werden Ursache: java.lang.ClassNotFoundException: Main Allgemeine Java-Themen 24
K Java Anwendung machen Anleitung Allgemeine Java-Themen 5
G java.io.listFiles() Allgemeine Java-Themen 3
8u3631984 Frage zu Java Streams min / max Allgemeine Java-Themen 17
S Java Programm lässt sich vom USB-Stick starten, aber nicht von HDD Allgemeine Java-Themen 16
K Java-Projekt Allgemeine Java-Themen 11
K Java-Projekt Allgemeine Java-Themen 0
ruutaiokwu Welcher Browser unterstützt heutzutage noch Java Applets? Allgemeine Java-Themen 5
Jose05 Java-Klasse im extra cmd-Fenster ausführen Allgemeine Java-Themen 3
rode45e Java Threads Allgemeine Java-Themen 4
G java.io.listFiles() Allgemeine Java-Themen 2
N Java Dynamic Proxy Allgemeine Java-Themen 3
N Leichte Java Gegner Ki Allgemeine Java-Themen 10
A Java modul Problem Allgemeine Java-Themen 4
Thomasneuling Java Jar datei erstellen, von Projekt, dass auch Javafx Dateien, FXML Dateien und CSS Dateien, sowie Bilder enthält? Allgemeine Java-Themen 14
V Funktionale Schnittstelle in Java Allgemeine Java-Themen 3
OnDemand Java String in Hashmap als Key NULL Allgemeine Java-Themen 27
urmelausdemeis Exception in thread "main" java.lang.Error: Unresolved compilation problem: Allgemeine Java-Themen 7
berserkerdq2 Wenn ich bei Intelij javafx mit maven importieren will, muss ich das in die pom.xml reintun, aber warum noch in module-info.java? Allgemeine Java-Themen 3
KonradN Java 20 am 21. März Allgemeine Java-Themen 1
O Java Website Stock Bot Allgemeine Java-Themen 3
J Front-/Backend in Java Allgemeine Java-Themen 14
doopexxx JAVA Google Webcrawler Allgemeine Java-Themen 1
J JavaScript innerhalb eines Java Projekts ausführen Allgemeine Java-Themen 2
A Java Programm erstellen hilfe Allgemeine Java-Themen 10
G java.lang.NoClassDefFoundError: org/aspectj/lang/Signature Allgemeine Java-Themen 2
lalex1491 Java Aktienkurse nachfragen Allgemeine Java-Themen 4
J Class to link Java Allgemeine Java-Themen 4
V Wie funktioniert das Schlüsselwort "final" von Java? Allgemeine Java-Themen 19
mrStudent Inferenz JAVA Allgemeine Java-Themen 6
U URI Rechner (Java Script) Allgemeine Java-Themen 7
TheSkyRider Java Geburtsdatum Textfeld Allgemeine Java-Themen 7
mihe7 Java 19 JavaDocs: Browserintegration Allgemeine Java-Themen 0
Encera Gleichzeitiges Ausführen und verbinden von 2 Java-Klassen über die Eingabeaufforderung und Eclipse Allgemeine Java-Themen 21
H Java Rechner Programmierung der Mathematik Allgemeine Java-Themen 33
Lennox Schinkel Java Kara Auf einen Java Host laufen lassen Allgemeine Java-Themen 17
C Fußnoten von DocX mit Java Allgemeine Java-Themen 2
C Fußnoten in DocX mit Java Allgemeine Java-Themen 1
M Aussagenlogik in Java Programmieren Allgemeine Java-Themen 22
B Per Java Word Dokument schreiben? Allgemeine Java-Themen 8
krgewb Java-Bibliothek für ONVIF Allgemeine Java-Themen 1
KonradN Oracle übergibt (Java Teile der) GraalVM Community Edition an OpenJDK Community Allgemeine Java-Themen 2
Momo16 Brauche Hilfe - Java Projekt kann nicht erstellt werden Allgemeine Java-Themen 12
B Java mit command line und jars benutzen? Allgemeine Java-Themen 18
M Java Überprüfen ob .exe-Datei bereits ausgeführt wird Allgemeine Java-Themen 2
B HTTP Allgemeine Fragen über Suchmaschine nutzen mit Java Allgemeine Java-Themen 20
Mick P. F. Wie kriege ich die Fehlermeldung "java: symbol lookup error: ..." weg? Allgemeine Java-Themen 11
K Nachhilfe Java Allgemeine Java-Themen 11
KonradN Java 19 Allgemeine Java-Themen 11
F IDEA IntelliJ Java Songliste erstellen Allgemeine Java-Themen 6
TheSepp Java bestimmtes Array auf den Wert 0 setzen Allgemeine Java-Themen 32
B Java Reflection Probleme beim wehcselseitigen Referenzieren zweier Klassen/Objekte Allgemeine Java-Themen 14
Sachinbhatt Sind alle Methoden in Java implizit virtuell Allgemeine Java-Themen 2
E Java und integrierte Grafikkarten Allgemeine Java-Themen 18
Sachinbhatt Wie wird die Typumwandlung bei Mehrfachvererbung in Java implementiert? Allgemeine Java-Themen 3
Peterw73 Hilfe bei Java gesucht Allgemeine Java-Themen 3
A Java unter Win 10 Allgemeine Java-Themen 1
B Woher kommen die Bildschirmkoordinaten beim java Robot? Allgemeine Java-Themen 14
P9cman java.Lang Klassen fehlen in JRE System Library Allgemeine Java-Themen 1
T Java Robot Class - Bot Allgemeine Java-Themen 3
E Wie Java Heap Space vergrößern? Allgemeine Java-Themen 3
B Java Programm auf virutellem Desktop laufen lassen? Allgemeine Java-Themen 1
D VBA Code mit Java ausführen möglich? Allgemeine Java-Themen 10
berserkerdq2 Threads, wie genau läuft das in Java ab? (Ich kann Threads erstellen und nutzen, nur das Verständnis) Allgemeine Java-Themen 6
izoards Java Home Pfad unabhängig von der Version Allgemeine Java-Themen 7
N JAVA-Code mit Grafikfenster zeichnet in Windows, aber nicht Mac. Allgemeine Java-Themen 4
L Java überprüfen lassen, ob sich ein gegebener Pfad / das Programm an sich auf einer CD oder Festplatte befindet Allgemeine Java-Themen 14
KonradN CVE-2022-21449: Fehler in Java bei Signaturprüfung Allgemeine Java-Themen 20
berserkerdq2 Java sql Allgemeine Java-Themen 15
JordenJost Unverständlicher Java code? Allgemeine Java-Themen 21
LimDul XSD To Java - Überschreiben von Assoziationen Allgemeine Java-Themen 1
Aartiyadav Comparisons and Swapa in Bubble-sort Java Allgemeine Java-Themen 6
KonradN Java 18 Allgemeine Java-Themen 8
N Statistische Auswertung von Logfiles (Einlesen, auswerten und grafische Aufbereitung von logfiles) mit Java Allgemeine Java-Themen 9
ME2002 Fragen aus einer Java Klausur Allgemeine Java-Themen 67
Z Mit Java 8+ Streams Zeilen nummern zu Zeilen hinzufügen Allgemeine Java-Themen 17
M Verständnisfrage java.util.TimerTask Allgemeine Java-Themen 2
V Hilfe mit Java Code Allgemeine Java-Themen 4
S Processing Java Code verstehen Allgemeine Java-Themen 4
O Newton Algorithmus Java Allgemeine Java-Themen 1
P Java Quellen finden Allgemeine Java-Themen 3
M Java Analyse/ SWOT-Analyse Allgemeine Java-Themen 13
J c Programm läuft nicht in compilierter Version des Java Projektes Allgemeine Java-Themen 7
Atten007 Java-Klasse auf macOS entpacken? Allgemeine Java-Themen 2
E java mithilfe url .jar datei öffnen Allgemeine Java-Themen 9
M Warum hat Java dieses und jenes nicht... Allgemeine Java-Themen 8
E Java .exe Datei mit args starten Allgemeine Java-Themen 2
LimDul Kam eine java.net.URL zu einer HashMap und ging als DNS Anfrage wieder heraus Allgemeine Java-Themen 18

Ähnliche Java Themen

Neue Themen


Oben