engl. restoring division, gebräuchlichste Methode zur Durchführung der Division einer natürlichen Zahl N durch eine natürliche Zahl D.

Bei Realisierung der Methode durch einen logischen Schaltkreis sind N und D in der Regel in binärer Festkommadarstellung gegeben. In einem ersten Schritt wird der Divisor D von rechts so weit mit Nullen aufgefüllt, daß 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 eingefügten Nullen ist. Die Methode geht nun iterativ vor.

Es sei N^(k−i+1) der Partialrest vor dem i-ten Iterationsschritt. Im i-ten Iterationsschritt wird der Wert D′ vom Partialrest N^(k−i+1) abgezogen, R^(k−i+1) bezeichne das Ergebnis dieser Subtraktion. Ist R^(k−i+1) negativ, d. h., war der Wert D′ größer als der Partialrest N^(k−i+1), so wird das entsprechende Quotientenbit Q_k−i+1 auf den Wert 0 gesetzt, und der alte Rest wird wiederhergestellt, indem der Wert D′ auf R^(k−i+1) wieder aufaddiert wird.

War der Wert R^(k−i+1) positiv, so wird das Quotientenbit Q_k−i+1 auf den Wert 1 gesetzt, R^(k−i+1) wird nicht verändert.

Sei \({R}_{neu}^{(k-i+1)}\) der so berechnete neue Partialrest. Bevor zu der nächsten Iteration übergegangen wird, wird der Wert \({R}_{neu}^{(k-i+1)}\) um eine Stelle nach links geshiftet und mit N^(k−i) bezeichnet, d. h., es wird \begin{eqnarray}{N}^{(k-i)}:=2\cdot {R}_{neu}^{(k-i+1)}\end{eqnarray}

gesetzt.

Nach (k + 1) Iterationen ist das Verfahren abgeschlossen, und \({R}_{neu}^{(0)}\), geshiftet um k Stellen nach rechts, gibt den Rest der Division von N und D an.

Erläuterung der Methode am Beispiel von \begin{eqnarray}\begin{array}{ccc}N=00100101(=37) & \text{und} & D=00101(=5)\end{array}\end{eqnarray}

in Zweierkomplement-Darstellung (k ist in diesem Fall gleich 3, D′ = 00101000, −D′ = 11011000 und N⁽³⁾ = 00100101):

Die Division von 00100101 (=37) und 00101 (=5) ergibt somit 00111 (=7). Der Rest der Division ist gegeben durch \({R}_{neu}^{(0)}\), geshiftet um k = 3 Stellen nach rechts, also 00010 (=2).