O'Reilly logo

Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems by Gustavo D. Sutter, Gery J.A. Bioul, Jean-Pierre Deschamps

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

6

ARITHMETIC OPERATIONS: DIVISION

Integer or finite length fractional numbers can be multiplied exactly, whenever sufficient length is allowed for the result. Division doesn't share this feature. As a matter of fact, division generally does not provide a finite length result. The accuracy must be defined beforehand by setting the unit in the least significant position (ulp) of the result. The number of algorithmic cycles will therefore depend on the desired accuracy, not on the operand length.

Digit recurrence algorithms represent the most common class of division techniques: a single quotient-digit is produced at each computation step. The classic pencil and paper method belongs to this class. The time complexity is thus a linear function of the desired number of quotient-digits. SRT division ([SWE1957], [ROB1958], [TOC1958]) has been widely used in computer applications. The digit recurrence algorithmic step mainly consists in an estimation of the greatest multiple of the divisor to be subtracted from the remainder.

Functional iteration is another class of algorithms. These algorithms use function-solving techniques to converge, from an initial estimation, toward the quotient with the required precision. The main feature of this method rests on the faster than linear convergence, typically quadratic. The main drawbacks are the step complexity and the need for additional computations to provide the final remainder, thus increasing the rounding complexity. The most used functional ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required