Composite Iterative Algorithm and Architecture for q-th Root Calculation

An algorithm for the q-th root extraction, being q any integer, is presented in this paper. The algorithm is based on an optimized implementation of X1/q= 2(1/q)log2(X) by a sequence of parallel and/or overlapped operations: (1) reciprocal, (2) digit–recurrence logarithm, (3) left–to–right carry–free multiplication and (4) on–line exponential. A detailed error analysis and two architectures are proposed, for low precision q and for higher precision q. The execution time and hardware requirements are estimated for single and double precision floating–point computations for several radices; this helps to determine which radices result in the most efficient implementations. The architectures proposed improve the features of other architectures for q–th root extraction.

keywords: Integer rooting, high-radix digit-by-digit algorithms, on-line algorithms, elementary function evaluation