Hardware algorithms for computing exponentials and logarithms using redundant binary representation
Naofumi Takagi, Shuzo Yajima · Systems and Computers in Japan · 1986
Abstract In this paper, we propose hardware algorithms for computing exponentials and logarithms utilizing the redundant binary representation for internal computation. The algorithms proposed in this paper are improved versions of modified STL methods which were improved by Specker and by Chen and are known as methods suited for the dedicated circuits for computing exponentials and logarithms. The algorithms by Specker and by Chen compute exponentials and logarithms by repeating a simple procedure composed of an additional subtraction, a shift and a table look‐up. In the proposed algorithms, by using the redundant binary representation, each digit at which is an element of {0, 1, ‐1} for the internal computation, we eliminate carry (borrow) propagation from addition (subtraction) and improve the speed of computation. Using the traditional methods, because of carry (borrow) propagation addition (subtraction), combinational circuits for computing n‐bit exponentials and logarithms require at least a computation time proportional to n log n and the number of elements proportional to n2. Using the proposed algorithms, the computation time is improved to be proportional to n, and the number of elements is proportional to n2 using traditional methods.