Restoring Division

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.

Restoring Division
Hallo,

haette da mal eine Frage zum allgemeinen Vorgehen bei der restoring division, vielleicht kann mir ja jemand helfen:

Angenommen ich habe 2 Zahlen

a = 0100 1001 0011

und

b = 0000 0010 1001

Jetzt ziehe ich ja von a a_geshiftet ab:

_0100 1001 0011
0100 1001 0011_
==========
$Zwischenergebnis

Jetzt frage ich mich:

1.) in diesem Fall hab ich ja einen Uebertrag. Was passiert damit?
2.) Wann hoert die Division eigentlich auf? Der eigentliche Divisor b kommt hier ja gar nicht vor?

Schon mal vielen Dank fuer jeden Hinweis :wink:


Hi,

sieh Dir bitte nochmal die Folien zur Division (Rechnerarithmetik) genau an. Die Division beginnt ab Folie 48. Bei der Restoring Division setzt man a als den Rest und zieht davon b schrittweise ab. Die genaue Vorgehensweise steht auf Folie 53 und auf der folgenden Folie 54 ist noch ein Beispiel. Das Beipiel zeigt a in der ersten Zeile und ax2 in der folgenden Zeile. b, das von a abgezogen wird, steht klein gedruckt unter a.

Zu Deinen Fragen:

  1. Ein Ueberlauf zeigt ein negatives Ergebnis an. Dies hat je nach Divisionsverfahren Auswirkungen auf den naechsten Schritt. Bei der Restoring Division wird der Divisor ohne Schieben des Dividenden wieder hinzuaddiert um den Ausgangswert zu erhalten.
  2. Die Division endet nach einer festen Anzahl von l Schritten, wobei l die halbe Bitlaenge des Dividenen ist. Die Non-Restoring Division bildet eine Ausnahme, da hier u. U. ein l+1ter Schritt notwendig ist um einen negativen Rest zu korrigieren.

vielen Dank fuer die Antwort.

Die Folien habe ich schon gefuehlte hundert mal angeschaut, durch deinen Hinweis bin ich jetzt allerdings drauf gekommen.
Es sah fuer mich so aus, als ob A_shift von A abgezogen wird, weil das B kleiner geschrieben ist und ich es daher als Uebertrag fehlinterpretiert habe :wink:

Vielen Dank auf jeden Fall :smiley:


Ich empfehle hier auch statt B abzuziehen, als Komplement hinzu zu addieren, finde ich um einiges einfacher. Man muss halt nur vorher das Komplement von B bilden und man darf nicht die führenden 1en vergessen beim hinzu addieren.
Hoffe das hilft dir vielleicht auch, weil ich so meine Probleme mit binärem subtrahieren habe/hatte :smiley:


ok, danke fuer den Tipp.

Moechte das Bsp trotzdem mal “normal” berechnen, nur um’s mal gemacht zu haben :wink:

Jetzt frage ich mich gerade wo das zu subtrahierende stehen muss (also an welcher Stelle?).

0100 1001 0011
0100 1001 0011
shift nach links
0000 0010 1001 subtrahieren

$Zwischenergebnis

Wie muss ich den Subtrahend positionieren?

Vielen Dank!


Wie machst du es denn beim dezimalen dividieren? (Selbes beim binären)


naja, wenn der Divisor groesser ist, muss ich shiften / haenge ne 0 hinten dran, ansonsten schreib ich’s direkt unter den Dividend.

d.h. in meinem Bsp ist der erste Shift eigentlich unnoetig…und die ganzen Nullen von b kann ich auch weglassen, zumindest bis auf eine vorne, richtig?

sprich, ich erhalte sowas:

0100 1001 0011
010 1001

$Zwischenergebnis

stimmt das soweit?


Jetzt schreibst du noch den Shift wieder dazu (denn der ist nicht unnötig) und subtrahierst B von A_geshiftet. Position von B stimmt.
Das Shiften lässt dich nämlich erkennen ob du fertig bist, oder weiter rechnest.

Am Ende wirds nämlich so aussehen (andres Bsp. nämlich das aus der Vorlesung der letzte Schritt):

0010000----
010000----- links shift
01111 Subtrahend


00001----- pos. Ergebnis

Jetzt kannst du nicht mehr shiften, und die Division ist fertig.


Die Folien helfen da weiter. Am Anfang der Divsion werden einige „Grundregeln“ zur Formatierung des Dividenden und des Divisors genannt, so z.B., dass der Dividend die doppelte Laenge des Divisors haben muss. In Abhaengigkeit dieser Formatierung geben die Algorithmen jeweils an wie vor dem ersten Schritt der Divisor im Verhaeltnis zum Dividenden zu platzieren ist.


Hallo,
ich hätte zum vorgehen bei der division auch eine Frage.
Wenn ich zb. 113 durch 8 dividiere komm ich ja auf einen Quotienten von 14 und einen Partialrest von 1. Das ganze mit 4 Schritten und am schluss eventuell mit einem korrekturschritt.
Aber wenn ich jetzt 113 durch 7 rechnen will kommt ja nach 4 Schritten ein Quotient von 15 mit einem partialrest von 8 raus. Dann dacht ich mir , dass man einen fünften Schritt machen muss weil 16 ja mit 4 bits nicht darstellbar ist. Aber dann kommt nur kompletter blödsinn raus.
Könnte mir da mal jemand erklären was ich falsch mache?

Beste grüße


Hat sich erledigt.
Hab die Bedingung: A < (2^l) * B übersehn.


Eigentlich dachte ich ich hätte es verstanden aber mit dem Versuch 7/3 zu teilen scheitert es grade… ich rechne mal vor, denn ich sehe den Fehler nicht…
0111| - -
0111- |- - (SL)
- 011
0100- |- 1
100 - -|1 - (SL)
- 011
???

eigentlich sollte doch 2R1 rauskommen aber tut es bei mir irgendwie nicht. Kann bitte jemand meine Denkblockade auflösen?

EDIT: habe gerade das problem gesehen :smiley: die 011 passt in die 111 gleich 2mal rein nicht nur einmal… wie umgeht man das fachlich? einfach eins weiter links anfangen oder nochmal subtrahieren ohne zu shiften?


Du shiftest den Divisor nicht weit genug nach links. 011 ist drei Stellen lang, also musst du ihn um drei Stellen nach links shiften.


Alles klar, Danke :slight_smile:


Ich habe auch versucht, 7:3 mit Restoring Division zu dividieren, Unterstriche sollen dabei Leertasten sein.

__0111|--
_0111-|-- // Shift
-11---|-- // Subtraktion
_1011-|-0 // negativer Rest: 0 kommt dran
+11---|-0 // Addition
_0111-|-0
_111--|0- // Shift
-11---|0- // Subtraktion
_001--|01 // positiver Rest: 1 kommt dran
_01---|1- // Shift
-11---|1- // Subtraktion
_10---|10 // negativer Rest: 0 kommt dran
+11---|10 // Addition
_01---|10

Passt die Rechnung so (besonders, ob ich an dieser Stelle die Rechnung schon abbrechen soll) oder fehlen hier noch einige Schritte?


Ich kenne mich bei der Division nicht so aus, aber warum machst du füllst Du nicht einfach mit Nullen auf, anstatt Leertasten zu machen ?