JPH0769785B2 - Divider - Google Patents

Description

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a division device for performing division with high accuracy and high speed.

2. Description of the Related Art Among the four arithmetic operations, division takes a long operation time, and when a simple algorithm is used, the size of the divisor and the dividend (or partial remainder) is compared, and the type of the next operation is determined by the comparison. It is also difficult to increase the number of parallel operation circuits and shorten the operation time as in the case of multiplication because of the time-consuming processing. Therefore, a convergent division method has been proposed as an improved division method. This uses a high speed multiplier and adder / subtractor.

To simplify this explanation, consider a case in which both the divisor and the dividend are normalized by a numerical system operation expressed in a binary system (the mantissa part in the case of the floating point expression corresponds to this).

In this case, the divisor (D) is 0.1 ××× ... × (the number of significant digits N
Digit, XX is a sequence of 0 or 1) If D = 1-D ₁ , D ₁ becomes a number smaller than 0.1 (D ₁
= 0.1, D = 0.1 and the quotient only needs to double the dividend. This is a 1-digit (1-bit) left shift operation in the case of binary numbers, so there is no need to perform full-scale division. In this case, Does not lose generality even if excluded).

The division A / D can be converted into a mathematical formula as follows.

When the number of significant digits N in the numerical system is N = 52 (48N52 is large in the case of the double-precision floating point representation format), D ₁ ⁶⁴ is a number that is too small to exceed the range of significant digits and is practically 0. And the following approximate expression holds after all.

Therefore, the calculation of D _{1 to} the power of 2n and the addition of 1 and each, each term 6
Division can be performed by executing multiplication times. here Is calculated by squaring, The calculation of The most significant digit of (originally Considering that the calculation time is virtually unnecessary, since it takes the form of 1) and the top is 0), the subtraction for obtaining D ₁ is 1 and 11 times. It is possible to divide by multiplication. When a very high-speed multiplier is used, the sum of these operation times is about 1 to 2 μsec, and a relatively high-speed divider has been obtained.

INVENTION AND SUMMARY problems conventional convergence division circuit scale multiplier a subtractor and a control circuit is inevitably very make fast divider for comparably small requires but the number of multiplications is greater if It was difficult.

Although there is also known a method of executing a very high-speed division by providing a large-scale circuit exclusively for division, a normal arithmetic unit has a large proportion of executing all four arithmetic operations, and the division is performed together with the multiplication function and the addition / subtraction function. It has a function. That is, since the multiplier and the adder / subtractor are located near each other, if these arithmetic functions are used effectively, the division can be executed without increasing the circuit scale.

Therefore, a method that requires a smaller number of multiplications by using a method similar to the convergent division algorithm is required.

In view of such a point, the present invention has an object to provide a faster and more compact division device.

Means for Solving the Problems The present invention is a normalized numerical system having a radix R (R-adic number) and N significant digits, and the upper M digits (D ₀ ) of the divisor (D) (however, 0).
At least the most significant digit of <M <N) is not zero (R-
1) · Reciprocal table storing the reciprocal of the value corresponding to each of the R ^M-1 numerical values, and output means for outputting the corresponding reciprocal when the reciprocal table is accessed by the numerical value of the upper M digits, An output from the output means, a dividend, and a high-speed convergence type division unit which inputs the value of the lower (N−M) digits of the divisor are provided. (1) The high-speed convergence type division unit is at least (N−M +
1) It includes a subtraction circuit for performing subtraction of digits, a multiplication circuit for performing multiplication of N digits, and a register circuit for temporarily storing the multiplication result and outputting the most significant digit as 1, and the dividend (A)
The division A / D for is approximated by A / DA ・ B ・ {1 + E ・ (1 + E ・ (... E ・ (1+
E)))} (4) However, B is a reciprocal table output value, a division device characterized by executing E = (subtraction circuit output value) · B, or (2) this high-speed convergence type The division unit includes at least a multiplication circuit that performs N-digit multiplication, a subtraction circuit that performs N-digit subtraction, and a squaring circuit that respectively squares and squares an input value,
Includes a quadratic circuit and a register circuit that temporarily stores the exponentiation result and outputs the most significant digit as 1. The division A / D for the dividend (A) is approximated by A / DA ・ B ・ (1-E)・ (1 + E ² ) ・ (1 + E ⁴ ) ...
(5) However, B is a reciprocal table output value, a division device characterized by executing using E = (D ₁ / D ₀ ) · B, or (3) This high-speed convergent division unit is at least (N-M +
1) A subtraction circuit that performs digit subtraction, a multiplication circuit that performs multiplication of N digit 2-input numerical values, a register circuit that temporarily stores the multiplication result and outputs the most significant digit as 1, and an input value A division circuit for the dividend (A), which includes a squaring circuit for executing squaring and squaring of the fourth power, and a register circuit for temporarily storing the exponentiation result and outputting the most significant digit as 1.
Approximate A / D to A / DA ・ B ・ (1 + E) ・ (1 + E ² ) ・ (1 + E ⁴ ) ...
(6) However, the division device is characterized in that B = reciprocal table output value and E = (subtraction circuit output value) · B.

The reciprocal of the value corresponding to the upper M digits (D ₀ ) of the divisor (D) is stored in advance in the reciprocal table, and this value and the value of the lower (NM) digit of the divisor (D) are used to approximate the above Formula (4),
By executing the calculations of (5) and (6), omitting the addition time with a special register in the process, and performing parallel processing of cumulative calculation and multiplication by dedicated circuits for squaring and quadratic, a compact size is achieved. It enables high-speed division.

Embodiment First, a configuration example showing a concept common to the embodiments of the present invention will be described. Instead of (1) and (2) as an approximate expression for division, the following approximate expression ((3) is used to perform even faster division.

As an example of D _{0 in the} formula, only the upper M digits of the number of significant digits N are the same as the divisor D, and the lower (N−M) digits are all zero. An inverse table is prepared for. (1 / for specific D ₀
D ₀ ) is output, the multiplication means, subtraction means for subtracting a small number from 1 to obtain a difference, and control means for controlling execution of each operation. The lower (N−M) digits of D ₀ for this reciprocal table do not necessarily have to be all zero.

This reciprocal table and a read-only memory (ROM) 1 as its output means are used.
FIG. 1 shows an example of the configuration including the subtractor 13 and the subtractor 13.

As an example of the numerical value, consider an example in which the number of significant digits is 52 and is displayed in binary, and as D _0, for example, upper 12 digits (the highest digit is 1) is taken. Candidates for D ₀ Therefore, since 2 ¹¹ (2048) present a scale of ROM1 becomes 2048 words × 52 bits (about 100k bits). Usually, the access time of ROM1 of this level is about 52 times of the multiplication time.
It is about 1/2. The operation in this case is as follows. R
When OM1 is accessed by D ₀ (that is, the data stored in the M-bit address corresponding to D ₀ is read),
The reciprocal of D ₀ , 1 / D _0, is output. The product D ₁ / D ₀ of this and the remaining low-order bit (NM) of the divisor is obtained by the multiplier 12.
Calculate (1-D ₁ / D ₀ ) using the subtractor 13 (calculation time is 1/2 or less of multiplication). The product (D ₁ / D ₀ ) · (1-D ₁ / D ₀ ) is calculated by the multiplier 12, and this operation is repeated until A and 1 /
To complete the calculation of equation (3) by multiplying by D ₀ , each operation and process is executed the following number of times.

52-digit multiplication: 6 times 52-digit subtraction: 4 times (equivalent to 2 multiplications) ROM read: 1 time (equivalent to 0.5 multiplications) If all the operation times are converted to multiplication, it will be equivalent to 8.5 times.

The control means 14 is a part that controls the execution of these series of arithmetic processes.

The above is the configuration showing the common idea of the present invention, and the first embodiment of the present invention will be described next. In the present invention, the following approximate expression (4) is used instead of the conventional approximate expression (1), (2), or (3). A configuration diagram in this case is shown in FIG.

Here, D ₀ is the 0th-order approximation value of D such that the upper M digits of the divisor D are the same and the lower (N−M) digits are all zero, as in the previous embodiment. That is, D, D ₀ and D ₁ are as follows.

D = [d _N d _N-1 …… d _{N-M + 1}・ d _NM …… d ₂ d ₁ ] D ₀ ＝ [d _N d _N-1 …… d _{N-M + 1} 0 …… 00] D ₁ = [00 ... 0d _NM ... d ₂ d ₁ ] On the other hand, d is a numerical value such that only the Mth digit from the higher order is 1 and the others are zero, as shown below.

d = [00 ... 10 ... 00] That is, the 0th order approximation value D ₀ + d of D in this case is lower (N−
Use the one that rounds up M).

Data in this case the reciprocal ROM21 accesses in D ₀ when 1 / (D
Data is set so that the data of ₀ + d) is read. First, the subtraction (d−D ₁ ) must be executed once, but 1 is added to the minute number by simply setting 1 to the highest level, so that the calculation time is substantially unnecessary. The number of times of arithmetic processing in this case is as follows.

52 digit multiplication 6 times 52 digit subtraction 1 time (corresponding to 0.5 multiplication, but it does not need actual calculation time because it affects ROM access time) ROM read 1 time (corresponding to 0.5 multiplication) Converting all calculation times into multiplication, equivalent to 6.5 times Become.

A block diagram of another embodiment is shown in FIG. This is based on the following approximate expression (5) obtained by further modifying the approximate expression (3).

A / DA ・ (1 / D ₀ )-(1-D ₁ / D ₀ ) ・ (1+ (D ₁ / D ₀ )
² ) ・ (1+ (D ₁ / D ₀ ) ⁴ ) …… (5) In this case, a squarer and a squarer are also prepared separately (however, squarer
In this case, 35 is a multiplier with a precision of 28 digits (52-12 × 2) (bits), and 4 multiplier 36 is a ROM with a precision of 4 digits (52-12 × 4). The operation reads (1 / D ₀ ) from the reciprocal ROM 31.

The multiplier 32 calculates D ₁ * (1 / D ₀ ).

The multiplier 32 calculates A * (1 / D ₀ ).

Calculate (D ₁ / D ₀ ) ² , (D ₁ / D ₀ ) ⁴ with the squarer 35 and the squarer 36,
The subtracter 33 calculates 1-D ₁ / D ₀ .

In the multiplier 32 To calculate.

Does not require calculation time] To calculate.

In the multiplier 32 To calculate.

Each arithmetic circuit has 30 to 52 digits multiplication 6 times 52 subtraction 1 time (however, it is 0 because it depends on the multiplication time) ROM access 1 time (corresponding to 0.5 times of multiplication) That is, the total calculation becomes 6.5 times of multiplication.

In this case, the multiplier for the squarer 35 may use the 52-digit multiplier 32.

A block diagram of another embodiment is shown in FIG. This configuration is based on the following approximate expression (6).

In this case, the reciprocal ROM 41 is used to calculate (1 / D ₀ + d), and the subtractor 43 calculates d−D ₁ .

The multiplier 42 calculates (d−D ₁ ) * (1 / D ₀ + d).

The multiplier 42 calculates A * (1 / D ₁ + d).

2 multiplier 45, 4 multiplier 46 To calculate.

In the multiplier 42 To calculate.

In the multiplier 42 To calculate.

In the multiplier 42 To calculate.

That is, also in this case, the number of calculations is 6.5, which is equivalent to multiplication.

EFFECTS OF THE INVENTION As is apparent from the description of the embodiments, according to the present invention, the number of executions (that is, the execution time) of all the operations including the multiplication to be performed to obtain the quotient is significantly reduced. It can be seen that a faster division can be performed by adding one ROM to the division device. Further, in the embodiment corresponding to FIGS. 3 and 4, a squarer and a squarer are further required. In this case, however, the operation operands before and after are independent, so that the multiplier is With a two-stage pipeline configuration,
Each multiplication execution time is halved equivalently. Therefore, the division execution time can be further shortened to 0.5 times equivalent to 0.5 times equivalent to 1 times equivalent to 4.5 times as a whole.

Whereas the conventional convergence type is equivalent to 11 times of multiplication and 1 time of subtraction, that is, 11.5 times of multiplication, the operation time is improved by 1.5 to 2.5 times by adding some elements and circuits shown in the present invention.

[Brief description of drawings]

FIG. 1 is a block diagram of a dividing device showing the concept common to the embodiments of the present invention, FIG. 2 is a block diagram of the first embodiment of the present invention,
FIG. 3 is a block diagram of the second embodiment of the present invention, and FIG. 4 is a block diagram of the third embodiment of the present invention. 10 …… High-speed convergence type divider, 11 …… ROM, 14 …… Control means.

Claims (3)

[Claims] 1. A normalized numerical system having a radix R (R-adic number) and N significant digits, in which the upper M digits of the divisor (D) (where 0 <M
At least the most significant digit of <N) is not zero (R-1)
· The reciprocal of the value (D ₀ + d) corresponding to each of the R ^M-1 numerical values {D ₀ } (where d is only the highest digit is 1 and the other digits are N−M + 1 digits of R) A reciprocal table for storing the reciprocal table, an output means for outputting the reciprocal corresponding to the reciprocal table accessed by the numerical value of the upper M digits, an output from the output means, a dividend, and a lower order of the divisor (NM). A high-speed convergent division unit that receives a digit value (D ₁ ) as an input, and this high-speed convergence division unit executes subtraction (d−D ₁ ) using at least d as a minuend input and D ₁ as a subtraction input. A subtraction circuit and a multiplication circuit for performing multiplication of N digit 2-input numerical values;
A register circuit that temporarily stores the result of this multiplication and outputs with the most significant digit set to 1, and divides the dividend (A) by A / D
Is an approximate expression A / DA ・ B ・ {1 + E ・ (1 + E ・ (1 + E ・ (... E
· (1 + E))) )} _{where, B = 1 / (D 0} + d), E = (d-D 1) / (D 0 + d) dividing apparatus characterized by executing with the. 2. A normalized numerical system having a radix R (R-adic number) and N significant digits, in which the upper M digits of the divisor (D) (where 0 <M
At least the most significant digit of <N) is not zero (R-1)
.R ^M-1 reciprocal table for storing the reciprocal of the value (D ₀ ) corresponding to each numerical value {D ₀ }, and outputting the reciprocal corresponding when the reciprocal table is accessed by the upper M digits And a high-speed convergence type division unit which inputs the output from this output unit, the dividend and the value (D ₁ ) of the lower (N−M) digits of the divisor. At least 1 is used as the minuend input and the multiplication result (D ₁ · (1 / D ₀ )) is subtracted as the subtraction input (1
-D ₁ / D ₀ ), a subtraction circuit for executing N-digit 2-input numerical value multiplication, a squaring circuit for respectively squaring and squaring of an input value, and a squaring circuit, A register circuit that temporarily stores this exponentiation result and outputs with the most significant digit set to 1 is used to calculate the division A / D for the dividend (A) as an approximate expression A / DA ・ B ・ (1-E) ・ (1 + E ² ) (1 + E ⁴ ) However, a division device characterized by executing using B = 1 / D ₀ and E = D ₁ / D ₀ . 3. A normalized numerical system having a radix R (R base number) and N significant digits, in which the upper M digits of divisor (D) (where 0 <M
At least the most significant digit of <N) is not zero (R-1)
· The reciprocal of the value (D ₀ + d) corresponding to each of the R ^M-1 numerical values {D ₀ } (where d is only the highest digit is 1 and the other digits are N−M + 1 digits of R) A reciprocal table for storing the reciprocal table, an output means for outputting the reciprocal corresponding to the reciprocal table accessed by the numerical value of the upper M digits, an output from the output means, a dividend, and a lower order of the divisor (NM). A high-speed convergent division unit that receives a digit value (D ₁ ) as an input, and this high-speed convergence division unit executes subtraction (d−D ₁ ) using at least d as a minuend input and D ₁ as a subtraction input. A subtraction circuit and a multiplication circuit for performing multiplication of N digit 2-input numerical values;
A register circuit that temporarily stores this multiplication result and outputs the most significant digit of 1 and a squaring circuit and a squaring circuit that respectively execute the square and the fourth power of the input value; Includes a register circuit that outputs 1 digit, and divides A / D with respect to the dividend (A) by an approximate expression A / DA ・ B ・ (1 + E) ・ (1 + E ² ) ・ (1 + E ⁴ ) A division device characterized by executing using (D ₀ + d) and E = (d−D ₁ ) / (D ₀ + d).