Division algorithm#SRT division

SRT division has a fast division method that is used in computer arithmetic. The name comes from its three inventors ago that described in 1958 almost simultaneously and independently of the process - Dura Sweeney (IBM), James Robertson ( University of Illinois ) and Keith Tocher (Imperial College London). Known to the general public, the procedure was the Pentium FDIV bug that resulted in the first versions of Intel's Pentium processors sporadic erroneous divisions. This was due to some wrong (because missing ) entries in the quotient table.

Theoretical foundations

Given are:

  • Dividend:
  • Divisor:
  • Base:
  • List of numbers:

Wanted:

  • Those solution with the smallest absolute value r with the same sign as.

The aim of the SRT division is to show the expression as.

Where N is the number of iterations ( and hence the number of the calculated numbers). n is the number of data for the calculation of the digits before the decimal point iterations. For floating-point mantissa is normalized n is always 0 in the processor technology, the SRT division is for practical reasons, usually with and implemented. So you can calculate the one hand, two result per iteration, on the other hand, without it, the divisor must be multiplied consuming, as consisting only of powers of 2.

The SRT division can thereby be divided into two components, one in the actual division algorithm, on the other hand in the digit selection function that is implemented in the processor technology in the rule with the aid of a table. The digit selection function receives, for example, the 6 most significant bits of the intermediate result and the four most significant bits of the divisor and returns the result to the next quotient digit back from.

The SRT division in practice

Conventional method of division

In the conventional division method starting with the most significant digits, check how many times the divisor is contained, listed the number as a most significant digit of the result, subtract the divisor corresponding to frequently. For the next step, which computes 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 ratio was determined with a satisfactory accuracy.

Example:

15624829:523 = 29875 remaining 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 method

In deciding how often the divisor divides the currently considered part of the number, the total number must be present. An estimate is not enough. The time required for an addition increases linearly with the number of digits, because transfers can propagate in the course of the addition, in the worst case of the least significant digit to most significant digit (Example: 99999999999 1), so that the addition can not be parallelized. Since computers use binary numbers, so possess only the digits 0 and 1, there are even "small" numbers of many digits. The four use the example numbers (dividend, divisor, quotient and remainder) eg be represented in binary number system as follows:. ⇒ 15624829 111011100110101001111101, 523 ⇒ 1000001011, 29875 ⇒ 111,010,010,110,011, 204 ⇒ 11001100 In order to simplify the switching units, computers are also working normally with a constant number of bits. If the number is 523 words stored in a 64 -bit register, then is also expected with 64 bits ( most of which are leading or final bits for floating point numbers are zeros ).

Saved -carry addition

To solve the problem with the carries, uses the SRT method to the Saved -carry addition ( to German: Saved unearned ) back. In this addition, the result is calculated, although the carries are ignored. These are stored separately and must be later added to obtain the correct result.

Example:

15624829   52329875    ========    67943694 (earnings before transfers )   00001101 - ( unearned )    ========   67954704 ( Corrected result) No correction of wrongly guessed quotient digits

When using pencil and paper performs a division, you have to intelligently guess how the next digit of the quotient is.

Example:

15624829:523 = Here you would based on the first digits " guess " that the 523 three times to fit the 1562 into it. It leads, however, to step to the end, you realize that the assumption was wrong:

15624829:523 = 3 -1569   ----     -7 In corrective division method (see example at the beginning ) you would now correct the ratio to 2 and add 523 again (or completely re- count ):

15624629:523 = 2 -1569   ----     -7   523   ----    516 The SRT - method is a non - corrective division method, so here remains in principle -7. In this case, you have the subtraction but then perform the entire number:

15624829:523 = 3 -15690000   --------     -65 171 Only in the next calculation step, the negative number is now corrected by the quotient than -1 (ie, negative, here represented by an overline ) is assumed:

_   15624829:523 = 31 -15690000   --------     -65 171    523000    -------     457829 If this procedure is continued ...

__   15624829:523 = 31935 remaining 204 -15690000 ( -523 * 10000 * 3)   --------     -65 171    523000 (-523 * 1000 * -1)    -------     457829    -470 700 ( -523 * 100 * 9)    -------     -12 871     15690 (-523 * 10 * -3)     ------       2819      -2615 ( -523 * 1 * 5)      -----        204 So ... for example, one obtains the quotient (negative is bold) 31935th This result represented in a redundant notation (each number can be represented in many ways ) now needs to be normalized. 31 means nothing more than 30 minus 1, so 29 is followed by a positive and 9 negative 3 so 87 and finally a positive 5 Thus, the quotient is corrected: 29875 (plus the rest of 204 ) which was the result of the first example corresponds.

Both together

Since we must choose the division that are too large quotient ( since this error can obviously correct again in the next step ), we no longer need in addition the entire number including transfers to be added, it is sufficient to approximate, eg the sum without carries, the carries can then be added in the next step. However, this is not without limitations:

__ 15690000 ( The magnitude smaller number is magnitude of the   15624829:523 = 3195? -15624829 Larger deducted sign correction only at the result) -15690000 ( -523 * 10000 * 3) --------- --------- 76281 ( Result without carry, ALWAYS () positive! -     -76 281 (result) because yes no transfer is taken into account )    523000 (-523 * 1000 * -1) -11110 ( carry digits, ALWAYS (!) Negative ( or 0) )     11110 ( Carry) ------    ------- 65171 ( Corrected difference, here positive)    568939 (Result) → same as in the previous example    -470 700 ( -523 * 100 * 9) ←    -111 110 ( carry) |    ------- - Based on the number 568 735 would have the ratio actually     Be -23 981 (Result) 10 or even 11, but since the quotient be only one digit     26150 (-523 * 10 * -5) may ( positive or not ), here is 9 the maximum.     11110 ( Carry)     ------     14389 (Result)      -? ( -523 * 1 * ? )      -1110 ( Carry) In the last step, a two-digit number would have to be elected to the too small selected in the penultimate step -5 rebalance. Even if be used from now on only positive 9s as digits, the correct result can not be achieved. Therefore, it is imperative to complete ( ie including transfers ) to calculate at least the three most significant digits. Here are the three highest digits (which may be 0 ) is fully summed, the rest as in the previous example with Saved Carry Addition:

__   156 | 24829:523 = 31936 -156 | 90000 ( -523 * 10000 * 3)   === | ===== -000 |? ? ( Partial result with carry ) ← The two most significant digits completely calculated, - |? 76281 ( partial result without carry ) the result may differ by only 1 from the correct result) -000 | 76281 (total income - part with, part without carry )   -007 | 6281 (total income - part with, part without carry )   052 | 3000 ( -523 * 1000 * -1)   001 | 1110 ( carried over from the partial result without carry )    === | ==== [ OK]   046 |? ? ( Partial result with carry )   |? 8939 ( partial result without carry )   046 | 8939 ( Mixed overall result )    468 | 939 ( Mixed overall result )    -470 | 700 ( -523 * 100 * 9)    -011 | 110 ( carried over from the partial result without carry )     === | ===    -013 |? ( Partial result with carry )    - |? 181 ( partial result without carry )    -013 | 981 ( Mixed overall result )     -139 | 81 ( Mixed overall result )     156 | 90 ( -523 * 10 * -3)     011 | 10 ( carry-over from the partial result without carry )      === | == [ OK]     028 |? ( Partial result with carry )     |? 29 ( partial result without carry )     028 | 29 ( Mixed overall result )       282 | 9 ( Mixed overall result )      -313 | 8 ( -523 * 1 * 6)      -001 | 0 ( carried over from the partial result without carry )       === | =      -032 |? ( Partial result with carry )      - |? 9 ( partial result without carry )      -032 | 9 ( Mixed overall result )       -329 | (Mixed overall results )       000 | (There follows no quotient digit )       010 | ( Carried over from the partial result without carry        === |       -319 | ( Remainder) ← This last addition is complete with all                                  Carry bits performed. Result 31936 with residual -319, next to the quotient obtained by one here is too large must now also the negative residual is normalized here the number. The remainder is corrected by adding the divisor is added to ( then gives 204 as in the examples above), then the quotient is 31935, or normalized 29875th

Similar procedures

  • Goldschmidt Division
743390
de