Minimum Mean Running Time Function Generation Using Read-Only Memory

High-speed hardware function generation using table look-up in ROM and high-speed multiplication is considered. The reduced interval of interest, [a, b], is split into several large partitions. Within each large partition the functionf(x) is evaluated by piecewise polynomials of the same low degree whose coefficients are stored in ROM. Four basic architectures for such a scheme are considered. A nonlinear programming problem is solved for determining the optimal partitioning of the interval [a, b]. The objective function is the average number of multiplications, which takes into account the probability distribution r(x) = 1/(x ln β), for the mantissas of normalized floating-point numbers where β is the radix of the number system. The constraint is the available number of ROM words. The particular case of f(x) = 1/x and β = 2 is considered in detail and results are presented including an estimate of the number of ROM units required.