Fast Division Algorithm with a Small Lookup Table
[Asilomar Conference, Nov. 1999]
Patrick Hung, Hossam Fahmy, Oskar Mencer, Michael J. Flynn
Abstract
This paper presents a new division algorithm, which requires
two multiplication operations and a single lookup in a small
table.
The division algorithm takes two steps. The table lookup and
the first multiplication are processed concurrently in the
first step, and the second multiplication is executed in the
next step. This divider uses a single multiplier and a lookup
table with (2^m)(2m+1)bits to produce 2m-bit results that are
guaranteed correct to one ulp. By using a multiplier and a
12.5KB lookup table, the basic algorithm generates a 24-bit
result in two cycles.