JPH0789315B2 - Rational arithmetic unit - Google Patents

Description

The present invention relates to a data processing device, and more particularly to a rational number arithmetic device suitable for performing reduction at high speed.

[Conventional technology]

There are various fields in the use of electronic computers in science and technology as well as numerical calculations, and mathematical processing is one of them. In mathematical processing, for example, the coefficient of a polynomial is calculated using a rational number (numerator,
Denominator integer pair) is often expressed.

By the way, proposals for rational number formats for direct application to hardware are currently at the stage of desk research, and in the actual use of electronic computers, integers (numbers in fixed-point format) are actually used.
It has been processed by software by combining the four arithmetic operations. The reason for this is that there are severe restrictions on the conventional hardware implementation technology for configuring a computer, and in addition to the arithmetic functions for numerical values in fixed-point format and floating-point format, the hardware for arithmetic functions for numerical values in rational number format is also used. It is conceivable that the alternative function could be implemented by software at the expense of speed, because there was no room to implement it.

The representation format for handling rational numbers with an electronic computer is described, for example, on page 5 of "Computer High-Speed Computing Method" (published by Modern Science Co., Ltd., September 1, 1980).

[Problems to be solved by the invention]

As the use of mathematical expression processing in electronic computers using rational numbers has advanced, high-speed processing of rational number operations has been desired. In the arithmetic operation of rational numbers, when the first operand is a / b and the second operand is c / d (there are a, b, c, d are integers), the addition result: (ad + bc) / bd subtraction result: (Ad-bc) / bd Multiplication result: (ac) / (bd) Division result: (ad) / (bc). As can be easily seen from the above calculation results, there is a problem that the number of digits increases as much as possible if the result is not reduced in the arithmetic operation of rational numbers, and even if the hardware implementation technology progresses, the numerical value in rational form is directly processed by hardware. It was the last challenge to do.

An object of the present invention is to reduce a given rational number numerator and denominator to obtain an irreducible numerator and denominator, or to obtain a irreducible approximate numerator and denominator within a certain number of digits by a high-speed rational number arithmetic device. To provide.

[Means for solving problems]

The rational number arithmetic unit of the present invention includes a dividend, a divisor, an old numerator,
Multiple registers that hold the values of the new numerator, old denominator, and new denominator respectively, division means that repeatedly calculates the quotient by dividing by the dividend and divisor, and multiplication by the quotient obtained by the divisor and the above division means Then, the product of the multiplication and the dividend are added, and the calculation means for iteratively calculating the remainder is selected, and the divisor is selected as the dividend in the next iterative calculation and set in the corresponding register, and the above-obtained remainder is calculated. First multiplication means for selecting the divisor in the next iterative calculation and setting it in the corresponding register, multiplication by the new numerator and the quotient obtained by the division means, and addition by the multiplication product and old numerator, Select the new molecule as the old molecule in the next iteration calculation and set it in the corresponding register, and select the molecule obtained above as the new molecule in the next iteration calculation. Applicable Second selection means set in the register, multiplication means by the new denominator and the quotient obtained by the division means, addition means by the product of the multiplication and the old denominator, and calculation means for iteratively calculating the denominator; Third selecting means for selecting the new denominator as the old denominator in the next iterative calculation and setting it in the corresponding register, and selecting the obtained denominator as the new denominator in the next iterative calculation and setting it in the corresponding register; The detecting means for detecting each of the condition that the obtained remainder becomes zero, that the new numerator exceeds the predetermined number of digits, and that the new denominator exceeds the predetermined number of digits, and the detecting means Based on the information, it comprises a dividing means and a control means for repeating the operation of the calculating means or ending the repetition and outputting the reduced numerator and denominator.

[Action]

For any real number r, using the Gaussian symbol “r” (the largest integer not exceeding r), In other words, the regular continued fraction expansion of r, Is obtained. If r is a rational number, the expansion ends in a finite number of times (rm = bm), and if r is an irrational number, the expansion does not end in a finite number of times. The nth approximation fraction of this regular continued fraction has the form of irreducible fraction, , P _-2 = O, P _-1 = 1, Q _-2 = 1, Q _-1 = 0, the recurrence formula P _n = P _n-2 + b _n P _n-1 ,, n ≧ 0 (5) Q _n = Q _n-2 + b _n Q _n-1 , n ≧ 0 It is well known numerically that (6) holds, for example, edited by The Mathematical Society of Japan, Second Edition, Iwanami Shoten ( June 1968) pp.5
31-532.

Here, for b _n By setting r = r ₀ , R _n-2 = P, R _n-1 = Q, R _n = R _n-2 −b _n R _n-1 (7) is obtained. In equation (7), the dividend is R _n-2 and the divisor is R
b _n can be obtained as the quotient of division when _n-1 .

Of the register group holding the dividend, the divisor, the old numerator, the new numerator, the old denominator, and the new denominator, the registers holding the dividend and divisor store R _n-2 and R _n-1 in the expression (7), The register holding the old numerator and the new numerator stores the formulas (5) P _n-2 and P _n-1 , and the register holding the old and new denominators stores the formula (6).
Stores Q _n-2 and Q _n-1 . Also, in the division means, equation (5),
Equation (7) is used in the calculation means for obtaining b _n (quotient) used in equations (6) and (7), and the dividend is added to the product of the divisor and the quotient, and the new numerator adds the old numerator to the product of the quotient. The computing means executes the equation (5), and the computing means for adding the old denominator to the product of the new denominator and the quotient executes the equation (6).

The selecting means is arranged between these registers and between the dividing / calculating means and the register (7), (5), (6).
A high-speed rational arithmetic operation by hardware is achieved by making it possible to repeatedly execute an expression, and further determining the end of the iterative calculation using the detection means and the control means and outputting the result.

〔Example〕

 An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram of an embodiment of a rational number arithmetic unit of the present invention, in which 1 is a control circuit for controlling the entire rational number arithmetic unit, 2 is a dividend input selection circuit, 3 is an old numerator input selection circuit, 4 is the old denominator input selection circuit, 5 is the divisor input selection circuit,
6 is a new numerator input selection circuit, 7 is a new denominator input selection circuit, 8
Is a dividend register, 9 is an old numerator register, 10 is an old denominator register, 11 is a divisor register, 12 is a new numerator register, 13 is a new denominator register, 14 is a dividend effective bit length detection circuit, 15
Is a divisor effective bit length detection circuit, 16 is a first operation number selection circuit, 17 is a second operation number selection circuit, 18 is a first operation number bit shifter, 19 is a second operation number bit shifter, and 20 is a quotient bit length prediction Circuit, 21 inversion circuit A, 22 table address selection circuit, 23 table address register, 24 table information storage unit, 25 augend selection circuit, 26 multiplicand selection circuit, 27 multiplier selection circuit A, 28 Is the augend register A,
29 is a multiplicand register, 30 is a multiplier register, 31 is an inversion circuit B, 32 is a multiplier selection circuit B, 33 is a composite arithmetic unit, 34 is an operation result register, 35 is a partial commercial bit shifter, 36 is an operation result delay register, and 37 is The augend register B, 38 is a bit residue shifter for partial remainder, 39 is an iteration end condition detecting circuit, 40 is a final numerator selecting circuit, 41 is a final denominator selecting circuit, 42 is a final numerator register, and 43 is a final denominator register. There is.

At the beginning of the divisor, the numerator of the divisor is selected by the dividend selection circuit 2, the constant “0” is selected by the old numerator selection circuit 3, and the constant “1” is selected by the old denominator input selection circuit 42. The denominator to be divided is selected by the divisor input selection circuit 5, the constant “1” is selected by the new numerator input selection circuit 6, and the constant “0” is selected by the new denominator input selection circuit 7. The dividend register 8 and the old numerator register, respectively. 9, old denominator register 10, divisor register 11, new numerator register 12,
It is set in the new denominator register 13. Here, the bit length of the dividend register 8 and the divisor register 11 is 64, and the bit length of the old numerator register 9, old denominator register 10, new numerator register 12, and new denominator register 13 is 32. The numbers handled in this embodiment are binary integers in 2's complement notation.

The outputs of the dividend register 8 and the divisor register 11 are detected by the dividend effective bit length detection circuit 14 and the divisor effective bit length detection circuit 15 as effective bit lengths, and the results are sent to the quotient bit length prediction circuit 20. The quotient bit length prediction circuit 20 determines whether the effective bit length of the dividend or divisor is 0, and the difference obtained by subtracting the effective bit length of the dividend from the effective bit length of the dividend.
Send to. Here, the effective bit length of a binary integer in 2's complement notation is the value obtained by subtracting the length of the continuous "0" bit string from the beginning, if the value is a positive integer, and the value is negative. In the case of an integer, add the value obtained by subtracting the length of the continuous bit string of "1" from the beginning from the total bit length, and add 1 if the subsequent bit string consists of all "0". The corrected value is added (1 is added even when the integer bit string is composed of all "1" s), and in other cases, the value is kept as it is without correction.

In the control circuit 1, based on the information given from the quotient bit length prediction circuit 20, when the effective bit length of the dividend or divisor is 0, the divisor processing is terminated, and a data processing device not shown in FIG. 1 is constructed. Perform appropriate processing such as sending an interrupt signal to the device. Similarly, if the result of subtraction of the effective bit length of the dividend and divisor exceeds 32, the numerator after the reduction will not fit in the 32-bit length, so an overflow will occur.
If the result of subtracting the effective bit length is negative and less than −32, the denominator after the reduction will not fit in the 32-bit length, so perform appropriate processing such as sending an interrupt signal to another device as an underflow. Abandon processing. Regarding overflow and underflow, when the absolute value of the result of subtraction of the effective bit length of the dividend and divisor is 31 or 32, the numerator or denominator after the reduction depends on the data of the dividend and divisor.
Whether or not it fits into 32 bits is determined. This is an overflow when the iterative end condition determination circuit 39 detects that the effective bit length of the operation result corresponding to the equation (5) of the first iterative calculation exceeds 32, When it is detected that the effective bit length of the operation result corresponding to the equation (6) of the first iterative calculation exceeds 32, the control circuit 1
Cancels the reduction processing and performs appropriate processing such as sending an interrupt signal to another device.

When the subtraction result of the effective bit length of the dividend and the divisor is negative and is −32 or more (32 or less in absolute value), the dividend register 8,
The contents of the old numerator register 9 and the old denominator register 10 are sequentially passed through the first operation number selection circuit 16 and are passed through the first operation number bit shifter 18 without a shift operation, and are passed through the augend selection circuit 25. Then, in the augend register 28, while the partial commercial bit shifter 35 outputs "0" and sets it in the multiplier register 30 via the multiplier selection circuit 27, the composite arithmetic unit 33 calculates the product of the multiplier parts. The augend is set to "0" in the operation result register 34 and selected by the divisor input selection circuit 5, the new numerator input selection circuit 6, and the new denominator input selection circuit 7 to select the divisor register 11, the new numerator register 12, the new denominator. When the register 13 is set, the data before update of each register is also converted into the dividend input selection circuit 2, the old numerator input selection circuit 3,
It is selected by the old denominator input selection circuit 4 and set in the dividend register 8, the old numerator register 9, and the old denominator register 10. By the above operation, data is exchanged between the multiplicand register 8 and the divisor register 11, the old numerator register 9 and the new numerator register 12, and the old denominator register 10 and the new denominator register 13, respectively.

When the subtraction result of the effective bit length of the dividend and the divisor is 0 or more and 32 or less, the following reduction processing is performed. The dividend and the divisor are selected by the first operation number selection circuit 16 and the second operation number selection circuit 17, respectively, and then the first operation number bit shifter 18 and the second operation number bit shifter 18.
After being bit-normalized (the first bit from the beginning differs from the second bit value) by the bit shifter 19 for arithmetic operation, all bits from the beginning to the third from the beginning of the divisor after bit normalization are "0". I checked if there were any and all were "0"
In this case, the exact reciprocal number corresponding to the sign of the divisor is the multiplier selection circuit without referring to the table information storage unit 24.
Selected by 27 and set in multiplier register 30. Further, when all the bits after the third from the beginning after the bit normalization are not “0”, the third to eleventh bits are set if the divisor is positive, and the third bits are set if the divisor is negative. The bit from the 11th bit to the 11th bit is inverted by the inversion circuit A21, selected by the table address selection circuit 22, set in the table address register 23, and the table information storage unit 24 is referred to. The table information storage unit 24 stores the approximate reciprocal of the divisor and is configured so that the quotient precision can be accurately calculated up to 8 bits when there is no overflow of the quotient and 9 bits when there is an overflow of the quotient. It has been done.

At the same time as preparing the approximate reciprocal of the divisor, the initial value for partial division is prepared. The dividend after bit normalization is selected by the augend selection circuit 25 and then set in the augend register 28. Partial commercial bit shifter for multiplier
35 outputs "0", which is set in the multiplier register 30 via the multiplier selection circuit A27. Also, the multiplier selection circuit B3
“0” is selected as the multiplier by 2 and the compound arithmetic unit 33 obtains the dividend after bit normalization as it is, and sets it in the arithmetic result register 34. The output of the operation result register 34 is set in the operation result delay register 36 and then set in the augend register B37.

Next, the operation for obtaining the partial quotient is started. The reciprocal of the divisor obtained as described above depending on the divisor after bit normalization is set in the multiplier register 30. In the augend selection circuit 25, "0" is selected and set in the augend register A28. on the other hand,
The bit-normalized dividend is selected by the multiplicand selection circuit 26 and set in the multiplicand register 29. Multiplier register
When the divisor is positive, the multiplier set to 30 is the multiplier as it is, and when the divisor is negative, the multiplier bit-inverted by the inverting circuit B31 is selected by the multiplier selection circuit B32. The product of the dividend and the reciprocal of the divisor is calculated and set in the operation result register 34. When a negative number is used as the multiplier, "1" is added to the lower-order truncation bit of the multiplier, so that the compound operator 33 can directly obtain the product of the two's complement. Sum of 1 bit as a code, 1 bit of partial quotient overflow, and 8 bits of partial quotient from the upper bits of the data set in the operation result register 34
10 bits are sent to the partial commercial bit shifter 35, right-shifted by the number obtained by subtracting the remainder when the predicted bit length of the quotient is divided by 8, and then selected by the multiplier selection circuit A27 and set in the multiplier register 30. To be done. From this, equation (7),
Calculations corresponding to equations (5) and (6) are performed.

First, as the augend, the partial remainder set in the augend register B37 is shifted to the left by the number of remainders obtained by dividing the predicted bit length of the quotient by 8 by the partial remainder bit shifter 38, and the augend is added. It is set in the number register 28. The bit-normalized divisor is selected as the multiplicand by the multiplicand selection circuit 26 and set in the multiplicand register 29. The multiplier is selected by the multiplier selection circuit B32 after the data set in the multiplier register 30 is inverted by the inversion circuit B31. In this way, the calculation of the dividend-divisor × partial quotient corresponding to the expression (7) is performed by the complex computing unit 33 and set in the computation result register 34 as a partial remainder.

When the quotient predicted bit length is 8 or more, the output of the operation result register 34 is set in the operation result delay register 36 in order to continue the division, and when the quotient predicted bit length is less than 8, the divisor Once selected by the input selection circuit 5 and set in the divisor register 11, the data before update in the divisor register 11 is selected by the dividend input selection circuit 2 and set in the dividend register 8.

Then, the output of the old numerator register 9 is the first operation number selection circuit.
After being selected by 16, passed through the first operation number bit shifter 18 without being shifted, it is selected by the augend selection circuit 25 and set in the augend register A28. on the other hand,
The output of the new numerator register 12 is selected by the second operation number selection circuit 17, and the second operation number bit shifter 19 shifts to the left by the number obtained by cutting off the lower 3 bits as the binary number of the estimated bit length of the quotient. It is selected by the multiplicand selection circuit 26 and set in the multiplicand register 29. As the multiplier, the output of the multiplier register 30 is selected by the multiplier selection circuit B32. In this way, the calculation corresponding to the equation (5) is performed by the composite arithmetic unit 33, and the result is set in the arithmetic result register 34.

When the predicted bit length of the quotient is 8 or more, the division is further continued, so the output of the operation result register 34 is set in the operation result delay register 36, and when the predicted bit length of the quotient is less than 8, a new Once selected by the molecule input selection circuit 6 and set in the new molecule register 12, the data before update of the new molecule register 12 is selected by the old molecule selection circuit 3 and set in the old molecule register 9.

Similarly, the output of the old denominator register 10 is the first operation number selection circuit 16
After passing through the first operation number bit shifter 18 without being shifted, it is selected by the augend select circuit 25 and set in the augend register A28. On the other hand, the output of the new denominator register 13 is selected by the second operation number selection circuit 17, and the second operation number bit shifter 19 shifts to the left by the same number of bits as in the case of the new numerator. It is selected and set in the multiplicand register 29. As the multiplier, the same ones as in the case of the old molecule and the new molecule are used as they are. In this way, the calculation corresponding to the equation (6) is performed by the complex computing unit 33, and the computation result register 34
The result is set to.

When the predicted bit length of the quotient is 8 or more, the division is further continued, so the output of the operation result register 34 is set in the operation result delay register 36, and when the predicted bit length of the quotient is less than 8, a new Once selected by the denominator input selection circuit 7 and set in the new denominator register 13, the data before update in the new denominator register 13 is selected by the old denominator input selection circuit 4 and set in the old denominator register 10. Here, when the predicted bit length of the quotient is 8 or more, the result corresponding to the expression (6) is set in the operation result register 34, and at the same time the result corresponding to the expression (5) is obtained.
Then, the result corresponding to the expression (7) is set in both the multiplicand register 29 and the augend register B7.

When the estimated bit length of the quotient is 8 or more, the above series of operations is repeated the number of times of the quotient when the estimated bit length of the quotient is further divided by 8. The difference from the above series of operations is that the output of the operation result delay register 36 is selected as the multiplicand when the partial quotient is obtained, that the partial quotient is passed through the partial commercial bit shifter 35 without being shifted, In the calculation, the partial remainder bit shifter 38 shifts the partial remainder to the left by 8 bits. In the calculation of the equations (5) and (6), the augend register B37 is used as the augend and the partial remainder bit shifter 38 shifts. Passing without doing the second
That is, the number of shifts to the left in the operation number bit shifter 19 is sequentially reduced by 8. After repeating the operation for the number of quotients obtained by dividing the estimated bit length of the quotient by 8, the dividend register 8, the old numerator register 9, and the old denominator register 10 are processed in the same manner as when the estimated bit length of the quotient is less than 8. , The divisor register 11, the new numerator register 12, and the new denominator register 13 are updated.

At the same time as the update of each register, the iterative end condition detection circuit 39 checks whether or not the iterative end condition is satisfied. When the condition for terminating the repetition is not satisfied, the data set in the above register after the update (7),
Iterative calculation corresponding to equations (5) and (6) is performed. Note that in the bit length prediction of the quotient in the second and subsequent iterative calculations, the divisor set in the divisor register 11 is not necessarily bit-normalized, and the dividend set in the dividend register 8 is bit-wise. In consideration of being in the size after being normalized, the quotient bit length prediction circuit 20 does not use the output of the dividend effective bit length detection circuit 14, and the dividend is already bit-normalized. Predict the bit length. When the iteration end condition is satisfied, the output of the new numerator register 12 and the new denominator register 13 when the partial remainder is zero, and the old numerator register 9 when the result of the iterative calculation for the numerator or denominator exceeds 32 bits, The output of the old denominator register 10 is selected by the final numerator selection circuit 40 and the final denominator selection circuit 41, respectively, and set in the final numerator register 42 and the final denominator register 43.

Although one embodiment of the present invention has been described above, when applying the present invention, the bit length of each register may be determined as desired in terms of accuracy, and the bit length of the register is set to 64,32 as in the present embodiment. There is no need to limit it.

Further, in the present embodiment, all calculations are performed by one complex computing unit, but three complex computing units may be used, and depending on the case, the complex computing unit is decomposed into an adder and a multiplier. The rational number arithmetic unit of the present invention can also be configured by using a divider that does not use the table information storage unit as in the present embodiment.

〔The invention's effect〕

As is clear from the above description, according to the present invention, since the reduction can be performed by using the high speed multiplier / divider, there is an effect in speeding up the reduction, and a high-speed rational arithmetic operation by hardware is realized.

[Brief description of drawings]

FIG. 1 is a block diagram of a rational arithmetic unit according to an embodiment of the present invention. 8 ... dividend register, 9 ... old numerator register, 10 ...
Old denominator register, 11 …… Divisor register, 12 …… New numerator register, 13 …… New denominator register, 20 …… Quarter bit length prediction circuit, 35 …… Partial commercial bit shifter, 39 …… Repeation end condition detection circuit.

Claims (1)

[Claims] 1. A rational number arithmetic device for obtaining a irreducible numerator and denominator by reducing a numerator and a denominator of a given numerical value, or an irreducible approximate numerator and denominator within a certain number of digits. , The dividend register in which the numerator to be reduced is initialized, the divisor register in which the denominator to be reduced is initialized, the constant 0 is initialized and the old numerator register is initialized, and the constant 1 is initialized. Old denominator register, new numerator register with constant 1 initialized, new denominator register with constant 0 initialized, and division by the dividend of the dividend register and the divisor of the divisor register to calculate the quotient. A division means for iteratively calculating, multiplication by the divisor of the divisor register and the quotient obtained by the division means, addition by the product of the multiplication and the dividend of the dividend register, and calculation of the remainder And the divisor of the divisor register is selected as the dividend in the next iterative calculation and set in the dividend register, and the obtained remainder is selected as the divisor in the next iterative calculation and the divisor is selected. The first selection means set in the corresponding register, the new numerator of the new numerator register and the quotient obtained by the division means are multiplied, and the product of the multiplication and the old numerator of the old numerator register are added to obtain the numerator. And the new molecule of the new molecule register is selected as the old molecule in the next iterative calculation and set in the old molecule register, and the obtained molecule is calculated in the next iterative calculation. Second multiplication means for selecting as a new numerator and setting it in the new numerator register, multiplication with the new denominator of the new denominator register and the quotient obtained by the division means, and multiplication with the product Operation means for iteratively calculating the denominator by performing addition using the old denominator of the old denominator register, and the new denominator of the new denominator register selected as the old denominator for the next iterative calculation and set in the old denominator register , Third selecting means for selecting the denominator obtained above as a new denominator in the next iterative calculation and setting it in the new denominator register, the obtained remainder becomes zero, and the new numerator exceeds a predetermined number of digits. That the new denominator has exceeded the predetermined number of digits, and the operation of the dividing means and the computing means is repeated based on the information by the detecting means and the information by the detecting means. A rational number arithmetic unit comprising: a control unit for controlling to output the reduced numerator and denominator after finishing the iteration.