Division and conquer

  • W. de Koning

Student thesis: Master


Integer division is an important arithmetic operation on microprocessors. To derive integer division algorithms we present an unconvential approach: a derivation technique in a calculational style, that guarantees that the derived algorithms are correct. Four different algorithms are derived using this method: restoring division, non-restoring divsion, radix-4 division and division by multiplication. We translate these to descriptions into combinatorial circuits, expressed in Verilog code. Then the circuits are compiled on a Spartan-3 Generation FPGA. At the end, we compare the propagation delays and area requirements for these circuits. We show that the division by multiplication is much faster than the other methods, however it only works for 18 bit integers.
Date of Award31 Dec 2013
Original languageEnglish
SupervisorR.R. Hoogerwoord (Supervisor 1)

Cite this