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.