Correctly rounded constant integer division via multiply-add

摘要

Implementing integer division in hardware is expensive when compared to multiplication. In the case where the divisor is a constant, expensive integer division algorithms can be replaced by cheaper integer multiplications and additions. This paper presents the conditions for multiply-add schemes to perform correctly rounded unsigned invariant integer division under one of three rounding modes. We propose a heuristic to explore the space of implementations meeting the conditions we derive. Experiments show that an average speed up of 20% and area reduction of 50% can be achieved compared to existing correctly rounded approaches. Extension to two's complement numbers is also presented.