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.
Divisionsverfahren: Overflows beim 2er-Komplement ignorieren?
In der Klausur vom 05. April 2013 sollte man a / b mittels des Non-Performing-Verfahrens berechnen.
a = 0 1001 0110 (= 150)
b = 01 0101 (= 21)
Die erste Frage ist schon, welche Wortbreite L ich nehmen soll.
Wenn ich L=5 wähle (da b nur 5 Bits effektiv beinhaltet und a in 2*L=10 Bits passt), dann ist die Hilfsgröße B’ = 2^(L) * B = 10101 00000.
In jedem Divisionsverfahren muss ich B’ mehrmals abziehen.
Hierzu bilde ich wie in der Übung das 2er-Komplement. Das ist hier aber nicht möglich, da das vorderste Bit von B’ schon 1 ist. Das heißt B’ ist bereits außerhalb des Wertebereichs.
Nehmen wir also L=6 Bit Wortbreite. Dann ist B’ = 010101 000000 = 0101 0100 0000.
-B’ ist im 2er-Komplement 1010 1100 0000.
Den anfänglichen Partialrest a ergänze ich um 3 führende Nullen auf 12 Bits.
Fragen
-
Bei der Durchführung wird der Partialrest an einer Stelle nach links geshiftet, sodass er im 2er-Komplement eine negative Zahl darstellt (“OVERFLOW?” im Code unten).
Außerdem treten noch mehrere Overflows bei der Subtraktion von B’ auf.
Jedoch scheint das Endergebnis korrekt zu sein (150 / 21 = 7 Rest 3). Kann man also Overflows getrost ignorieren? -
Die ganze Rechnung habe ich statt 2er-Komplement auch einmal mit handschriftlicher Subtraktion durchgeführt, d. h. mit Borrows. Da kommt exakt dasselbe heraus, selbst die Differenzen von “2*Partialrest minus B’” sind dieselben. Ist die handschriftliche Subtraktion also dasselbe wie die Berechnung mittels 2er-Komplement?
-
In der Übung musste man “A = 0111101 durch B = 0110” mittels Non-Restoring teilen.
[quote]A < 2^(n) * B.
Hier ist dies ab n = 4 der Fall, also legen wir die Wortbreite auf 4 Bit fest. In der Regel hat B einfache (hier also 4) und A doppelte Wortbreite (8), weshalb wir mit Nullen ergänzen (aber darauf achten, dass inbesondere der Partialrest auch negativ sein kann – in dieser Aufgabe reichen 8 Bit trotzdem, weil A nur 6 Bits nutzt und somit stets R_i <=2 * A < 2^(2n-1)).[/quote]
Wie kommt man auf die letzte Ungleichung? Wie man in der Aufgabe zuvor (und im Code unten) sieht, kann A durchaus solange nach links geshiftet worden sein, dass es >= 2^(2*6 - 1), also >= 2^11 sein kann, das heißt im 2er-Komplement mit 12 Bits als negativ betrachtet werden würde.
Vielen Dank an alle, die es bis hier hin durchgelesen haben 
Ich bin für jeden Hinweis sehr dankbar!
a / b mittels Non-Performing
a = 0 1001 0110 (= 150)
b = 01 0101 (= 21)
[code]
0000 1001 0110 - - - - - -
0001 0010 110- - - - - - - << 1: Shift nach links
1010 1100 0000 - - - - - - Minus B’
1011 1110 110- - - - - - 0 < 0
0001 0010 110- - - - - - 0 Kopiere alten Partialrest * 2 (also geshiftet)
0010 0101 10-- - - - - 0 - << 1: Shift nach links
1010 1100 0000 - - - - 0 - Minus B’
1101 0001 10-- - - - - 0 0 < 0
0010 0101 10-- - - - - 0 0 Kopiere alten Partialrest * 2 (also geshiftet)
0100 1011 0— - - - 0 0 - << 1: Shift nach links
1010 1100 0000 - - - 0 0 - Minus B’
1111 0111 0— - - - 0 0 0 < 0
0100 1011 0— - - - 0 0 0 Kopiere alten Partialrest * 2 (also geshiftet)
1001 0110 ---- - - 0 0 0 - << 1: Shift nach links (OVERFLOW?)
1010 1100 0000 - - 0 0 0 - Minus B’
0100 0010 ---- - - 0 0 0 1 > 0 (Overflow im 2er-Kpl., Carry-Out != Carry-In)
1000 010- ---- - 0 0 0 1 - << 1: Shift nach links
1010 1100 0000 - 0 0 0 1 - Minus B’
0011 000- ---- - 0 0 0 1 1 > 0 (Overflow im 2er-Kpl., Carry-Out != Carry-In)
0110 00-- ---- 0 0 0 1 1 - << 1: Shift nach links
1010 1100 0000 0 0 0 1 1 - Minus B’
0000 11-- ---- 0 0 0 1 1 1 > 0
Quotient = 0111 (im Zweierkomplement)
Rest: 11 = 011 (im Zweierkomplement)[/code]
Zu 1:
Nicht ganz richtig.
Das ist wie in der normalen Divison auch. Du schaust nach, “wie oft” die Zahl reinpasst, und gehst dann zur nächsten Stelle, wenn sie nicht reinpasst.
Hier machst du Analog etwas Ähnliches: Du subtrahierst zwei Zahlen. Ist das Ergebnis negativ, kommt rechts hinter dem Gleichheitszeichen eine 0 hin, ist es positiv eine 1. Wenn negativ: Du addierst dann wieder den Divisor und gehst an die nächste Stelle und schaust, ob es reinpasst. Das “schauen ob es wie oft reinpasst” wird hier durch das negative Ergebnis signalisiert. Denn du hast eigtl nur zwei Zustände: Zahl größer bzw. gleich oder Zahl kleiner. Du hast nie den Fall, dass die Zahl mehrfach reinpasst wie das bei der dezimalen Division ja durchaus passieren kann.
Zu 2:
Eigtl machst du damit nix Anderes als dass du die Subtraktion umschreibst als z.B. 2-5 = 2+(-5). Bei einer schriftl. Subtraktion machst du analog dazu fast dasselbe. Du schaust dir die Differenz an, schreibst sie drunter, nimmst dann ein negatives Vorzeichen, fertig. Der Computer bildet dann dafür das Zweierkomplement und addiert.
Danke für die Antwort!
Zu 1:
Ich verstehe nicht ganz, wo da der Zusammenhang zu den Overflows in deiner Antwort steckt.
Zu 2:
Ist das Ergebnis nur fast dasselbe oder genau dasselbe?
Der Zusammenhang ist ganz simpel:
Ist die Zahl, von der du subtrahierst, kleiner, dann kommt logischerweise immer etwas Negatives. In dem Fall addierst du einfach wieder die abzuziehende Zahl, stellst rechts vom Gleichheitszeichen eine 0 hin und gehst zur nächsten Stelle weiter.
Ich schreib dir deine Rechnung mal mit Kommentar hin:
10010110 / 10101 = 0111
-10101 // 10101 passt kein mal rein, da 10010 kleiner ist als 10101. Erste Ziffer: 0. Addiere 10101, fahre mit nächster Stelle fort. (= nimm die 1 herunter.)
---------- // Schritt 2: Setze Zahl zurück, nimm die nächste Stelle mit rein:
100101
- 10101// Zahl größer. Zweite Ziffer: 1. Subtrahiere beide voneinander.
100001 //(= nimm die nächste Ziffer runter)
- 10101 // Zahl größer. Dritte Ziffer: 1. Subtrahiere…
11000
- 10101 // Zahl größer. Letzte Ziffer: 1 Subtrahiere…Rest: 11.
Zur 2: Wenn du etwa 244-356 nimmst, dann hast du Folgendes:
244 = 1111 0100
356 = 1 0110 0100
Von 0 bis 0 sind 0.
Von 0 bis 0 sind 0.
Von 1 bis 1 sind 0.
Von 0 bis 0 sind 0.
Von 0 bis 1 sind 1.
Von 1 bis 1 sind 0.
Von 1 bis 1 sind 0.
Von 0 bis 1 sind 1.
Dann noch die letzte 1 sehen als Vorzeichen (= Zahl 2 ist größer als Zahl 1.)
=(Von unten nach oben) 1 1001 0000
= -112.
Nehmen wir das Ganze mal mit Zweierkomplementdarstellung vor:
11110100
+010011100
1 1001 0000
Das Zweierkomplement hat den großen technischen Vorteil, das der Computer keine Vorzeichen kennen muss sondern es eine reine Operation auf Basis von Zeichenmanipulation ist. Im Endeffekt wird hier das Prinzip der
schriftlichen Subtraktion ausgenutzt.
Danke für deine Beispiele, aber ich vermute, wir reden aneinander vorbei.
Dein Divisionsbeispiel nutzt das erste in der VL vorgestellte Verfahren, das Schulverfahren. Da tritt mein Problem nicht auf.
In welchem Zahlenformat sind denn überhaupt die ganzen Zahlen in den Registern gespeichert, vorzeichenlos oder Zweierkomplement?
Wenn ich vom 2er-Komplement ausgehe, und zum Beispiel das Non-Performing-Verfahren nutze, dann shifte ich den Partialrest nach links (anstatt den Divisor/Nenner nach rechts). Dabei kann es vorkommen, dass durch das Shiften (also *2) das vorderste Bit des Partialrestes gesetzt wird. Plötzlich wird also die Zahl im Sinne des 2er-Komplements negativ! Kann das stimmen? Siehe mein Divisionsbeispiel im ersten Beitrag, dort wo “OVERFLOW?” steht.
Bei deinem 2. Beispiel: Es ist also kein Zufall, dass bei der handschriftlichen Subtraktion “1 1001 0000” und bei Nutzung des 2er-Komplements auch "1 1001 0000
" herauskommt, also das insbesondere das Zielformat der schriftlichen Subtraktion automatisch 2er-Komplement ist?
Zu 1: Stimmt. Hab das wohl verwechselt, macht aber nix, da du fast dasselbe machst in dem Fall.
In dem Fall schreibst du eine 0 in die rechte Spalte, addierst den Divisor wieder drauf und shiftest dann 1 Bit nach links und wiederholst die Operation. Also fast das Gleiche wie bei mir.
Hier ist das auf Folie 9 noch mal ausführlich erklärt:
http://users.minet.uni-jena.de/~nez/rechnerarithmetik_5/folien/Rechnerarithmetik.2008.17.handout.pdf
Zu 2:
Nein, natürlich ist es kein Zufall, weil die dahinter liegende Rechenoperation immer gleich ist.
Du könntest ja auch auf den Gedanken kommen, das mal umzuschreiben:
-356+244 ist nichts anderes als 356 modulo 244 mit einem daraufhin negativ angehängten Vorzeichen.
-356+244 = -356+243+1 = 243-356+1 = -113+1 = -112
Genau DAS wird bei der Subtraktion mit Zweierkomplement automatisch so durchgeführt.
Wenn du es mir nicht glauben solltest(^^):
https://en.wikipedia.org/wiki/Two's_complement#Why_it_works
Und übrigens noch eine interessante Anmerkung dazu: Dasselbe wird auch so etwa bei der Borrow-Semantik ausgenutzt:
Zu 1: Nichts für ungut, aber ich weiß immer noch, wie das Divisionsverfahren geht 
Das wusste ich schon seit Beitrag 1. Es geht nur darum, was passiert, wenn durch’s Shiften die Zahl ins Negative im Sinne des 2er-Komplements rutscht.
Zu 2: Ok, ich fand das nämlich nicht unbedingt naheliegend, dass die gleiche Repräsentation für negative Zahlen vorliegt. Zum Beispiel gibt es auch das Einerkomplement, was dann mit der schriftlichen Subtraktion nicht übereinstimmen kann.
Vielen Dank!