2024 ASEE Annual Conference & Exposition

Of the four arithmetic functions, Division is the most complex. When we learn arithmetic in
school it is the last of the arithmetic operations taught after first learning addition, subtraction,
and multiplication. This is the case, again, since division is the most complex of the four
operations to learn, and similarly, from a digital implementation standpoint, division is the most
complex. In undergraduate digital system design courses, we typically teach addition, subtraction,
and maybe multiplication, but division is treated as a more complex algorithm that is rarely
touched upon. We believe this is the case because of the complexity of division and its general
lack of use in most algorithms. From our exploration of where division is used, it appears in the
Diffie-Helmann algorithm and pseudo-random number generators. We hypothesize the second
reason division is not typically explored in undergraduate education is that the complexity of
division implementation is beyond most instructors and there are few tools to help us all
understand division.
In this work, we investigate the efficiency of different division algorithms as the bit width of the
division increases, specifically for unsigned integer division. Our target architecture is a Field
Programmable Gate-Array (FPGA) where we measure each divider’s area (measured by Logic
Elements of the FPGA) and the speed of division. We investigate non-restoring division, Radix-2
SRT division, Radix-4 SRT division, and Goldschmidt division at widths ranging from 8 bits to
1024 bits. Each of these dividers at each bit-width is tested for functionality and is measured
based on speed (a combination of critical path and number of clock cycles to complete) and area
(number of logic elements (LEs) needed for the divider). Our results provide a general trend for
the area and speed for these division algorithms as the width of the division grows for FPGAs,
and our tool is open source so that others can implement these dividers with detailed examples of
their stepwise operation so that educationally we can develop an understanding of division
algorithms.