Experimental Software and Hardware Evaluation of Ad-Hoc Constant Division Routines

Dividing by a constant is an operation that is often needed in algorithms, be they implemented in software or in hardware. Given the fact that general purpose processors have had fast hardware multipliers for decades, the solution for software is to multiply by a compile time computed reciprocal and perform some adjustment. However, for hardware implementations, in particular with relatively small and exotic bit sizes, shift-and-add solutions might be worth looking at. In this paper, we report our study on implementing constant unsigned division based on Li's work. We found that a few of his algorithms are wrong and propose corrections that need a bit more computations. For software, we show that the approach can be useful only for low-end microcontrollers. For hardware, our FPGA and ASIC synthesis outline that it has good scalability, although being not very efficient for small dividends. As delay and area are very dependent on the value of the divisors, this approach appears as yet another possibility to choose from when looking on how to divide by a given constant.