Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

6.3 CONVERGENCE (FUNCTIONAL ITERATION) ALGORITHMS

6.3.1 Introduction

Functional iteration algorithms represent division as a function. Numerical calculus techniques are used to solve, for example, Newton–Raphson equations or Taylor–MacLaurin expansions. These methods provide better than linear convergence, but the step complexity is somewhat more important than the one involved in digit recurrence algorithms. Since functional iteration algorithms use multiplication as a basic operation, the step complexity will mainly depend on the performance of the multiplication resources at hand ([FER1967], [FLY1970]). In practice, whenever the division process is integrated in a general-purpose arithmetic processor, one of the advantages comes from the availability of multiplication without additional hardware cost. It has been reported ([OBE1994], [FLY1997]) that, in typical floating-point applications, sharing multipliers does not significantly affect the overall performances of the arithmetic unit. In what follows, the divisor d is assumed to be a positive and normalized number such that, for example, 1/B ≤ d < 1. In most practical binary applications, IEEE normalization standards are used: 1 ≤ d < 2.

6.3.2 Newton–Raphson Iteration Technique

Coming back to the general division equation written

the theoretical exact quotient (r = 0) may be written

Actually, the Newton–Raphson method first ...