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.
Wortbreite Non-Restoring-Division
Hallo zusammen,
für die Wortbreite n bei der Non-Restoring-Division muss ja gelten:
A < 2^n * B
Was ist nun aber, wenn die Länge von B = 6 bit und die Länge von A = 8 bit ist (beide mit Vorzeichenbit versehen für 2K). Eigentlich würd die Gleichung ab n = 3 passen. Ich kann aber A nicht in 3 bit packen. Wähle ich dann die Länge von B als Mindestlänge? Und wird dann A = 12 bit oder bleibt es bei 8 bit? In der Vorlesung und den Übungsaufgaben gabs ja leider immer nur optimale Bsp mit 4 bzw. 8 bit…
Vielen Dank bereits!
Hi!
Genau, wie du schon richtig schreibst, hast du folgende Einschränkungen:
- n >= 3, damit A < 2^n * B erfüllt ist
- n >= 4 = ceil(|A|/2), damit A noch in die doppelt-große Breite passt
- n >= 6 = |B|
Also wählst du n = max(3, 4, 6) = 6. Damit erhälst du für B sowie für den Quotienten eine Breite von 6 Bit, für A eine Breite von 2 * 6 = 12 Bit.
Du musst A nicht zwingend doppelt-groß wählen; wenn du dies nicht tust, beachte, dass dadurch Formeln der VL u. U. nicht mehr gelten.
Zum Beispiel müsstest du statt B’ = 2^n * B Folgendes tun: Wähle B’ so, dass es links mit dem 1. Bit von A beginnt, in Formeln: B’ = 2^(|A|-n) * B.
Auch das Auslesen des finalen Restes ist anders: R = 2^(-(|A|-n)) * R^(n+1) = R^(n+1) >> (|A|-n), also Rechtsshift um |A|-n, was im Falle |A|=2n eben den Formeln der VL gleicht.
Ein weiteres Beispiel mit einer genauren Anleitung findest du auf meiner Website 
Das stimmt, jedoch werden hoffentlich in der Klausur auch nicht völlig abstruse Bitlängen drankommen 
In der Realität hast du sowieso immer feste Breiten, die sind durch die in HW gegossenen Register vorbestimmt.
1 „Gefällt mir“
Ganz herzlichen Dank, die max(x,y,z)-Sichtweise hilft mir optimal weiter!
Und deine HP gucke ich mir gerne mal an.
Mein obiger Post ist im bestimmten Randfällen fehlerhaft!
Außerdem wurde ich darauf aufmerksam gemacht, dass in einer Altklausur nach “der minimalen Anzahl an Divisionsschritten/Quotientenbits” sowie der Durchführung der Division gefragt wurde.
So ist es richtig:
Man erweitert also am besten doch nicht auf doppelte Wortbreiten, sondern geht wie folgt vor:
Man wählt das kleinste n so, dass A < 2^n * B erfüllt ist. A und B lässt du bestehen, bis auf ggf. Hinzufügen eines VZ-Bits (falls sie bereits mit einer 1 beginnen).
B’ = 2^n * B.
Auslesen des finalen Restes: R = R^n * 2^(-n), also streiche die unteren n Bits.
[quote=Marcel[Inf]]Wähle B’ so, dass es links mit dem 1. Bit von A beginnt, in Formeln: B’ = 2^(|A|-n) * B.
Auch das Auslesen des finalen Restes ist anders: R = 2^(-(|A|-n)) * R^(n+1) = R^(n+1) >> (|A|-n), also Rechtsshift um |A|-n[/quote]
Die Formeln versagten zum Beispiel in dem pathologischen Randfall: 8 : 2 = 4.
- 1000 : 10.
- Das kleinste n, für das A < 2^n * B erfüllt ist, ist n = 3.
- Erweitere um VZ-Bits: A_neu = 0 1000, B_neu = 010.
- Würde man nun 010 so lange nach links schieben, bis es mit dem 1. Bit von A beginnt (also 0 1000, was A_neu gleicht), führt die Division auf 8 : 2 = 7 Rest 1, was offensichtlich fehlerhaft ist.
Im Gegensatz funktioniert jedoch die Rechnung, wenn man B * 2^n = 01 0000 ausrechnet und nun das erste Bit wegschneidet, damit es nicht länger als A_neu ist: B’ = 1 0000, -B’ = 1 0000 (=B’ hier).
Dieses Wegschneiden des ersten Bits und auch der Overflow von -B’ erscheinen mir selbst etwas schleierhaft, aber es funktioniert zumindest <_<.
Habe eine ganz andere Idee, sei eine Zahl mit führender 1 und Länge 7 gegeben und eine andere Zahl mit führender 1 und Laenge, sagen wir Mal 5. Erweitere beide Zahlen um eine führende Null. Betrachte nun den “oberen Rand” und den “rechten Rand” des Array Dividierer auf Seite 83 im Skript.
7 6 5 4 3 2 1 0
0…
5 4 3 2 1 0
0…
So ein Felddividierer hätte also 3 Zeilen, die 3 Zeilen entsprechen der Länge des Wortes.Kann man sich auch ganz einfach überlegen, warum das so ist, Linksshift entspricht ja einfach einem *2, n Mal Linksshift einem 2^n, wie oft passt B in A?