Aufgabe 5.3
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Übungsblatt 05
Hallo,
folgende Fragen habe ich zur Teilaufgabe e)
Steckt die Rekursion in der Formel? xy = (x1y1)2 … + x0y0
Also, dass das grüne die rekursiven Aufrufe sind? Anders kann ich die Aufgabe nicht interpretieren.
Und zum anderen. Gibt es vielleicht einen weiteren Tipp, wie man sich für die richtige Größer für lowerBits zu entscheiden hat [für den merge(…) Aufruf in der multimulti…4(…)]?
In dieser Aufgabe sollst du die Multiplikation implementieren - deine Vermutung ist zum Grossteil richtig. Nur die Multiplikationen mit 2er-Potenzen darfst (und sollst) du durch Bitshifts ausdruecken.
Versuch, den entsprechenden main-Test auf dem Papier mal nachzuvollziehen.
Hey Leute,
ich komme bei der multimultimultimulti4() - Methode einfach nicht aufs richtige Ergebnis…
Ich hab mir mal nach jedem Methodenaufruf x0,x1,y0 und y1 ausgeben lassen, verstehe jedoch nicht, warum manche Zahlen negativ sind, obwohl ich den Fall für x<= 0 abgefangen habe.
Ich glaube es hängt mit der Anzahl der übergebenen lowerBits zusammen, weil ich mir nicht sicher bin, wie groß lowerBits bei unterschiedlicher Bitlänge der beiden Zahlen sein muss.
Folgendes wird mir ausgegeben:
x0= -1 x1= 1 y0= 0 y1= 2
42 * 0 = 0, but m3 told us: -11
x0= -2 x1= 2 y0= -2 y1= 2
x0= 0 x1= 1 y0= 0 y1= 1
x0= 2 x1= 5 y0= -1 y1= 2
x0= 0 x1= 1 y0= 0 y1= 1
x0= 1 x1= 1 y0= -2 y1= 0
3 * 4 = 12, but m4 told us: 8
3 * 4 = 12, but m3 told us: -11
10 * 10 = 100, but m4 told us: 64
10 * 10 = 100, but m3 told us: -11
42 * 23 = 966, but m4 told us: 32
42 * 23 = 966, but m3 told us: -11
Test finished. If there are errors in public cases, you should see them above.
This does not imply that your code is correct, please test with further test cases.
You may share them/their results in the FSI forum…
==> WARNING: some conditions are NOT tested by EST (such as the forbidden *) <===
Über einen Tipp würde ich mich freuen 
Was hast du denn für einen Methodenaufruf, dass du x0 = -1 erhälst?
Naja, ich hole mir die x0 mit Hilfe der getLow - Methode.
Dabei übergebe ich eben die Zahl x und die lowerBits.
Ja und mit was rufst du deine Methode getLow(…) auf? Darum gehts mir.
Achso^^
getLow( getBitNum(x) >> 1 , x)
Ehm, und was ist x? 1? 2? 100.000? -1? -200?
Wie soll man dir helfen, wenn man nicht weiß, wo dein Problem liegt. Du hast eine Ausgabe gepostet, der man nicht ansehen kann, welche Werte als Parameter benutzt wurden. Es ist von Vorteil, wenn du dich präziser ausdrückst.
Oh, Tut mir Leid, , das hab ich gar nicht dabei bedacht…
Also nehmen wir mal als Beispiel folgenden Testfall:
multimultimultimulti4( 42,23)
also x = 42 und y = 23
Die Bits der Zahlen hole ich mir mit den bereits implementierten Methoden getLow() und getHigh().
Habe das ganze nun nochmal nur für diesen Fall durchlaufen lassen und bekomme nun folgendes als Ausgabe:
x0= 2 x1= 5 y0= -1 y1= 2
x0= 0 x1= 1 y0= 0 y1= 1
x0= 1 x1= 1 y0= -2 y1= 0
42 * 23 = 966, but m4 told us: 32
42 * 23 = 966, but m3 told us: -11
Test finished. If there are errors in public cases, you should see them above.
This does not imply that your code is correct, please test with further test cases.
You may share them/their results in the FSI forum…
==> WARNING: some conditions are NOT tested by EST (such as the forbidden *) <===
Bei mir schaut die Ausgabe etwas anders aus.
x0 = 2 x1 = 5 y0 = 7 y1 = 2
x0 = 1 x1 = 1 y0 = 3 y1 = 1
966Das y0 = -1 sollte definitiv nicht der Fall sein.
Überleg dir mal schriftlich, wie die Multiplikation laut Formel (siehe Aufgabenblatt) ablaufen muss. Hat mir zumindest geholfen.
Hm… Hab die Multiplikation nochmal komplett auf dem Blatt mit allen Zwischenschritten durchgeführt und weiß glaub ich auch worauf du hinaus willst, hab nur noch keine Ahnung wie ich das in den Code einfügen soll…
Hab ein bisschen dran rumgebastelt und mittlerweile bekomme ich das raus:
x0= 2 x1= 5 y0= 0 y1= 6
x0= 0 x1= 1 y0= 0 y1= 3
x0= 0 x1= 3 y0= 0 y1= 3
x0= 0 x1= 2 y0= 0 y1= 2
x0= 0 x1= 1 y0= 0 y1= 1
42 * 23 = 966, but m4 told us: 1072
42 * 23 = 966, but m3 told us: -11
Test finished. If there are errors in public cases, you should see them above.
This does not imply that your code is correct, please test with further test cases.
You may share them/their results in the FSI forum…
==> WARNING: some conditions are NOT tested by EST (such as the forbidden *) <===
Die y0 = -1, ist zwar immerhin schonmal weg, aber der Rest ist leider noch ziemlich falsch…
Ich gehe mal stark davon aus, dass du deine x und y falsch aufteilst. Anhand der x0 und x1 kann man erahnen, dass die Methode getLow(…) richtig funktionieren zu scheint, aber die Zerlegung von y in y0 und y1 ist falsch.
VIelleicht hilft das als Orientierung.
Ich habe noch ein Problem mit der Argumentenliste in merge().
Ist int lower == (x0y0), int middle == (x1y0 + x0y1) usw?
Wie komme ich auf das Ergebnis merge(3,14,39,10) = 966?
Richtig.
Einfach nur die Formel anwenden:
(x1*y1)*2^(2*lower) + (x1*y0 + x0*y1)*2^lower + x0*y0Btw. gibts hier ne Möglichkeit Formeln richtig darzustellen?
Wenn man jetzt deine Zahlen da einsetzt erhält man:
10 * 2^6 + 39*2^3 + 14 = 966
1 Like
Das Forum selbst bietet kein Latex-Environment, aber mit dieser tollen Seite kann man sich behelfen und den getexten Code direkt hier anzeigen.
1 Like
Erst mal danke! Ich hab noch eine Frage und zwar was machst du nachdem du (x0 = 2 x1 = 5 y0 = 7 y1 = 2) bekommen hast?
Ich kann ja sofort lower, middle, upper-Teile durch private rekursive Funktion für Multiplikation berechnen und dann mit diesen Werten die Methode merge() aufrufen. Danke.
Meine Methode rechnete die Multiplikation bis zum Basisfall herunter, gibt diesen eben ggf. zurück und liefert schlussendlich das Ergebnisse (jedes Teilergebnis auch) mithilfe der merge(…) Methode.
Ich dachte mir zu Beginn auch, ich kann ja die Multiplikation ganz einfach durch eine rekursive Methode mir definieren, aber dann hat die Übungaufgabe ihren Lernzweck verfehlt. Deshalb solltest du darauf achten, deine multmultmultmult4(…) wiederzuverwenden.