SRT division

The SRT division is a fast division method used in computer arithmetic. The name comes from its three inventors, who around 1958 described the process almost simultaneously and independently - Dura Sweeney ( IBM ), James Robertson ( University of Illinois ) and Keith Tocher ( Imperial College London ). The method became known to the general public through the Pentium FDIV bug , which led to isolated faulty divisions in the first versions of Intel's Pentium processors. The reason was some incorrect (because missing) entries in the quotient table.

Theoretical foundations

Given are:

Dividend: ${\ displaystyle p \ | p \ in \ mathbb {Z}}$
Divisor: ${\ displaystyle d \ | d \ in \ mathbb {N} \ land d \ geq 1}$
Base: ${\ displaystyle g \ | g \ in \ mathbb {N} \ land g \ geq 2}$
Number list: ${\ displaystyle S_ {g}: = \ {- a, ..., 0, ..., + a \} | a \ in \ mathbb {N} \ land 2 \ cdot a + 1 \ geq g}$

Searched:

That solution for with the smallest r with the same sign as . ${\ displaystyle q: = p \ div d + r}$ ${\ displaystyle p \ cdot d}$

The aim of the SRT division is to present the expression as . ${\ displaystyle q: = p \ div d + r}$ ${\ displaystyle q = \ sum _ {k = -n} ^ {Nn} q_ {k} g ^ {- k} + r \ qquad | q_ {k} \ in S_ {g}}$

Where N is the number of iterations (and therefore the number of digits calculated). n is the number of iterations needed to calculate the digits before the decimal point. For floating point numbers with a normalized mantissa , n is always 0. In processor technology, the SRT division is usually carried out with and for practical reasons . On the one hand, you can calculate two result bits per iteration, on the other hand you can dispense with laboriously multiplying the divisor, since it only consists of powers of 2. ${\ displaystyle g = 4}$ ${\ displaystyle S_ {4} = {- 2, -1,0,1,2}}$ ${\ displaystyle S_ {4}}$

The SRT division can be divided into two components, on the one hand in the actual division algorithm, on the other hand in the digit selection function, which in processor technology is usually implemented with the help of a table. The digit selection function receives z. B. the six highest bits from the intermediate result and the four highest bits from the divisor and returns the next quotient digit as the result . ${\ displaystyle S_ {g}}$

The SRT division in practice

Conventional division method

With the conventional division method, you start with the most significant digits, check how often the divisor is included, note the number as the most significant digit of the result, and subtract the divisor accordingly frequently. For the next step, which calculates the next lower digit of the quotient, the next lower digit of the dividend is added to the intermediate result. The process is repeated until the quotient has been determined with satisfactory accuracy.

Example:

15624829:523=29875 Rest 204
1046            Schritt 1:  1562:523=2, 2*523=1046, 1562-1046=516 ⇒ Quotient: 2????
 ====
 5164
 4707           Schritt 2:  5164:523=9, 9*523=4707, 5164-4707=457 ⇒ Quotient: 29???
 ====
  4578
  4184          Schritt 3:  4578:523=8, 8*523=4184, 4578-4184=394 ⇒ Quotient: 298??
  ====
   3942
   3661         Schritt 4:  3942:523=7, 7*523=3661, 3942-3661=281 ⇒ Quotient: 2987?
   ====
    2819
    2615        Schritt 5:  2819:523=5, 5*523=2615, 2819-2615=204 ⇒ Quotient: 29875
    ====
     204

Disadvantages of this procedure

To decide how often the divisor divides the currently considered part of the number, the entire number must be available. An estimate is not enough. The time required for an addition increases linearly with the number of digits because, in the worst case, transfers in the course of the addition can propagate from the lowest digit to the highest digit (example: 99999999999 + 1), which means that the addition cannot be parallelized. Since computers work with binary numbers, i.e. only have the digits 0 and 1, even "small" numbers consist of many digits. The four numbers used in the example (dividend, divisor, quotient and remainder) e.g. B. are represented in the binary number system as follows: 15624829 ⇒ 111011100110101001111101, 523 ⇒ 1000001011, 29875 ⇒ 111010010110011, 204 ⇒ 11001100. In order to simplify the switching mechanisms, computers usually work with a constant number of bits. If the number 523 is stored in a 64-bit register, then the calculation is made with 64 bits (most of the bits are leading or trailing zeros in the case of floating point numbers ).

Saved-carry addition

To solve the problem with the transfers, the SRT process uses the saved-carry addition (in German: saved transfers). With this addition, the result is calculated, although the carryovers are ignored. These are saved separately and have to be added later to get the correct result.

Example:

  15624829
 +52329875
  ========
  67943694 (Ergebnis ohne Überträge)
 00001101- (Überträge)
  ========
 +67954704 (Korrigiertes Ergebnis)

No correction for incorrectly guessed quotient digits

When dividing with pencil and paper, one has to be smart about guessing what the next digit of the quotient is.

Example:

15624829:523=

Here, based on the first digits, one would "guess" that 523 would fit into 1562 three times. However, if you then complete the step, you can see that the assumption was wrong:

 15624829:523=3
-1569
 ----
   -7

In the corrective division method (see example at the beginning) one would now correct the quotient to 2 and add 523 again (or recalculate):

 15624829:523=2
-1569
 ----
   -7
 +523
 ----
  516

The SRT method is a non-corrective division method, so the principle -7 remains here. In this case, the subtraction has to be carried out with the whole number:

 15624829:523=3
-15690000
 --------
   -65171

Only in the next calculation step is the negative number corrected by assuming the quotient as -1 (i.e. negative, represented here by an overline):

               _
 15624829:523=31
-15690000
 --------
   -65171
  +523000
  -------
   457829

If you continue this procedure ...

               _ _
 15624829:523=31935 Rest 204
-15690000 (-523*10000*+3)
 --------
   -65171
  +523000 (-523* 1000*-1)
  -------
   457829
  -470700 (-523*  100*+9)
  -------
   -12871
   +15690 (-523*   10*-3)
   ------
     2819
    -2615 (-523*    1*+5)
    -----
      204

... so you get z. B. the quotient (negative is bold) 3 1 9 3 5. This result, shown in redundant notation (every number can be shown in many ways) now has to be normalized. 3 1 means nothing other than 30 minus 1, i.e. 29. This is followed by a positive number 9 and a negative 3, i.e. 87 and finally a positive number 5. The quotient is corrected: 29875 (plus the remainder 204), which is the result corresponds to the first example.

Both together

Since we can also choose quotients that are too large for division (since this error can obviously be corrected in the next step), we no longer need to add the entire number including carry-overs, but an approximate value is sufficient, e.g. B. the total without carry-overs; the transfers can then be added in the next step. However, this does not apply without restrictions:

               _ _               +15690000 (die betragsmäßig kleinere Zahl wird von der betragsmäßig
 15624829:523=3195?              -15624829  größeren abgezogen, Vorzeichenkorrektur erst beim Ergebnis)
-15690000 (-523*10000*+3)        ---------
---------                           +76281 (Ergebnis ohne Übertrag, IMMER(!) positiv -
   -76281 (Ergebnis)                        weil ja kein Übertrag berücksichtigt wird)
  +523000 (-523* 1000*-1)           -11110 (Übertragsziffern, IMMER(!) negativ (oder 0))
   +11110 (Übertrag)                ------
  -------                           +65171 (Korrigierte Differenz, hier positiv)
  +568939 (Ergebnis)                       → gleich wie im vorhergehenden Beispiel
  -470700 (-523*  100*+9) ←+
  -111110 (Übertrag)         |
  -------                    +-- Basierend auf der Zahl 568735, müsste der Quotient eigentlich 
   -23981 (Ergebnis)             10 oder sogar 11 sein, da der Quotient aber nur eine Ziffer sein 
   +26150 (-523*   10*-5)        kann (positiv oder nicht), ist hier 9 das Maximum.
   +11110 (Übertrag)
   ------
   +14389 (Ergebnis)
    -???? (-523*    1*+?)
    -1110 (Übertrag)

In the last step, a two-digit number would have to be selected in order to compensate for the -5 that was selected too small in the penultimate step. Even if from now on only positive 9s are used as digits, the correct result can no longer be achieved. It is therefore essential to calculate at least the three most significant digits in full (including carryovers). The three highest digits (which can also be 0) are now completely summed up, the rest as in the previous example with saved-carry addition:

                _ _
 156|24829:523=31936
-156|90000 (-523*10000*+3)
 ===| =====
-000|????? (Teilergebnis mit Übertrag) ← Die beiden höchstwertigen Ziffern vollständig berechnet, 
-???|76281 (Teilergebnis ohne Übertrag) - (das Ergebnis kann nur um 1 vom korrekten Ergebnis abweichen)
-000|76281 (Gesamtergebnis - Teils mit, Teils ohne Übertrag)

 -007|6281 (Gesamtergebnis - Teils mit, Teils ohne Übertrag)
 +052|3000 (-523* 1000*-1)
 +001|1110 (Übertrag aus dem Teilergebnis ohne Übertrag)
  ===|==== [OK]
 +046|???? (Teilergebnis mit Übertrag)
 +???|8939 (Teilergebnis ohne Übertrag)
 +046|8939 (Gemischtes Gesamtergebnis)

  +468|939 (Gemischtes Gesamtergebnis)
  -470|700 (-523*  100*+9)
  -011|110 (Übertrag aus dem Teilergebnis ohne Übertrag)
   ===| ===
  -013|??? (Teilergebnis mit Übertrag)
  -???|181 (Teilergebnis ohne Übertrag)
  -013|981 (Gemischtes Gesamtergebnis)

   -139|81 (Gemischtes Gesamtergebnis)
   +156|90 (-523*   10*-3)
   +011|10 (Übertrag aus dem Teilergebnis ohne Übertrag)
    ===|== [OK]
   +028|?? (Teilergebnis mit Übertrag)
   +???|29 (Teilergebnis ohne Übertrag)
   +028|29 (Gemischtes Gesamtergebnis)

     282|9 (Gemischtes Gesamtergebnis)
    -313|8 (-523*    1*+6)
    -001|0 (Übertrag aus dem Teilergebnis ohne Übertrag)
     ===|=
    -032|? (Teilergebnis mit Übertrag)
    -???|9 (Teilergebnis ohne Übertrag)
    -032|9 (Gemischtes Gesamtergebnis)

     -329| (Gemischtes Gesamtergebnis)
     +000| (es folgt keine Quotientenziffer mehr)
     +010| (Übertrag aus dem Teilergebnis ohne Übertrag)
      ===|
     -319| (Divisionsrest) ← Diese letzte Addition wird vollständig mit allen 
                                Übertragsbits durchgeführt.

The result here is the number 3 1 9 3 6 with the remainder -319, in addition to the quotient, which is one too large here, the negative remainder must now also be normalized. The remainder is corrected by adding the divisor (then results in 204, as in the examples above), the quotient is then again 3 1 9 3 5, or also normalized 29875.

Similar procedures

Individual evidence

↑ John Cocke , Dura W. Sweeney: High speed arithmetic in a parallel device. Technical Report IBM, February 1957.
↑ James E. Robertson: A new class of digital division methods. IEEE Trans. Electronic Computers, 7 (1958), pp. 218-222.
↑ Keith D. Tocher: Techniques of multiplication and division for automatic binary computers. Quart. J. Mech. Appl. Math. 11 (1958), pp. 364-384.

Web links

uni-oldenburg.de: SRT-Division , Wiland Schmale, retired professor of mathematics at the Carl von Ossietzky University of Oldenburg, supplement to a hands-on lecture on the SRT division (pdf; 284 kB)
tu-muenchen.de: SOFTWARE - DISASTER AND HOW TO PREVENT IT , introductory seminar on the Pentium bug, December 11, 2002, (pdf; 421 kB)

[1] John Cocke , Dura W. Sweeney: High speed arithmetic in a parallel device. Technical Report IBM, February 1957.

[2] James E. Robertson: A new class of digital division methods. IEEE Trans. Electronic Computers, 7 (1958), pp. 218-222.

[3] Keith D. Tocher: Techniques of multiplication and division for automatic binary computers. Quart. J. Mech. Appl. Math. 11 (1958), pp. 364-384.