Direkt zum Inhalt

Lexikon der Mathematik: nichtwiederherstellende Division

(engl. nonrestoring division), Methode zur Division einer natürlichen Zahl N durch eine natürliche Zahl D, beide in der Regel in binärer Festkommadarstellung gegeben.

In einem ersten Schritt wird der Divisor D so weit von rechts mit Nullen aufgefüllt, bis die Stelligkeit der höchstwertigen Stelle von D der Stelligkeit der höchstwertigen Stelle von N entspricht. Die so entstandene Zahl wird mit D′ bezeichnet. Der anfängliche Partialrest N(k) ist durch N gegeben, wobei k die Anzahl der rechts neu eingefügten Nullen ist. Die Methode geht nun iterativ vor. Sei N(k−i+1) der Partialrest vor dem i-ten Iterationsschritt. Ist N(k−i+1) ≥ 0, so wird im i-ten Iterationsschritt der Wert D′ vom Partialrest N(k−t+1) abgezogen und die Quotientenstelle Qki+1 auf 1 gesetzt. Ist N(k−i+1) < 0, so wird D′ auf den Partialrest N(k−t+1) aufaddiert und die Quotientenstelle Qki+1 auf −1 gesetzt.

Bevor zur nächsten Iteration übergegangen wird, wird der so abgeänderte Partialrest R(k−t+1) um eine Stelle nach links geshiftet und mit N(k−i) bezeichnet, d. h. \begin{eqnarray}{N}^{(k-i)}:=2\cdot {R}^{(k-i+1)}\end{eqnarray} gesetzt. Nach k + 1 Iterationen ist das Verfahren abgeschlossen. R(0), geshiftet um k Stellen nach rechts, gibt den Rest der Division von N und D an. Der Quotient der Division ergibt sich aus \begin{eqnarray}\mathop{\sum ^{k}}\limits_{i=0}{Q}_{i}\cdot {2}^{i}.\end{eqnarray}

Eine Erläuterung der Methode am Beispiel von N = 00100101 und D = 00101 in Zweier-Komplement-Darstellung (k ist in diesem Fall gleich 3, D′ = 00101000, −D′ = 11011000 und N(3) = 00100101):

Abbildung 1 zum Lexikonartikel nichtwiederherstellende Division
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Der Quotient von 00100101 (=37) und 00101 (=5) ist somit \begin{eqnarray}\mathop{\sum ^{3}}\limits_{i=0}{Q}_{i}\cdot {2}^{i}={2}^{3}-{2}^{2}+{2}^{1}+{2}^{0}=7,\end{eqnarray}

der Rest der Division ist gegeben durch R(0), geshiftet um k = 3 Stellen nach rechts, also 0010 (=2).

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos