Software Integer Division

Tom Rodeheffer

MSR-TR-2008-141 |

Early computers omitted instructions for integer multiplication and division, requiring these operations to be synthesized in software. Even some modern RISC and DSP architectures are deficient in the case of division. Therefore software methods for performing integer division continue to be of interest. We consider typical architectures based on two’s complement binary arithmetic and present various methods of performing single precision unsigned integer division in software. In addition to methods based on the standard test-subtract-shift approach, we present a method and variants based on a novel adaptation of the Newton-Raphson recurrence to the domain of unsigned integers.