Symmetric bipartite tables for accurate function approximation

Abstract

The paper presents a methodology for designing bipartite tables for accurate function approximation. Bipartite tables use two parallel table lookups to obtain a carry-save (borrow-save) function approximation. A carry propagate adder can then convert this approximation to a two's complement number or the approximation can be directly Booth encoded. Our method for designing bipartite tables, called the Symmetric Bipartite Table Method, utilizes symmetry in the table entries to reduce the overall memory requirements. It has several advantages over previous bipartite table methods in that it: (1) provides a closed form solution for the table entries; (2) has right bounds on the maximum absolute error; (3) requires smaller table lookups to achieve a given accuracy; and (4) can be applied to a wide range of functions. Compared to conventional table lookups, the symmetric bipartite tables presented are 15.0 to 41.7 times smaller when the operand size is 16 bits and 99.1 to 273.9 times smaller when the operand size is 24 bits.