High‐speed multioperand addition and subtraction using a p‐ary representation with necessary and minimum redundancy
T. Tamesada · Systems and Computers in Japan · 1989
Abstract In the usual P‐ary number digit for the addition and subtraction of two numbers (operands), 0, 1, 2, …, P ‐ 1 are employed. In the minimum redundant P‐ary representation, 1 is further used, and the addition or subtraction can be performed in a constant time independent of the number of operand digits (Pϵ{2, 3, 4, …}). This paper extends this property. First, a high‐speed addition‐subtraction algorithm is discussed. It can execute the addition and subtraction of L(ϵ {2, 3, …, P}) operands in a constant time independent of n and L. The following property is shown as the result. Using the redundant P‐ary representation (called K‐redundant P‐ary representation), where K,…, 2, 1, 0, 1, 2, …, P‐l can be used as the digit, the minimum necessary value for K is L ‐ 1, and the desired algorithm can be found if L‐1K(ϵP—1). The presented algorithm can easily be extended to an algorithm which can execute the addition and subtraction of L operands in a constant time independent of n, where L is an arbitrary number such that P+IL. It is shown that if f(x) = [logpx]+1 ([y] is the minimum integer not less than y), the computation time T is O(loga), where α is the minimum number of operations for the function f( ) satisfying f(f(f(F))))P; α increases stepwise with L. When P is increased, T decreases, and the range of L, for which T is constant, increases exponentially. Using the proposed algorithm, one can expect that a multi‐input high‐speed adder‐subtractor can be constructed. Various kinds of high‐speed data processings can be realized, including the multiplication, where the shifted partial products are added.