Background of the Invention
This invention relates to a method and apparatus for division in a digital computation. This invention is particularly useful for implementing the power series to an electronic digital computer system.
Heretofore, it has been suggested to implement a multiplication method to division process. One technique described in "The IBM System/360 Model 91: Floating-Point Execution Unit" IBM Journal of Res. & Develop. Vol. 11 No. 1, 1967 pp. 34-54 by S. F. Anderson et al. suggests that a succession of factor multiplications to the dividend and divisor leads to the results; an approximated quotient and one, respectively. The selection of the multiplying constant a.sub.k is the essential part of the procedure. This procedure is shown:
Aa.sub.0 a.sub.1 a.sub.2 a.sub.3 a.sub.4 . . . a.sub.n is an approximated quotient, when Ba.sub.0 a.sub.1 a.sub.2 a.sub.3 a.sub.4 . . . a.sub.n is approaching to one. The divisor can be expressed as C=1-x where x.ltoreq.1/2, since C is a bit-normalized, binary floating-point fraction of the form 0.1yyy . . . . Now, if the constant a.sub.0 is set equal to 1+x and the divisor is multiplied by a.sub.0, then C.sub.1 =Ca.sub.0 =(1-x).multidot.(1+x)=1-x.sup.2 where x.sup.2 .ltoreq.1/4. The new divisor is guaranteed to have the form 0.11yyy . . . . Likewise, select a.sub.1 =1+x.sup.2 with double the leading 1 on the next iteration to yield C.sub.2 =C.sub.1 a.sub.1 =(1-x.sup.2).multidot.(1+x.sup.2)=1-x.sup.4 where x.sup.4 .ltoreq.1/16. In general, if x.sub.i .ltoreq.(1/2).sup.n then x.sub.i+1 .ltoreq.(1/2).sup.2n. Thus, by continuing the multiplication until x.sub.i is less than the least significant digit (bit) of the divisor (division fraction), the desired result, namely a denominator (a constant multiplied divisor) equivalent to one (=0.111 . . . 111 . . . ) is obtained. The multiplier a.sub.i for each succession is the two's complement of the denominator a.sub.i =2-a.sub.i-1 =2-(1-x.sub.i-1)=1+x.sub.i-1.
The first multiplier a.sub.0 is generated by a table-lookup which inspects the first seven bits of the divisor. The first multiply guarantees a result which has seven similar bits to the right of the binary point (1+x has the form b.bbbbbbb . . . etc.) where b is the negated number of b. The following sequence outlines the operations: (1) determine the first multiplier by a table-lookup, (2) multiply B by a.sub.0 forming B.sub.1, (3) multiply A by a.sub.0 forming A.sub.1, (4) truncate B.sub.i and complement to form a.sub.i, (5) multiply A.sub.i by a.sub.i forming A.sub.i+1, (6) multiply B.sub.i by a.sub.i forming B.sub.i+1, (7) iterate on (4), (5), and (6) until B.sub.i+n approaches one and then A.sub.i+n becomes an approximated quotient of the division A/B.
It is one object of the present invention to provide a method and apparatus for performing division A/B.
It is another object to accomplish a division process quickly by evaluating a power series.
Other objects and features of the present invention will be apparent in view of the following general and specific descriptions of embodiments of the invention.
Summary of the Invention
In accordance with a principal feature of the present invention, the digital number q of the divisor B=D.sup.n +q (where D is a base radix, D.sup.n is a pseudoradix and the domain of q is in 0.ltoreq.q.ltoreq.D.sup.n (D-1)) is successively used in order to obtain acceleration constant a.sub.i for i=0,1,2, . . . , and in accordance with a recursive application of an acceleration determining process described herein, the successively multiplied result of the division A/B by acceleration constants guarantees a small covergence rate of the power series so that the division process is accomplished by evaluating a few terms in the power series.
The apparatus comprises a control unit comprised of sequential circuitry, a divisor register comprised of a row of associated flipflops, a dividend/quotient register comprised of a row of associated flipflops, multiplication means, a counter unit comprised of structured circuitry with feedback loops, an adding unit, and a logic unit comprised of sequential logical circuitry, said components being interfaced in a manner to accomplish the computational process of this invention.
Brief Description of the Drawing
In the accompanying drawing forming a part of this specification and in which similar numbers of reference indicate corresponding parts in all the figures of the drawing:
FIG. 1 is a graph showing mathematical functions and boundaries of different acceleration constants applicable to the value q.
FIG. 2 shows a functional relationship between the domain and the range of the mathematical functions and also shows a successive application process of the determining acceleration constants.
FIG. 3 is a table of subdivisions described herein.
FIG. 4 is a block diagram chart showing steps to perform division 1/B based on the invention.
FIGS. 5a and 5b are block diagrams indicating a system of conventional electronic digital equipment for performing the division described herein.
FIG. 6 is an operational block diagram indicating a performing logic of the successive multiplication of a multiplier to a dividend A and a divisor B.
FIG. 7 is an operational block diagram depicting a determination of an acceleration constant.
FIG. 8 is an operational block diagram illustrating an evaluation process of the power series.
Detailed Description of the Invention
A division A/B where A and B are represented in a radix D can be accomplished by evaluating a power series
if .vertline.P/D.vertline. is less than one where B=D+P. This evaluation does not involve any division since (1/D).sup.i is a digit shift operation to the left by i-digits. The series evaluates the reciprocal of a constant B. When a pseudoradix D' is introduced such that D'=D.sup.n with .vertline.D.sup.n .vertline.>.vertline.B.vertline. for the smallest integer n=1,2,3, . . . , the convergence condition .vertline.P/D'.vertline.<1 in (1) is always satisfied. We shall call n the power of a pseudoradix. However, when .vertline.P/D'.vertline. is close to one, the convergence rate of (1) is slow and the division process of power series evaluation (1) is practically useless due to the required computation of many terms in (1). Since the truncation error .vertline..epsilon..vertline. at the i.sup.th term of (1) is given by .vertline.A/B.vertline..multidot..vertline.P/D.vertline..sup.i, the number i could be a large quantity to obtain a small .vertline..epsilon..vertline.. When such a slower convergence of the power series in division is observed, this invention forces the division to converge quickly by providing an acceleration factor. Thus, the power series implementation becomes practical and useful.
A number B (a divisor) having a radix D is represented generally as:
where for example the radix is ten and the number B is 189, then the pseudoradix is D.sup.2 =100 and P is 89. When the power is increased by one the value of P, for a given B, becomes a negative number. For example B is 189 in the radix ten and n is 3, then D.sup.3 =1000 and P=-811. For the sake of simlicity, we introduce a positive quantity q for P. Thus the value P can be described with q.
Note: when P=0, namely B=D'=D.sup.n or D.sup.n+1, the reciprocal of B becomes 1/D', that being just a digit shift operation. Now the ratio P/D' in (1) is represented by functions of q:
From equations (2) the domain of q is 0.ltoreq.q.ltoreq.D.sup.n (D-1) where D.sup.n is a pseudoradix. Since q depends on the pseudoradix, the domain may be considered a fixed interval 0.ltoreq.q.ltoreq.D'(D-1) relative to a pseudoradix D'.
Let us consider an overrelaxation of f.sub.2 (q) with a parameter `a`. We have
where `a` is an integer in the domain 1.ltoreq.a.ltoreq.D. Note: as special cases, g(q,1)=-f.sub.2 (q) and g(q,D)=-f.sub.1 (q). The functions f.sub.1 (q), f.sub.2 (q), and the family of g(q,a) for a=2,3,4, . . . , D-1 are illustrated in FIG. 1.
The intersections between f.sub.1 (q) and the family of g(q,a) are marked with M.sub.a for a=1,2, . . . , D in FIG. 1. Consider the saw shaped zig-zag lines crossing the abscissa which are connected to another line of the family by equating -g(q.sup.+,a)=g(q.sup.+,a-1) for a=2,3, . . . , D. The quantity of q.sup.+ is
where `a` is regarded as an argument of q.sup.+. The points of q.sup.+ (a) appear with the mark M.sub.a ' in FIG. 1. The value of q.sup.+ (a) is a boundary of a different parameter applicable to the regions of q. We shall define these regions as follows: ##EQU1## We shall call the regions subdivisions of q that are depicted as S.sub.i for i=1,2,3, . . . , D-1,D in FIG. 1.
Next, we observe the following situation: although .vertline.g(q,a+1).vertline. is greater than .vertline.g(q,a).vertline. for any q in S.sub.a (refer FIG. 1) but q.sub.2 /D.sup.n is less than q.sub.1 /D.sup.n where the value of q.sub.2 is computed from q.sub.2 =-g(q.sub.1,a+1)D.sup.n. Thus, the value of q.sub.2 may belong to another subdivision S.sub.i where i.gtoreq.a and q.sub.1 is assumed in S.sub.a. The function -g(q,a+1)D.sup.n shall be denoted as q.sub.2 =h(q.sub.1,a). The entire computed mapping range of h(q,a) from the q.sub.1 domain 0.ltoreq.q.ltoreq.D.sup.n (D-1) is the interval of 0.ltoreq.q.ltoreq.D.sup.n+1. The individual subranges R.sub.a of h(q.sub.1,a) for each corresponding domain S.sub.a for a=1,2,3, . . . , (D-1) are computed as follows: ##EQU2## where q.+-.(a) for a=2,3, . . . , D is the inferior limit of q.sup.+ (a) in S.sub.a.
FIG. 2 illustrates the subranges R.sub.a and the detailed f.sub.1 (a) and g(q,a) and also shows subdivisions S.sub.1 for i=D-5,D-4, . . . , D.
In order to apply functions h(q,a) and g(q,a) recursively we will use the suffix n. Thus h(q,a) and g(q,a) become h.sub.n (q,a) and g.sub.n (q,a), respectively. The q domain becomes the interval 0.ltoreq.q.ltoreq.D.sup.n (D-1) for n, and for n+1 the q domain becomes the interval 0.ltoreq.q.ltoreq.D.sup.n+1 (D-1). Similarly for applying S.sub.a recursively we use S.sup.n.sub.a with the q domain above.
The mapping function h.sub.n+i (q.sub.i, a.sub.i) is a piece-wise linear function that maps the interval of q, or 0.ltoreq.q.ltoreq.D.sup.n+i (D-1), into the interval 0.ltoreq.q.ltoreq.D.sup.n+i+1. When the pseudoradices D.sup.n+i and D.sup.n+i+1 are neglected due to the relative definition of the subdivisions with respect to them, these intervals (the individual subranges described in (7) and each corresponding subdivisions defined in (6)) may be considered fixed upper/lower limits relative to a pseudoradix and are called relative ranges and relative domains of q, respectively. An interval consisting of the upper/lower limits of each subdivision is greater than the one of the corresponding subrange limits except the case a=D-1. In other words, a mapped relative range, which becomes the next relative domain, is narrower than its relative domain. When a successive application of h(q,a) is taking place, a distance measured from the origin in the relative q coordinate is contracting until the distance reaches the subdivision S.sub.D-a that is an invariant interval. The gradually shrinking distances are successive images of the q mapping. Thus, there is a sequence of subdivisions that are a visiting order of successive images.
Let B=D.sup.n +q.sub.0 be a constant of a divisor. If a successive q.sub.i is determined by q.sub.i+1 =h.sub.n+i (q.sub.i,a.sub.i) where q.sub.i in S.sub.a.sbsb.i.sup.n+i for i=0,1,2,3, . . . , then parameters a.sub.0,a.sub.1,a.sub.2, . . . , and a.sub.j in generating a sequence by h(q,a) have a relation:
where q.sub.j is in S.sub.D-1.sup.n+j. FIG. 2 illustrates these successive images of q.sub.0. For example if the initial q.sub.0 is in S.sub.1 then the mapped image q.sub.1 =h(q.sub.0,1) exists in R.sub.1. Since the subrange R.sub.1 is equal to the summed subdivisions of S.sub.D-3,S.sub.D-4, and the left part of S.sub.D-5, the value of q exists in the summed subdivision. Let us assume it in S.sub.D-3. FIG. 2 depicts that R.sub.1 is overlapped on the summed subdivision. By applying another mapping on q.sub.1, the image of q.sub.1, q.sub.2 =h(q.sub.1,D-3), shall belong to the subrange R.sub.D-3 that is also overlapped on parts of S.sub.D-1 and S.sub.D-2 (refer FIG. 2).
A repeated application of the mapping to a value q will result in the movement of successive images into the subdivision S.sub.D-1. As soon as the last image q.sub.j that belongs to S.sub.D-1 is obtained, the function g(q.sub.j,D-1) is evaluated, in order to find the final ratio q.sub.f. Let q.sub.0 be in the domain 0.ltoreq.q.sub.0 .ltoreq.D.sup.n (D-1). If q.sub.0 is in a subdivision S.sub.a.sbsb.0 where an integer a.sub.0 is in the interval 1.ltoreq.a.sub.0 .ltoreq.D-1 and the last q.sub.j which is the first visit in the subdivision S.sub.D-1 is obtained through a sequence of q.sub.i by successive mapping q.sub.i+1 =h.sub.n+i (q.sub.i,a.sub.i), then an acceleration factor .alpha.' is ##EQU3## The final ratio P/D' is obtained from q.sub.f =-g.sub.n+j (q.sub.j (q.sub.j,D-1), so we have
where .vertline.q.sub.f .vertline..ltoreq.1/(2D-3) is guaranteed, since 1/(2D-3) is derived by substituting equation (5) into the function g(q,a) and by setting a=D-1 in the substituted result. When the initial q.sub.0 exists in S.sub.D that is the remaining case to discuss, the final q.sub.f is determined from q.sub.f =f.sub.1 (q.sub.0). An acceleration factor for this case is D in equation (8), where .vertline.q.sub.f .vertline..ltoreq.1/(2D-1) by substituting a=D in (5).
After we obtained a ratio q.sub.f from the above method, the quantity of (8 ) must be evaluated. However, a careful inspection of the inside terms in the brace of (8) leads us to the following factorial terms: ##EQU4## We consider these terms as other acceleration factors and denote them as follows:
Thus, equation (8) becomes ##EQU5## Ignoring the terms that are smaller than q.sub.f.sup.2.spsp.l in (10), an approximated reciprocal of B becomes as follows: ##EQU6##
FIG. 3 is a subdivision table for the base radix=10 and the pseudoradix=100. It is computed from equation (6). The following examples shall utilize the table for the successive mapping of q.
The following steps illustrate a computation of 1/189 through the division process described in the block diagram of FIG. 4.
Example 1; starting B=189 with a base radix D=10,
where .epsilon.=1.0.times.10.sup.-14 is assumed.
Example 2; the same divisor is used but a different base radix D=100 is employed.
Comparing these results with the real quotient 0.00529100529100529100 . . . , we find that these numerical accuracies are correct to 12 digits (when D=10) and to 14 digits (when D=100). In the example we needed to evaluate acceleration constants of two a's (one integer multiplication, note: (D-1) multiplication is performed with a shift to the left and a subtraction) the three b's (twice of squaring operations) for the case D=10, and three a's (twice of integer multiplications) and two b's (once of squaring operation) for the case D=100. Also it was necessary to perform five subtractions in each case and to multiply these constants by each other (four multiplications) in order to obtain the numerical quotient.
Consider a straightforward application of the equation (9), that is quadratic convergence, to this example. We would probably need to determine nine b's starting with b.sub.o =10.multidot.(1-89/100)=1.1 in order to attain at least the same accuracy. This implies that eight squaring operations, nine multiplications, and nine subtractions must be computed. Also consider the well known method used in the IBM System 360/91 Model. The method requires nine multiplications and four subtractions in this example. A comparison table is presented below where M and S denote multiplication (or squaring operation) and subtraction, respectively.
The calculation of a numerical inverse using the acceleration factor compares very well with the quadratic convergence method and the well known method.
When a divisor consists of many digits, the divisor can be split in two (or more) separated digit strings. Consider B=B.sub.1 D.sup.m +B.sub.2 where B.sub.1 and B.sub.2 are the upper half significant digits and the lower half significant digits, respectively and D.sup.m is a pseudoradix that indicates the splitting digit boundary between B.sub.1 and B.sub.2. Thus, we have the following equation: ##EQU7## where q.sub.b =B.sub.2 /B.sub.1 D.sup.m, and c.sub.o =1-q.sub.b and c.sub.r =1+q.sub.b.sup.2.spsp.4 or r=1,2,3, .sup.. . . . The second product term in the brace is the power series equivalent to 1/(1+q.sub.b) and the rest of the terms are a computation of 1/B.sub.1 which is the equation (10).
FIG. 5-a illustrates a digital circuitry diagram. Blocks 1-5 and 2-5 are sequential control units to perform a digital division (or to obtain a reciprocal of a constant). Dividend and divisor are stored in digital registers of blocks 8-5 and 3-5, respectively. Block 4-5 is a register holding a pseudoradix D.sup.n and the quantity q. The register of block 4-5 is used recursively during the determination process of acceleration constants a.sub.i for i=0,1,2, . . . ,j. Block 5-5 is the determination logic circuitry of a.sub.i that utilizes the subdivision table. The subdivision table could be realized by using Read Only Memory. After determining an appropriate acceleration constant by block 5-5, B is multiplied by the constant in order to obtain the next q at block 6-5. Simultaneously the constant is sent to the register of block 8-5 in order to multiply A by it. The results (the next q and the next pseudoradix) from block 6-5 are sent back to the register of block 4-5. The determination logic of block 5-5 is activated again for the content of the register block 4-5.
The functions of blocks 4-5, 5-5 and 6-5 have been charted in the process boxes 3-5, 5-4, 6-4, 7-4, 8-4, 3-4, 5-4, . . . of FIG. 4 recursively, until a successive q value belongs in the subdivision S.sub.D-1. When the q is in S.sub.D-1, block 7-5 is initiating the functions that are described by process boxes 9-4 through 15-4 in FIG. 4. These processes are the evaluation of the power series of 1/(1+q.sub.f). The constant b.sub.i determined in this block is transmitted to the register of block 8-5, in order to multiply A by it. When a desired accuracy of the quotient is accumulated in the register of block 8-5, the control unit signals the termination of operations to all the blocks.
When divisor digits are split in two subdivisors (refer equation (12)), the computation process of the power series of 1/(1+q.sub.b) must be continued after completing an evaluation of 1/B.sub.1. A digital circuitry diagram of the digit splitting case is illustrated in FIG. 5-b. The functions of the first eight blocks are the same as these eight blocks of FIG. 5-a except the divisor B is split in two B.sub.1 and B.sub.2 subdivisors. Another difference is the eight blocks worked for 1/B.sub.1 instead of 1/B. Registers of blocks 3-5 and 9-5 hold the upper half significant digits and the lower half significant digits of B, respectively. As soon as desired accurate digits of 1/B.sub.1 are obtained in the register of block 8-5, the control unit commands the computation of 1/(1+q.sub.b) at block 10-5 that is generating constants of c.sub.r for r=0,1,2, . . . . Each generated constant c.sub.r is sent to the register of block 8-5 to multiply A by it.
The control unit terminates the process when a desired accuracy is accumulated in the register holding A. Since the performance of block 10 is the same as the function of block 7, both the block functions could be realized with a physical digital circuitry.
The other aspect of the performing division is illustrated in FIGS. 6,7, and 8. FIG. 6 shows the successive multiplication to the dividend by acceleration constants and the iterative determination of the quantity of q.sub.i for i=0,1,2, .sup.. . . . When the control unit 1, comprising sequential circuitry, has received a division start signal after storing dividend A and divisor B into the dividend/quotient register 24, comprising a row of associated flipflops, and the divisor register 3, comprising another row of associated flipflops, respectively, the control unit resets the pseudoradix register 7 and the i counter 9, structuring circuitry with feedback loops depended not only on its present input but also on the inputs that may have been presented previously, with a predetermined pseudoradix D.sup.n and zeros, respectively. Then the control unit commands the negation logic 5 to get -D.sup.n and starts the addition 4 to obtain q from B and -D.sup.n by a digital adding circuitry 29. The resultant q.sub.o is stored in the q register 8. Next, the control unit initiates the determination logic of a.sub.i 14, comprising combinational logic circuits and Read Only Memories (ROM) of a table, that provides a control signal, s(D-1<a.sub.i), s(D-1=a.sub.i) or s(D-1<a.sub.i), and an acceleration constant a.sub.i as the output from this.
If a signal s(D-1>a.sub.i) is generated, then the signal is used to start i counter counting by performing the addition 10 through the OR logic 11 and the AND logic 12. Furthermore, if it is, the signal opens a control path of the OR logic 11 and the AND logic 13 to form the quantity D.sup.n +q.sub.i by the addition 16. Then the signal s(D-1>a.sub.i) also provides a path for a multiplication (a.sub.i +1) to the multiplicant (D.sup.n +q.sub.i) via the AND logic 17. After a completion of the above, the multiplication 18 furnishes the result (a.sub.i +1)(D.sup.n +q.sub.i) by a digital multiplier 28. The shifted by one digit in block 6 and negated result -D.sup.n+1 of D.sup.n and the resulted quantity (a.sub.i +1)(D.sup.n +q.sub.i) of the multiplication are added by the addition 20. When the digit shifting 22 is performed by one digit via the actuated commanding signal controlled by the AND logic 21 when detecting the signal s(D-1>a.sub.i). The consequent result q.sub.i+1 is fed back in the q register 8. Subsequently the control unit initiates the determination logic of a.sub.i 14 again to determine another control signal and another a.sub.i.
If a signal s(D-1=a.sub.i) is generated by the determination logic of a.sub.i 14 then the signal is used to actuate that the i counter is counted up by performing the addition 10 through a signal path of the OR logic 11 and the AND logic 12. Furthermore, the signal opens the OR logic 11 and the AND logic 13 in order to form the quantity (D.sup.n +q.sub.i) by the addition 16. Then the signal s(D-1=a.sub.i) also provides the path for a multiplication a.sub.i =D-1 to the multiplicant (D.sup.n +q.sub.i) via the AND logic 15. After a completion of these operations, the multiplication 18 provides the result a.sub.i (D.sup.n +q.sub.i)=(D-1) (D.sup.n +q.sub.i) by one digit shifting of the multiplicant and by subtracting the multiplicant from the shifted result. Also the shifted by one digit in block 6 and negated result -D.sup.n+1 of D.sup.n and the resulted quantity a.sub.i (D.sup.n +q.sub.i) of the multiplication are added by the addition 20. Then the digit shifting 22 is carried out by (n+1) digits via the actuated command signal by detecting the signal s(D-1=a.sub.i) in the AND logic 19. The consequent result q.sub.f is fed back in the q register 8. Subsequently the control unit shall receive the stop condition signal of the iterative process for q.sub.i evaluation through the delay logic 26 and the OR logic 27 by passing the signal s(D-1=a.sub.i).
Concurrently, the multiplier (a.sub.i +1) or a.sub.i, when a generated signal is s(D-1>a.sub.i) or s(D-1=a.sub.i) respectively by the determination logic of a.sub.i, is multiplied to the content A' of the dividend/quotient register 24 by the multiplication 25. Note that when a multiplier is a digit number D-1, the multiplication of the multiplicant (D.sup.n +q.sub.i) by the multiplier is performed by one digit shifting of the multiplicant and by subtracting the multiplicant from the shifted result. The result, A'(a.sub.i +1) or A'a.sub.i, of the multiplication is stored back into the dividend/quotient register. The delay logic 23 provides a time delay so that a digital multiplier can perform both the multiplications 18 and 25.
If the generated signal from the determination logic of a.sub.i 14 is a signal s(D-1>a.sub.i) then the iterative process for q.sub.i evaluation shall not be initiated due to detecting the stop condition signal from the OR logic 27. Intermediate results of additions 16 and 20, multiplication 18 and digit shifting 22 could be held in the divisor register 3, in the q register 8 or in the combined register of both the registers 3 and 8.
FIG. 7 depicts an internal logic of the determination logic of a.sub.i which consists of a subdivision table 3-7 comprising a set of memory registers; a selection matrix 4-7 comprising a set of AND logics; a comparator section 5-7 comprising one or more comparators structured to compare the content q.sub.i of the q register with the i.sup.th content and the (i+1).sup.th content of the subdivision table and to generate an output signal indicating a magnitude relationship between the q.sub.i, and the i.sup.th content and/or the (i+1).sup.th content such as s(i.sup.th content<q.sub.i), s((i+1).sup.th content>q.sub.i) or s((i+1).sup.th content>q.sub.i and i.sup.th content.gtoreq.q.sub.i); a digital counter 7-7 structured to count up the content whenever an ORed signal from the OR logic 10-7 of the signals, s(i.sup.th content<q.sub.i) and s((i+1).sup.th content>q.sub.i), appears; a shift register 9-7 comprised of a chain of flipflops to provide two selection bits for the selection matrix; a shift bit generator 8-7, comprised of sequential circuitry structuring to generate a train of pulse wave forms dictating a number of shifting bits D/(2 .sup..nu.+1) where .nu. is the content of the counter 7-7 and a signal directing shifts to the right or to the left depended on a signal, s(i.sup.th content<q.sub.i) or s((i+1).sup.th content>q.sub.i); an encoder 12-7 which performs convertion of the present selecting bit position in the shift register to an acceleration constant a.sub.i when a signal s((i+1).sup.th content<q.sub.i and i.sup.th content.gtoreq.q.sub.i) is generated by the comparator section 5-7; and a comparator 13-7 that generates a signal indicated a magnitude relationship between the acceleration constant a.sub.i and the digital constant D-1, where D is a base radix by a comparator 13-7.
The control unit 6-7 initializes the shift register to select the (D/2).sup.th content and the (D/2+1).sup.th content of the subdivision table, and the counter through reset lines when a division has started. Then the shift register bits open data paths of the designated contents of the table to the comparator section via the selection matrix. The comparator section generates a signal, that indicates a magnitude relationship between the quantity q.sub.i and the designated contents, such as s(i.sup.th content<q.sub.i), s((i+1).sup.th content>q.sub.i) or s((i+1).sup.th content<q.sub.i and i.sup.th content.gtoreq.q.sub.i).
When a signal s(i.sup.th content<q.sub.i) or s((i+1).sup.th content>q.sub.i) is generated, the counter is counted up by one via a signal from the OR logic 10-7. Also the generated signal is used in the shift bit generator to determine a shifting direction. Then the shift bit generator generates a train of pulses syncronized with clock pulses in order to dictate a number of shifting bits, (D/2.sup..nu.+1), in the shifting register. The shifted content of the shift register makes transferring paths of the new designated contents to the comparator section via appropriate AND logics of the selection matrix.
When a signal s((i+1).sup.th content<q.sub.i and i.sup.th content.gtoreq.q.sub.i) is generated, the bit position of the shift register is encoded to an acceleration constant a.sub.i by opening the AND logic 11-7. Finally a comparator generates a magnitude relationship signal between the a.sub.i and the constant D-1, such as s(D-1<a.sub.i); s(D-1=a.sub.i) or s(D-1>a.sub.i).
FIG. 8 illustrates the evaluation process of the power series after the quantities q.sub.f and A'=A.alpha.'=A(a.sub.o +1) . . . (a.sub.j-1 +1)(D-1) have been obtained in the pseudoradix/q register 2-8 and the dividend/quotient register 15-8, respectively. All combined blocks in FIG. 8 except the above two registers and the control unit 1-8 provides the function of the determination logic of b.sub.k in figure 5-8. The control unit arranges a combination of the pseudoradix register and the q register and initializes the k counter 4-8, structuring circuitry with feedback loops, with all zero bits. By the OR logic 5-8, all bits of the k counter are ORed. Since the initial output of the OR logic 5-8 is a zero, the AND logic 8-8, is opened for transferring the present content Q.sub.o =q.sub.f of the pseudoradix/q register by the negated signal by the negation 7-8. The quantity Q.sub.o is negated by the negation logic 11-8 then the addition 13-8 by utilizing the adding unit 16-8 is performed to produce the quantity 1-Q.sub.o. The content A' of the dividend/quotient register is multiplied by 1-Q.sub.o by utilizing the multiply unit 17-8 and the result is stored back in the dividend/quotient register.
Simultaneously, the control unit actuates the squaring operation by performing the multiplication 10 by using the multiply unit 17-8 in order to form Q.sub.k.sup.2 =Q.sub.k+1 then the squaring result is stored back in the pseudoradix/q register. At the same time the quantity Q.sub.k+1 is compared with a predetermined truncation error tolerance C, in general the C is less than the least significant digit (bit) of the divisor, by the comparator 12-8 comprising combinational logic circuitry. The comparator outputs a signal, s(Q.sub.k+1 .ltoreq.C) or s(Q.sub.k+1 >C).
If the signal s(Q.sub.k+1 >C) is generated then the k counter is counted up by one via the AND logic 6-8 and the addition 3-8. After a count up of the k counter, all bits of the k counter are ORed. The ORed signal opens the AND logic 9-8 then the addition 13-8 is performed to form the quantity 1+Q.sub.k. After the addition, the multiplication 14-8 is executed in order to produce a new quantity A'.multidot.(1+Q.sub.k) as a new content of the dividend/quotient register. Beside the operations of the addition 13-8 and the multiplication 14-8, the squaring operation 10-8 and the comparison by the comparator 12-8 are carried out parallelly. When the signal s(Q.sub.k+1 >C) is generated again, the same process of the addition 13-8 and the multiplication 14-8, and the squaring 10-8 and the comparison by the comparator 12-8 is repeated until a signal s(Q.sub.k+1 .ltoreq.C) is generated by the comparator. When a signal s(Q.sub.k+1 .ltoreq.C) is sent to the control unit, a division process has been completed.
This completes the description of the apparatus which performs a digital division process in a digital computation device. The described process of the apparatus can be realized with conventional digital pulse circuits or sequential switching circuits. The described process used in the apparatus described represents the best known use of the invention. The invention is particularly useful to find the reciprocal of a constant whose convergence rate of the power series of 1/B is close to one.