Note: Descriptions are shown in the official language in which they were submitted.
CA 02453712 2003-12-17
METHOD OF PERFORMING BINARY INTEGER DIVISION
Field of Invention
The present invention relates to the field of mathematical processing in
computer systems
and more particularly to methods of performing binary integer division.
Back round
The execution of binary integer division in many computer systems requires
considerably
more processing cycles than other operations such as binary integer
multiplication. As a result,
methods have been developed for computing binary integer division by using low-
cost operations,
in terms of processor cycles and execution time required, such as shift,
multiply and add rather than
hardware based integer division. Binary integer division methods are used in
compilers for
generating program code used to evaluate integer divisions, for example, in
programming loops with
compile-time known loop-invariant divisors (i.e., the divisor is the same for
each division).
Programs resulting from implementation of these methods typically run faster
than programs using
the native hardware binary integer division, thus improving execution time and
overall performance.
However, when the divisor of a binary integer division operation used in a
program loop is
Ioop-invariant, but its value is not known at compile time, changes to
traditional processing methods
are required.
CA9-2003-0101 1
CA 02453712 2003-12-17
Surnmary of Invention
In accordance with one aspect of the present invention, there is provided a
method of
performing binary integer division to obtain a final quotient and a final
remainder from an N-bit
denominator d and a 2N-bit numerator comprising a binary integer component n
of N-bits and a zero
component of N-bits of binary 0's, the method including: (a) delivering the
denominator and
intermediate remainders to a computer system operable to determine quotient
values; (b) delivering
the denominator and quotient values to a computer system operable to determine
the intermediate
remainders; wherein the quotient values q(i) and the intermediate remainders
r(i) are generated by
performing the following assignments iteratively (i=i+1) until the binary 0's
of the zero component
of the numerator are exhausted, in which r(0) is initially set equal to n and
q(0) is initially set equal
to r(0)[/]d; q(i)=r(i)[/]d padded to the left with binary 0's equal to N less
the number of bits in the
intermediate remainder r(i); and r(i+1)=r(i)[-](q(i)[*]d) padded to the right
with binary 0's equal to
N less the number of bits in the intermediate remainder r(i) removed from the
zero component of the
numerator, wherein the final quotient is represented by a concatenation of the
quotient values q(i)
and the final remainder is represented by the value of r(i).
In accordance with another aspect of the present invention, there is provided
a method of
performing binary integer division to obtain a final quotient and a final
remainder from an N-bit
denominator d and a 2N-bit numerator comprising a binary integer component n
of N-bits and a zero
component of N-bits of binary 0's, the method including: (a) calculating a
quotient value q(i) as
r(i)[/]d, wherein r(i) is an intermediate remainder and r(0)=n and
q(0)=r(0)[/]d; (6) padding the
quotient value q(i) to the left with binary 0's equal to N less the number of
bits in the intermediate
Ct~9-2003-0101 2
CA 02453712 2003-12-17
remainder r(i); (c) calculating a subsequent intermediate remainder r(i+1) as
r(i)[-](q(i)[*]d); (d)
padding the subsequent intermediate remainder r(i+1 ) to the right with binary
0's equal to N less the
number of bits in the intermediate remainder r(i) removed from tale zero
component of the
numerator; (e) repeating steps (a)-(d) until the binary 0's of the zero
component of the numerator are
exhausted; (f) concatenating the quotient values q(i) obtained from step (a)
to form the final quotient;
and (g) assigning the final remainder as the last subsequent intermediate
remainder r(i+1 ) determined
at step (c).
In accordance with yet another aspect of the present invention, there is
provided a computer-
readable medium having computer executable instructions for performing binary
integer division to
obtain a anal quotient and a final remainder from an N-bit denominator d and a
2N-bit numerator
comprising a binary integer component n of N-bits and a zero component of N-
bits of binary 0's, the
instructions including the steps of: (a) delivering the denominator and
intermediate remainders to
a computer system operable to determine quotient values; and (b) delivering
the denominator and
quotient values to a computer system operable to determine the intermediate
remainders; whereby
the quotient values q(i) and the intermediate remainders r(i) are generated by
performing the
following assignments iteratively (i=i+1) until the binary 0's of the zero
component of the numerator
are exhausted, in which r(0) is initially set equal to n and q(0) is initially
set equal to r(0)[/]d:
q(i)=r(i)[/]d padded to the left with binary 0's equal to N less the number of
bits in the intermediate
remainder r(i); and r(i+1)=r(i)[-](q(i)[*]d) padded to the right with binary
0's equal to N less the
number of bits in the intermediate remainder r(i) removed from the zero
component of the
CA9-2003-0101 3
CA 02453712 2003-12-17
numerator, wherein the final quotient is represented by a concatenation of the
quotient values q(i)
and the final remainder is represented by the value of r(i).
In accordance with still yet another aspect of the present invention, there is
provided a
computer program product in a computer usable medium, for performing binary
integer division to
obtain a final quotient and a final remainder from an N-bit denominator d and
a 2N-bit numerator
comprising a binary integer component n of N-bits and a zero component of N-
bits of binary 0's, the
product having instructions for performing the steps of: (a) calculating a
quotient value q(i) as
r(i)[/]d, wherein r(i) is an intermediate remainder and r(0)=n and
q(0)=r(0)[/]d; (b) padding the
quotient value q(i) to the left with binary 0's equal to N less the number of
bits in the intermediate
remainder r(i); (c) calculating a subsequent intermediate remainder r(i+1) as
r(i)[-](q(i)[*]d); (d)
padding the subsequent intermediate remainder r(i+1) to the right with binary
0's equal to N less the
number of bits in the intermediate remainder r(i) removed from the zero
component of the
numerator; (e) repeating steps (a)-(d) until the binary 0's of the zero
component of the numerator are
exhausted; (f) concatenating the quotient values q(i) obtained from step (a)
to form the final quotient;
and (g) assigning the final remainder as the last subsequent intermediate
remainder r(i+1 ) determined
at step (c).
Brief Description of Drawings
Fig. 1 is an illustrative representation of binary integer division shown in a
long division
format according to an embodiment of the present invention;
CA9-2003-0101 q.
CA 02453712 2003-12-17
Fig. 2A to 2C are illustrative examples of binary integer division in long
division formats
according to an embodiment of the present invention;
Figs. 3 and 4 are flow diagrams of a binary integer division method according
to exemplary
embodiments of the present invention; and
Fig. 5 is a diagram of a computer system useful in implementing the
embodiments of the
invention.
Detailed Descriution
In the field of binary integer division, the computation of a "floor" (2N * n
/d) is typically
involved in the division process, where N is the number ofbits in a computer
system's native integer
arithmetic, (e.g. 32-bit, 64-bit, etc.) and numerator (or dividend) n and
denominator (or divisor) d
are N-bit integers. The floor (2N * n /d) cannot generally be evaluated
directly using the computer
system's multiply and divide instructions, since the numerator (2~ * n) is
generally a 2N-bit integer.
In these situations (termed 2N-bit/ N-bit division) performance can be
compromised since a general
2N-bit numerator is assumed and the calculations are implemented in terms of
single-bit operations,
rather than N-bit operations.
An illustrative representation (in long division format) of binary integer
division 100
according to an embodiment of the present invention is shown in Fig. 1. A
numerator (or dividend)
101 is a 2N-bit binary integer comprised of a N-bit binary integer component n
102 and a zero
component 104 also of N-bits in length (i.e., an N-bit string of binary 0's).
A denominator (or
CA9-2003-0101 5
CA 02453712 2003-12-17
divisor) d 106 of the binary integer division 100 is also N-bits in length.
The binary integer division
100 generates a final quotient Q I0~ and a final remainder REM 1 I 1. The
final quotient Q 108 is
obtained from a plurality of quotient values q(i) in a manner described below.
The final remainder
REM 111, is determined by the final value of remainder r(i) in a manner
described below. The
following mathematical notations are used to represent N-bit binary integer
arithmetic operations:
addition [+], subtraction [-], multiplication [*], division [/], bitwise or
[OR], and bit left shift [«].
As a general overview, the first partial remainder r(0) is initially assigned
to be equal to the
value of the numerator component n 102 (r(0)=n). The first quotiient value
q(0) is initially assigned
a value calculated by dividing the first partial remainder r(0) by the
denominator d 106 (q(0) _
r(0)[/]d=n[/]d). The first quotient value q(0) becomes the leftmost part of
the final quotient Q 108
when q(i) is non-zero (the handling of zero quotient values will be described
below). The next
partial remainder r(i+1) (shown as expression 112 in Fig. 1) is determined by
subtracting from the
previous partial remainder r(i) a product of the quotient value q(i) and the
denominator d 106
(r(i+1)=r(i)[-] (q(i) [*] d). Therefore, partial remainder r(1) is equal to
r(0)[-](q(0)[*]d)= n[-](n[/]d
[*] d).
At this stage, the number of bits (rem_bits) in the calculated partial
remainder r(i) is
considered for subsequent "padding" operations of the partial remainders and
quotient values. In
particular, the partial remainders r(i) are padded (i.e., binary zeros are
appended) such that the
number of bits in the partial remainder r(i) is maintained at N-bits in length
(i.e., N-rem_bits binary
0's are appended to the r(i)). The padding of binary zeros to the partial
remainder is notionally
equivalent to "removing" or "bringing down" (shown illustratively with the
dotted arrow from
CA9-2003-0101 6
CA 02453712 2003-12-17
component 104 in Fig. 1 ) binary 0°s from the binary zero component 104
of the numerator 101. The
binary integer division 100 is considered complete when all of the binary 0's
in the zero component
104 are "exhausted" (i.e. all 0's have been removed or brought down) and the
final remainder is
computed. Further, at each stage {of determining r(i) and q(i)), the quotient
values are also
"padded" to the left (i.e., N-rem_bits binary 0's are inserted to the front of
the calculated q(i)), which
is ultimately concatenated with the other quotient values to form the final
quotient Q 108. Details
of padding partial remainders and quotient values are provided below in
conjunction with the
description of a specific division example.
Figs. 2A, 2B and 2C represent an illustrative example binary integer division
according to
an embodiment of the present invention where N=4, the numerator, (2N*n), is n
(1101) followed by
N zero bits (0000) (24* 13=208 in decimal or 11010000 in binary). The
denominator d is 1100 in
binary (12 in decimal). The initial partial remainder r(0) is set equal to n,
r(0) = n. The first partial
quotient q(0) is calculated by dividing r(0) by the denominator (i.e.,
q{0)=r(0)[/]d=1101 [/] 1100=1).
Binary 1 {i.e., q(0) becomes the first part of the quotient Q. The remainder
r(1) is calculated where
IS r(I) = r(0) - q(0) [*] d therefore r(1)=I 101-1 [*] I I00=1. The
rennainder, r(1), is then padded to the
right with the appropriate number of zeros removed from the zero component, so
that the remainder
r(1) is still of N-bits in length (N-rem_bits = 4 -1 = 3) such that r(1) =
1000. A new partial quotient
q(1) is calculated, q(1)=r(1)[/]d=1000[/ ] 1 I00 which is equal to G. Since
q(1) is equal to 0, the sub-
process is executed using r(1)=1000 and d=1 I00 to calculate a new partial
quotient and remainder.
The sub-process continues the division operation by using (N+1)-bit/N-bit
division to calculate a
new quotient and remainder.
CA9-2003-0101
CA 02453712 2003-12-17
Now referring to Fig. 2C, the computation of (N+1 )-bit/N-bit division is
executed by bringing
down the remaining 0 of the zero component and padding it to r(1), so that it
now equals 10000 (N+1
bits). The remainder r(1) is used as the numerator value in the (N+1)-bit/N-
bit division operation.
Since N+1-bit division is not directly possible on N-bit hardware, the sub-
process is used. Let
n'=1000 be the leftmost N bits of r(1). The sub-process then computes
r(1)/d=2*n'/d as follows.
A working value, d2, is calculated by dividing the denominator, d, by two, so
that
d2=d[/]2=1100[/] 10=110 (binary) =1212=6 (decimal). The least significant bit
of d is checked.
Since this bit is 0, d is divisible by two. In this case, the new partial
quotient q(1) is recalculated by
dividing the numerator n' by the working value d2 (q( 1)= n'/d2=1000[/]
110=1). Since the value of
q(1) does not equal zero, a new remainder r(2) is calculated by the numerator
n', minus working
value d2, multiplied by two(r(2)=2(n[-]d2)=10[*](1000[-] 110)=100). Therefore
the new remainder
r(2) is equal to 100. The partial quotient q(1) is padded to the left with an
equal number of zeros
removed from the zero component prior to the (N+1)-bitJN-bit division (3) such
that q(1) is equal
to 0001. The value of quotient Q is the concatenation of q(0) =l and q
(1)=0001 therefore
Q=10001(binary) = 17 (decimal). The last remainder value r(2) is the final
remainder REM=100
(binary) = 4 (decimal).
Figs. 3 and 4 represent flow diagrams illustrating a method (200 and 300) of
performing
binary integer division according t~ an exemplary embodiment of the present
invention. In the
illustrative example shown in Figs. 2A, 2B and 2C, the calculation of the
final quotient was
performed by concatenation of the values of q(i) and the final rez~ainder as
determined by the last
value of r(i). In reference to Figs. 3 and 4, the quotient Q is computed by
concatenation of the value
CA9-2003-0101 8
CA 02453712 2003-12-17
of the partial quotient b, and remainder REM is calculated directly with
binary operations. At step
202 working values of the process 200/300 are initialized, REM = 0, Q = 0,
nzeros = Q and z = N,
where REM is the remainder, Q is the quotient, nzeros is a counter for the
number of zeros brought
down during the last operation from the zero component, and ~: is the number
of zeros remaining
to be brought down from the zero component. At step 204, it is determined
whether remainder is
greater than or equal to denominator d (REM >_ d) or if there are no more
zeros to be brought down
from the zero component, (z = 0).
If step 204 is true, (i.e. REM >_ d and z =0) at step 206 the partial
quotient, is set equal to the
remainder divided by the denominator ( b = REM[/]d). The quotient is then
shifted to the left by the
number of zeros brought down from the zero component during the last operation
(Q shifted left by
nzeros). The partial quotient is inserted into the quotient Q by a bitwise OR
of quotient and partial
quotient (Q = Q[~R]b). At step 210 the zero status is once again determined.
If there are no more
remaining zeros to be brought down (z = 0), then the final result of quotient
(Q) and remainder
(REM) are displayed at step 212 terminating the process. If there are zeros
remaining to be brought
down (z ~0), at step 211 the remainder is set equal to the remainder minus the
partial quotient
multiplied by denominator (REM=REM[-](b[*]d). The process then continues at
step 204.
If step 204 is false, (i.e. REM < d or z r0), there are still zeros to be
brought down however
(N+1)-bitlN-bit division is required so that progress may continue: at step
208. Now referring to Fig.
4, a sub-process 300 calculates the (N+1)-bit/N-bit division 2*n'/d, where the
current value of REM
is used as the numerator n' in the sub-process 300 (n'=REM). At step 302, a
working value, d2, is
CA9-2003-0101 g
CA 02453712 2003-12-17
assigned equal to the denominator divided by two (d2= d [/] 2) which can be
performed by a right
shift operation of the denominator in binary arithmetic.
At step 304 it is then determined if the denominator is divisible by two by
determining if the
least significant bit of the denominator is zero. If the denominator is
divisible by two, then the
working value is exact. At step 306, since there is no remainder the partial
quotient is set to equal
to the numerator divided by the working value (b= n' [/] d2).
At step 308, if the partial quotient is equal to 0 (b = 0), then the remainder
is set equal the
numerator multiplied by two (IZEM = 2 [*] n') at step 312. If the; partial
quotient is not equal to 0
b # 0) at step 308, then the remainder is set to the numerator minus the
working value and then
multiplied by two ( REM = 2 [*] ( n' [-] d2 ) at step 314.
If the denominator is not divisible by two at step 304, therefore d/2 is not
an integer, it is then
determined whether the numerator n' is less than or equal to the working value
d2 (n' <= d2) at step
310.
If the numerator n' is less than or equal to the working value (n' < =d2) at
step 310, then the
numerator is less than the denominator divided by two ( n'< d/2) therefore the
partial quotient is set
equal to zero (b = 0) and the remainder is set equal to the numerator
multiplied by two (REM = 2
(*) n') at step 316. However, if n' is greater than the working value ( n'>
d2) at step 310, the
numerator is greater than or equal to the working value plu s one, which is
greater than the
denominator divided by two ( n' >_ d2 +1 > d/2 ), so that the numerator
multiplied by two, divided
by the denominator, is greater than one ( 2*n'/ d > 1) and partial quotient is
equal to one (b = 1).
CA9-2003-0101 10
CA 02453712 2003-12-17
Therefore at step 318, the remainder is then equal to the product of the
numerator multiplied by two,
minus the denominator which is equal to the numerator minus working value
multiplied by two
REM = 2*n'-d = 2* (n - d/2)). However, since the denominator divided by two (
d/2 ) is not an
integer, the denominator divided by two is equal to the working value plus one-
half ( d/2 = d2 + 1/2),
so that the remainder is equal to the product of the numerator minus the
working value minus one-
half multiplied by two, which is also equal to the numerator minus the working
value multiplied by
two minus one (REM = 2 * (n - d2 -1/2) = 2 * (n - d2) -1=2 [*] (n' [-] d2) [-]
1). The new values of
the partial quotient and the remainder are returned to the main process to
continue the division.
Referring again to Fig. 3, at step 214, the number of zeros last brought down
is incremented
by one (nzeros = nzeros[+] 1) and the number of zeros remaining is decreased
by one ( z = z [-] 1) as
the sub-process implicitly brings down one zero. The quotient is shifted left
by the number of zeros
last brought down to make room for the partial quotient (q = q + nzeros). The
partial quotient is then
inserted into the quotient by a bitwise OR operation (Q = Q [OR] b). The
number of leading zeros
in the remainder indicates the number of bits by which the process has
progressed. The number of
zeros last brought down is then set equal to the minimum of the number of
leading zeros in the
remainder, rem_bits, and the zeros remaining to be brought down (nzeros = MIN
(rem_bits, z)). The
remainder is shifted left by number of remaining zeros last brought down (REM
=REM [«] nzeros)
and the number of zeros remaining to be brought down is decrernented by the
number of zeros last
brought down ( z = z[-) nzeros ). The process then restarts at step 204 until
the final value for Q and
REM are displayed at step 212.
CA9-2003-0101 11
CA 02453712 2003-12-17
An example of the exemplary embodiment of binary integer division described in
Fig. 3 and
Fig.4 implemented in C programming language is provided below. The TNDIV
function
implements the main process 200 while N2DIV implements the sub-process 300.
TNDIV (n,d) function
#define MIN(x,y) (x<y?x:y}
extern unsigned int CNTLZ (UNSIGNED);
/* Returns number of leading zeros */
extern UNSIGNED N2DIV (UNSIGNED, UNSIGNED, UNSIG1VED *);
/* See next process */
UNSIGNED TNDIV (UNSIGNED n, UNSIGNED d)
/* Returns floor (2**N * n / d), where n < d and N is the word length. */
UNSIGNED rem, b, q, z, rem_bits, b_bits, nzeros, rem2;
rem = n; /* Current remainder */
q = 0; /* Quotient so far */
z = N; /* Number of zeros remaining to be brought down. */
nzeros = 0; /* Number of zeros last brought down. */
while ( 1 ) {
if ((rem >= d) I, (z = = 0))
/*Either there are no more zeros to be brought down, in which case this is the
last
iteration, or we can make progress using N-bit/N-bit division. */
/* Do N-bit divide. */
b = rem/d;
/* Make room for partial quotient and insert it, */
q «= nzeros;
q I= b;
/* Done if no more zeros to bring down. */
if (z == 0) break;
/* Compute new remainder */
rem -= d*b;
CA9-2003-0101 12
CA 02453712 2003-12-17
else {
I* There are still zeros to be brought down, and we need to use (N+1)-bit/N-
bit
division to make progress. */
/* Do (N+1)-bitlN-bit divide of 2*rem/d. This implicitly brings down one more
zero. */
b = N2DIV (rem, d, &rem);
nzeros += l;
z -= l;
/* Make room for partial quotient and insert it. */
q «= nzeros;
q ~=b~
/* Determine number of leading zeros in remainder, which is the number of bits
we have
progressed by. */
rem bits = CNTLZ (rem)
/* Determine number of zeros to bring down and bring there down. */
nzeros = MIN (rem bits, z);
rem «= nzeros;
z -= nzeros;
return q;
N2DIV functi~n
UNSIGNED N2DIV (UNSIGNED n, UNSIGNED d, UNSIGNED *r)
/* Returns floor (2 * n / d) . Sets r to remainder. Must have n < d. */
{
UNSIGNED d2, q;
d2 = d » l; /* d2 = dl2 */
if (!(d & 1)) {
/* d is divisible by 2, so d2 is exact */
q=n/d2;
if (q = = 0) {
*r=2*n;
CA9-2003-0101 13
CA 02453712 2003-12-17
else {
*r =2 ~ (n - d2);
else {
/* d is not divisible by 2 */
if (n <= d2) {
q=0;
*r = 2 * n;
}
else {
q = 1;
~r = 2 ~' (n - d2) -1;
}
return q;
{
The hardware elements of a computer system used to implement the present
invention are shown
in Fig. 5. A central processing unit (CPU) 400 provides main processing
functionality. A memory
410 is coupled to CPU 400 for providing operational storage of programs and
data. Memory 410
may comprise, for example, random. access memory (RAM) or read only memory
(R~M). l~Ton-
volatile storage of, for example, data files and programs is provided by a
storage 420 that may
comprise, for example, disk storage. Both memory 410 and storage 420 comprise
a computer useable
medium that may store computer program products in the form of computer
readable program code.
User input and output is provided by an inputJoutput (I/O) facility 430 The
I/O facility 430 may
include, for example, a graphical display, a mouse and/or a keyboard.
CA9-2003-O 101 14
