srt-division – Wikipedia

The SRT-Division is a fast division process that is used in computer arithmetic. The name comes from her three inventors, which described the procedure almost simultaneously and independently around 1958 – Dura Sweeney (IBM) ^[first] , James Robertson (University of Illinois) ^[2] and Keith Docher (Imperial College London) ^[3] . The procedure became known to the general public by the Pentium FDIV bug, which in the first versions of Intel’s Pentium processors led to a few faulty divisions. The reason was some false (because missing) entries in the quotient table.

Are given:

• Dividend:
  ${Displaystyle P | Mathbb {z}}}}}$

  

• Divisor:
  ${DisplayStyle D | Din Mathbb {n} Land dgeq 1}$

  

• Basis:
  ${DisplayStyle G | Gin Mathbb {n} Land Ggeq 2}$

  

• Digit list:
  ${displaystyle S_{g}:={-a,…,0,…,+a}|ain mathbb {N} land 2cdot a+1geq g}$

  

Sought:

• That solution for
  ${displaystyle q:=pdiv d+r}$

  With the amount of the smallest R with the same omen as

  ${DisplayStyle Pcdot D}$

  .

The aim of the SRT division is to express the expression

${displaystyle q:=pdiv d+r}$

To present as

${displaystyle q=sum _{k=-n}^{N-n}q_{k}g^{-k}+rqquad |q_{k}in S_{g}}$

.

N is the number of iterations (and thus the number of counters calculated). n is the number of iterations required for calculating the digits before the decimal point. In the case of sliding comma numbers with normalized mantises, n is always 0. In processor technology, the SRT division is usually used for practical reasons

${displaystyle g=4}$

and

${displaystyle S_{4}={-2,-1,0,1,2}}$

carried out. On the one hand, you can calculate two result bits per iteration, on the other hand, can do without multiplying the divisor, there

${displaystyle S_{4}}$

only consists of potencies in 2.

The SRT division can be divided into two components, on the one hand in the actual division salgorithm, and on the other hand into the number selection function, which is usually implemented in the processor technology using a table. The number selection function is available. B. the six highest bits from the intermediate result and the four highest bits from the divisor and the result is the next quotient number

${displaystyle S_{g}}$

return.

Conventional division procedure [ Edit | Edit the source text ]

With the conventional division process, you start with the highest -quality areas, checks how often the divisor is included, notes the number as the highest -quality number of the result, subtracts the divisor frequently. For the next step, which calculates the next lower digit of the quotient, the next lower number of the dividend is added to the intermediate result. The process is repeated until the quotient was determined with satisfactory accuracy.

Example:

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

Disadvantages of this procedure [ Edit | Edit the source text ]

The entire number must be available for the decision as to how often the divisor shares the currently considered part of the number. An estimate is not enough. The time required for an addition increases linearly with the number of digits, because transfers in the course of the addition in the worst case can be reproduced from the lowest digit to the highest quality (example: 999999999+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 used numbers (dividend, divisor, quotient and rest) are shown in the binary number system, for example: 15624829 ⇒ 1110110011011111101, 523 ⇒ 1000001011, 29875 ⇒ Usually with a constant number of bits. If the number 523 is stored in a 64-bit register, then 64 bits are also expected (most bits of which are leading or final zeros).

Saved-Carry-Addition [ Edit | Edit the source text ]

In order to solve the problem with the transfers, the SRT procedure uses the Saved Carry Addition (in German: stored transfers). With this addition, the result is calculated, although the transfers are ignored. These are saved separately and must be added later to get the correct result.

Example:

15624829
 +52329875
  ========
  67943694 (result without transfers)
 00001101- (transfers)
  ========
 +67954704 (corrected result) 

No correction for incorrect quotient digits [ Edit | Edit the source text ]

If you carry out a division using paper and pencil, you have to intelligently guess what the next number of the quotient is.

Example:

15624829: 523 = 

Based on the first digits, one would “advise” that 523 fit three times in 1562. However, if you come to an end, you can see that the assumption was wrong:

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

In the corrective division procedure (see example at the beginning), the quotient would now be correct to 2 and add 523 again (or calculate new):

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

The SRT procedure is a non-corrected division process, so there remains in principle -7. In this case you have to do the subtraction with the whole Perform number:

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

The negative number is only corrected in the next computing step by assuming the quotient as -1 (i.e. negative, shown here by a rag):

_
 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 fat) 3 first 9 3 5. This result, shown in a redundant spelling (each number can be displayed in many ways) must now be normalized. 3 first means nothing more than 30 minus 1, i.e. 29. A positive number 9 and a negative 3, 87 and finally a positive number 5, are the quotient corrected: 29875 (plus the rest 204), which the result from the first Example corresponds.

Both together [ Edit | Edit the source text ]

Since we can also choose too large quotients in the division (since this error can apparently be corrected again in the next step), we no longer need to add the entire number including transfers to the addition, but it is sufficient. B. the sum without transfers; The transfers can then be added in the next step. However, this does not apply without restrictions:

_ _ +15690000 (the smaller number is from the amount
 15624829: 523 = 3195? -15624829 larger ones, sign correction only in the result)
-15690000 (-523*10000*+3) ---------
--------- +76281 (result without transmission, always (!) Positive-
   -76281 (result) because no transfer is taken into account)
  +523000 (-523* 1000* -1) -11110 (transmission figure, always (!) Negative (or 0))
   +11110 (transfer) -------
  ------- +65171 (corrected difference, positive here)
  +568939 (result) → the same as in the previous example
  -470700 (-523* 100*+9) ←+
  -111110 (transfer) |
  ------- +-based on the number 568735, the quotient should actually
   -23981 (result) 10 or even 11, since the quotient is only a digit
   +26150 (-523* 10* -5) can (positive or not), 9 is the maximum here.
   +11110 (transfer)
   -------
   +14389 (result)
    -???? (-523* 1*+?)
    -1110 (transfer) 

In the last step, a double -digit number would have to be chosen to compensate for the -5 chosen too small in the penultimate step. Even if only positive 9s are used as digits from now on, the correct result can no longer be achieved. It is therefore essential to fully calculate at least the three highest quality digits (i.e. including transfers). Here the three highest digits (which can also be 0) are completely added up, the rest as in the previous example with Saved Carry Addition:

_ _
 156 | 24829: 523 = 31936
-156 | 90000 (-523*10000*+3)
 === | =====
-000 | ????? (Partial result with transmission) ← The two highest quality digits fully calculated,
- ??? | 76281 (partial result without transmission) - (the result can only deviate by 1 from the correct result)
-000 | 76281 (overall result - partly with, partly without transmission)

 -007 | 6281 (overall result - partly with, partly without transmission)
 +052 | 3000 (-523* 1000* -1)
 +001 | 1110 (transfer from the partial result without transmission)
  === | ==== [ok]
 +046 | ???? (Partial result with transmission)
 +??? | 8939 (partial result without transmission)
 +046 | 8939 (mixed overall result)

  +468 | 939 (mixed overall result)
  -470 | 700 (-523* 100*+9)
  -011 | 110 (transfer from the partial result without transmission)
   === | ===
  -013 | ??? (Partial result with transmission)
  -??? | 181 (partial result without transmission)
  -013 | 981 (mixed overall result)

   -139 | 81 (mixed overall result)
   +156 | 90 (-523* 10* -3)
   +011 | 10 (transfer from the partial result without transmission)
    === | == [ok]
   +028 | ?? (Partial result with transmission)
   +??? | 29 (partial result without transmission)
   +028 | 29 (mixed overall result)

     282 | 9 (mixed overall result)
    -313 | 8 (-523* 1*+6)
    -001 | 0 (transfer from the partial result without transmission)
     === | =
    -032 |? (Partial result with transmission)
    -??? | 9 (partial result without transmission)
    -032 | 9 (mixed overall result)

     -329 | (Mixed overall result)
     +000 | (No more quotient digits follow)
     +010 | (Transfer from the partial result without transmission)
      === |
     -319 | (Division residue) ← This last addition will be completely with everyone
                                Transfer bits carried out. 

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

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), S. 218–222.
3. ↑ Keith D. Tocer: Techniques of multiplication and division for automatic binary computers. Quart. J. Mech. Appl. Math. 11 (1958), S. 364–384.

• Uni-Bldenburg.de: SRT-Division , Wiland Schmalle, Retired Professor of Mathematics at the Carl of Ossietzky University Oldenburg, supplement to a participation lecture on the subject of SRT division (PDF; 284 KB)
• tu-muenchen.de: Software – Disaster, and how to remove them , Proseminar on Pentiumbug, December 11, 2002, (PDF; 421 KB)