On the Complexity of Table Lookup for Iterative Division

We show that except for a few special cases allowing smaller tables, the lookup table used for achieving k digits of convergence after the initial multiplication (or for obtaining the approximate reciprocal of the divisor with k − 1 digits of accuracy) in iterative division methods must have at least (r−-l) rk words of k + I digits, r being the number representation base. In the important special case of r = 2 with k ≥5, a 2k-word table with k-bit entries can be used, since the initial digit is always 1. It is also shown that a table of this optimal size can always be constructed. The special cases corresponding to r = 3 with k = 1, and r = 2 with k ≤ 4, allow smaller tables than the general case and are thus handled separately.