本文发表在 rolia.net 枫下论坛Integer Division
Of all the elemental operations, division is the most complicated and can consume the most resources (in either silicon, to implement the algorithm in hardware, or in time, to implement the algorithm in software). In many computer applications, division is less frequently used than addition, subtraction or multiplication. As a result, some microprocessors that are designed for digital signal processing (DSP) or embedded processor applications do not have a divide instruction (they also usually omit floating point support as well).
Recently I did some preliminary work on the design of the code generation phase for a compiler that would target a digital signal processor. This processor does not have a divide instruction and I had no idea how long it would take to implement the run time function needed to support integer division in software. The answer, it turns out, is "it depends". If all that is needed is a basic division function, and performance is not a major issue, the runtime function is fairly straight forward. A high performance division function is more complicated and would take more time to implement and test. The division function that is included here is of the former variety - a basic binary integer division function. I have also included some references on higher performance algorithms, but these are, as my professors used to say, left as exercises to the reader.
The integer division algorithm included here is a so called "radix two" division algorithm. One computation step is needed for each binary digit. There are radix 4, 8, 16 and even 256 algorithms, which are faster, but are more difficult to implement. The main reference I used in implementing my algorithm was Digital Computer Arithmetic by Cavanaugh. Several other references on high radix division are also listed below.
Digital Computer Arithmetic: Design and Implementation by Joseph J. F. Cavanaugh, McGraw-Hill, 1984. This is an extremely valuable reference work, but it may be out of print. This is one of the best surveys I've seen on digital computer arithmetic and hardware design.
Computer Organization and Design: The Hardware Software Interface by David A. Patterson and John L. Hennessy, Morgan Kaufmann Press. This book has a brief (compared to Cavanaugh) section on digitial arithmetic. It is an excellent book on computer architecture and should be read by anyone designing a digital signal processor.
An Analysis of Division Algorithms and Implementations by Stuart F. Oberman and Michael J. Flynn, Stanford University Computer Systems Laboratory, CSL-TR-95-675. This paper if available via ftp in postscript, compressed with zip (this file can be uncompressed with GNU unzip).
High-radix Division with Approximate Quotient-digit estimation by Peter Fenwick, Department of Computer Science, University of Auckland, New Zealand (p_fenwick@cs.auckland.ac.nz). This paper is available on the World Wide Web. Professor Fenwick's paper describes a high-radix division algorithm with some refinements of his own. The University of Paderborn site also has a pointer to what is supposed to be a postscript version of Prof. Fenwick's paper. However, when I tried to download it, all I got was garbage. The postscript can also be downloaded from the University of Auckland (ftp://ftp.cs.auckland.ac.nz/out/peter-f/division.ps).
My integer division algorithm is written in C++ and is included below. The file can be downloaded here.
Division is the process of repeated subtraction. Like the long division we learned in grade school, a binary division algorithm works from the high order digits to the low order digits and generates a quotient (division result) with each step. The division algorithm is divided into two steps:
Shift the upper bits of the dividend (the number we are dividing into) into the remainder.
Subtract the divisor from the value in the remainder. The high order bit of the result become a bit of the quotient (division result).
/*
Copyright stuff
Use of this program, for any purpose, is granted the author,
Ian Kaplan, as long as this copyright notice is included in
the source code or any source code derived from this program.
The user assumes all responsibility for using this code.
Ian Kaplan, October 1996
*/
void unsigned_divide(unsigned int dividend,
unsigned int divisor,
unsigned int "ient,
unsigned int &remainder )
{
unsigned int t, num_bits;
unsigned int q, bit, d;
int i;
remainder = 0;
quotient = 0;
if (divisor == 0)
return;
if (divisor > dividend) {
remainder = dividend;
return;
}
if (divisor == dividend) {
quotient = 1;
return;
}
num_bits = 32;
while (remainder < divisor) {
bit = (dividend & 0x80000000) >> 31;
remainder = (remainder << 1) | bit;
d = dividend;
dividend = dividend << 1;
num_bits--;
}
/* The loop, above, always goes one iteration too far.
To avoid inserting an "if" statement inside the loop
the last iteration is simply reversed. */
dividend = d;
remainder = remainder >> 1;
num_bits++;
for (i = 0; i < num_bits; i++) {
bit = (dividend & 0x80000000) >> 31;
remainder = (remainder << 1) | bit;
t = remainder - divisor;
q = !((t & 0x80000000) >> 31);
dividend = dividend << 1;
quotient = (quotient << 1) | q;
if (q) {
remainder = t;
}
}
} /* unsigned_divide */
#define ABS(x) ((x) < 0 ? -(x) : (x))
void signed_divide(int dividend,
int divisor,
int "ient,
int &remainder )
{
unsigned int dend, dor;
unsigned int q, r;
dend = ABS(dividend);
dor = ABS(divisor);
unsigned_divide( dend, dor, q, r );
/* the sign of the remainder is the same as the sign of the dividend
and the quotient is negated if the signs of the operands are
opposite */
quotient = q;
if (dividend < 0) {
remainder = -r;
if (divisor > 0)
quotient = -q;
}
else { /* positive dividend */
remainder = r;
if (divisor < 0)
quotient = -q;
}
} /* signed_divide */更多精彩文章及讨论，请光临枫下论坛 rolia.net
Of all the elemental operations, division is the most complicated and can consume the most resources (in either silicon, to implement the algorithm in hardware, or in time, to implement the algorithm in software). In many computer applications, division is less frequently used than addition, subtraction or multiplication. As a result, some microprocessors that are designed for digital signal processing (DSP) or embedded processor applications do not have a divide instruction (they also usually omit floating point support as well).
Recently I did some preliminary work on the design of the code generation phase for a compiler that would target a digital signal processor. This processor does not have a divide instruction and I had no idea how long it would take to implement the run time function needed to support integer division in software. The answer, it turns out, is "it depends". If all that is needed is a basic division function, and performance is not a major issue, the runtime function is fairly straight forward. A high performance division function is more complicated and would take more time to implement and test. The division function that is included here is of the former variety - a basic binary integer division function. I have also included some references on higher performance algorithms, but these are, as my professors used to say, left as exercises to the reader.
The integer division algorithm included here is a so called "radix two" division algorithm. One computation step is needed for each binary digit. There are radix 4, 8, 16 and even 256 algorithms, which are faster, but are more difficult to implement. The main reference I used in implementing my algorithm was Digital Computer Arithmetic by Cavanaugh. Several other references on high radix division are also listed below.
Digital Computer Arithmetic: Design and Implementation by Joseph J. F. Cavanaugh, McGraw-Hill, 1984. This is an extremely valuable reference work, but it may be out of print. This is one of the best surveys I've seen on digital computer arithmetic and hardware design.
Computer Organization and Design: The Hardware Software Interface by David A. Patterson and John L. Hennessy, Morgan Kaufmann Press. This book has a brief (compared to Cavanaugh) section on digitial arithmetic. It is an excellent book on computer architecture and should be read by anyone designing a digital signal processor.
An Analysis of Division Algorithms and Implementations by Stuart F. Oberman and Michael J. Flynn, Stanford University Computer Systems Laboratory, CSL-TR-95-675. This paper if available via ftp in postscript, compressed with zip (this file can be uncompressed with GNU unzip).
High-radix Division with Approximate Quotient-digit estimation by Peter Fenwick, Department of Computer Science, University of Auckland, New Zealand (p_fenwick@cs.auckland.ac.nz). This paper is available on the World Wide Web. Professor Fenwick's paper describes a high-radix division algorithm with some refinements of his own. The University of Paderborn site also has a pointer to what is supposed to be a postscript version of Prof. Fenwick's paper. However, when I tried to download it, all I got was garbage. The postscript can also be downloaded from the University of Auckland (ftp://ftp.cs.auckland.ac.nz/out/peter-f/division.ps).
My integer division algorithm is written in C++ and is included below. The file can be downloaded here.
Division is the process of repeated subtraction. Like the long division we learned in grade school, a binary division algorithm works from the high order digits to the low order digits and generates a quotient (division result) with each step. The division algorithm is divided into two steps:
Shift the upper bits of the dividend (the number we are dividing into) into the remainder.
Subtract the divisor from the value in the remainder. The high order bit of the result become a bit of the quotient (division result).
/*
Copyright stuff
Use of this program, for any purpose, is granted the author,
Ian Kaplan, as long as this copyright notice is included in
the source code or any source code derived from this program.
The user assumes all responsibility for using this code.
Ian Kaplan, October 1996
*/
void unsigned_divide(unsigned int dividend,
unsigned int divisor,
unsigned int "ient,
unsigned int &remainder )
{
unsigned int t, num_bits;
unsigned int q, bit, d;
int i;
remainder = 0;
quotient = 0;
if (divisor == 0)
return;
if (divisor > dividend) {
remainder = dividend;
return;
}
if (divisor == dividend) {
quotient = 1;
return;
}
num_bits = 32;
while (remainder < divisor) {
bit = (dividend & 0x80000000) >> 31;
remainder = (remainder << 1) | bit;
d = dividend;
dividend = dividend << 1;
num_bits--;
}
/* The loop, above, always goes one iteration too far.
To avoid inserting an "if" statement inside the loop
the last iteration is simply reversed. */
dividend = d;
remainder = remainder >> 1;
num_bits++;
for (i = 0; i < num_bits; i++) {
bit = (dividend & 0x80000000) >> 31;
remainder = (remainder << 1) | bit;
t = remainder - divisor;
q = !((t & 0x80000000) >> 31);
dividend = dividend << 1;
quotient = (quotient << 1) | q;
if (q) {
remainder = t;
}
}
} /* unsigned_divide */
#define ABS(x) ((x) < 0 ? -(x) : (x))
void signed_divide(int dividend,
int divisor,
int "ient,
int &remainder )
{
unsigned int dend, dor;
unsigned int q, r;
dend = ABS(dividend);
dor = ABS(divisor);
unsigned_divide( dend, dor, q, r );
/* the sign of the remainder is the same as the sign of the dividend
and the quotient is negated if the signs of the operands are
opposite */
quotient = q;
if (dividend < 0) {
remainder = -r;
if (divisor > 0)
quotient = -q;
}
else { /* positive dividend */
remainder = r;
if (divisor < 0)
quotient = -q;
}
} /* signed_divide */更多精彩文章及讨论，请光临枫下论坛 rolia.net