Higher radix values of the form β = 2rhave been employed traditionally for recoding of multipliers, and for determining quotientand root-digits in iterative division and square root algorithms, usually only for quite moderate values of r, like 2 or 3. For fast additions, in particular for the accumulation of many terms, generally redundant representations are employed, most often binary carry-save or borrow-save, but in a number of publications it has been suggested to recode the addends into a higher radix. It is shown that there are no speed advantages in doing so if the radix is a power of 2, on the contrary, there are significant savings in using standard 4-to-2 adders, even saving half of the operations in multi-operand addition.

This paper presents a study of some basic blocks needed in the design of floating-point summation algorithms. In particular, in radix-2 floating-point arithmetic, we show that among the set of the algorithms with no comparisons performing only floating-point additions/subtractions, the 2Sum algorithm introduced by Knuth is minimal, both in terms of number of operations and depth of the dependency graph. We investigate the possible use of another algorithm, Dekker's Fast2Sum algorithm, in radix-10 arithmetic. We give methods for computing, in radix 10, the floating-point number nearest the average value of two floating-point numbers. We also prove that under reasonable conditions, an algorithm performing only round-to-nearest additions/subtractions cannot compute the round-to-nearest sum of at least three floating-point numbers. Starting from an algorithm due to Boldo and Melquiond, we also present new results about the computation of the correctly-rounded sum of three floating-point numbers. For a few of our algorithms, we assume new operations defined by the recent IEEE 754-2008 Standard are available.

Define an "augmented precision" algorithm as an algorithm that returns, in precision-p floating-point arithmetic, its result as the unevaluated sum of two floating-point numbers, with a relative error of the order of 2-2p. Assuming an FMA instruction is available, we perform a tight error analysis of an augmented precision algorithm for the square root, and introduce two slightly different augmented precision algorithms for the 2D-norm √x2+y2. Then we give tight lower bounds on the minimum distance (in ulps) between √x2+y2and a midpoint when √x2+y2is not itself a midpoint. This allows us to determine cases when our algorithms make it possible to return correctly-rounded 2D-norms.

During any composite computation, there is a constant need for rounding intermediate results before they can participate in further processing. Recently, a class of number representations denoted RN-Codings were introduced, allowing an unbiased rounding-to-nearest to take place by a simple truncation, with the property that problems with double-roundings are avoided. In this paper, we first investigate a particular encoding of the binary representation. This encoding is generalized to any radix and digit set; however, radix complement representations for even values of the radix turn out to be particularly feasible. The encoding is essentially an ordinary radix complement representation with an appended round-bit, but still allowing rounding-to-nearest by truncation, and thus avoiding problems with double-roundings. Conversions from radix complement to these round-to-nearest representations can be performed in constant time, whereas conversion the other way, in general, takes at least logarithmic time. Not only is rounding-to-nearest a constant time operation, but so is also sign inversion, both of which are at best log-time operations on ordinary two's complement representations. Addition and multiplication on such fixed-point representations are first analyzed and defined in such a way that rounding information can be carried along in a meaningful way, at minimal cost. The analysis is carried through for a compact (canonical) encoding using two's complement representation, supplied with a round-bit. Based on the fixed-point encoding, it is shown possible to define floating-point representations, and a sketch of the implementation of an FPU is presented.

We introduce several algorithms for accurately evaluating powers to a positive integer in floating-point arithmetic, assuming a fused multiply-add (fma) instruction is available. For bounded, yet very large values of the exponent, we aim at obtaining correctly rounded results in round-to-nearest mode, that is, our algorithms return the floating-point number that is nearest the exact value.

This paper presents a study of some basic blocks needed in the design of floating-point summation algorithms. In particular, we show that among the set of the algorithms with no comparisons performing only floating-point additions/subtractions, the 2Sum algorithm introduced by Knuth is minimal, both in terms of number of operations and depth of the dependency graph. Under reasonable conditions, we also prove that no algorithms performing only round-to-nearest additions/subtractions exist to compute the round-to-nearest sum of at least three floating-point numbers. Starting from an algorithm due to Boldo and Melquiond, we also present new results about the computation of the correctly-rounded sum of three floating-point numbers.

An important problem in the realization of floating-point subtraction is the identification of the position of the first nonzero digit in a radix-represented number, since the significand usually is to be represented left-normalized in the part of the word(s) allocated for representing its value. There are well-known log-time algorithms for determining this position for numbers in nonredundant representations, which may also be applied to suitably (linear-time) transformed redundant representations. However, due to the redundancy in the latter case, the position thus determined may need a correction by one. When determination of the shift amount is to be performed in parallel with conversion to nonredundant representation (the subtraction), it must be performed on the redundant representation. This is also the case when the significand is to be retained in a redundant representation until the final rounding. This paper presents an improved algorithm for determining the need for a correction of the normalization shift amount, which can be run in parallel with the algorithm finding the "approximate" position.

Redundant number representations are generally used to allow constant time additions, based on the fact that only bounded carry-ripples take place. But, carries may ripple out into positions which may not be needed to represent the final value of the result and, thus, a certain amount of leading guard digits are needed to correctly determine the result. Also, when cancellation during subtractions occurs, there may be nonzero digits in positions not needed to represent the result of the calculation. It is shown here that, for normal redundant digit sets with radix greater than two, a single guard digit is sufficient to determine the value of such an arbitrary length prefix of leading nonzero digits. This is also the case for the unsigned carry-save representation, whereas two guard digits are sufficient, and may be necessary, for additions in the binary signed-digit and 2's complement carry-save representations. Thus, only the guard digits need to be retained during sequences of additions and subtractions. At suitable points, the guard digits may then be converted into a single digit, representing the complete prefix.

We develop the foundations for confirming monotonicity of a multi-term reciprocal function approximation. We introduce the concept of operand recoding to improve the accuracy of multipartite approximation. The results are applied to provide a proposed four-partite reciprocal implementation with total table size /spl sim/27 Kbytes, that yields an IEEE standard, single precision sized format (24 bit) reciprocal instruction, that is a one-ulp monotonic reciprocal.

Range-reduction is a key point for getting accurate elementary function routines. We introduce a new algorithm that is fast for input arguments belonging to the most common domains, yet accurate over the full double-precision range.

The quotient digit selection in the SRT division algorithm is based on a few most significant bits of the remainder and divisor, where the remainder is usually represented in a redundant representation. The number of leading bits needed depends on the quotient radix and digit set, and is usually found by an extensive search, to assure that the next quotient digit can be chosen as valid for all points (remainder, divisor) in a set defined by the truncated remainder and divisor, i.e., an "uncertainty rectangle." This work presents expressions for the number of bits needed from the truncated remainder and divisor (the truncation parameters), thus eliminating the need for a search through the truncation parameter space for validation. The analysis is then extended to the digit selection in SRT square root algorithms, where it is shown that, in general, it may be necessary to increase the number of leading bits needed for digit determination in a combined divide and square root algorithm. An easy condition to check the number of bits needed is established, also checking the number of initial digits of the root may have to be found by other means, e.g., by table look-up. The minimally redundant, radix-4 combined divide and square root algorithm is finally analyzed and it is shown that, in this case, it can be implemented without such a special table to determine initial digits for the square root.

The quotient digit selection in the SRT division algorithm is based on a few most significant bits of the remainder and divisor, where the remainder is usually represented in a redundant representation. The number of leading bits needed depends on the quotient radix and digit set, and is usually found by an extensive search, to assure that the next quotient digit can be chosen as valid for all points (remainder, divisor) in a set defined by the truncated remainder and divisor, i.e., an "uncertainty rectangle". We present expressions for the number of bits needed for the truncated remainder and divisor, thus eliminating the need for a search through the truncation parameter space for validation. We also present simple algorithms to properly map truncated negative divisors and remainders into nonnegative values, allowing the quotient selection function only to be defined on the smaller domain of nonnegative values.

Recently there has been quite a number of papers discussing the use of redundant 4-to-2 adders for the accumulation of partial products in multipliers, claiming one type to be superior to other types. This paper analyses the use of various 3- and 4-element redundant digit sets for radix 2, and compares their adder implementations using various encodings of the digits and carries. It is shown that theoretically they are equivalent, and differences in their implementations need only be very marginal. Another recent proposal for the use of the digit-set {0, 1, 2, 3}, with a special 3-bit encoding of digits, is analyzed and some optimizations are shown, including the possibility of using a 2-bit encoding, simplifying the wiring of a multiplier tree. All these proposed designs are shown to be equivalent to a standard 4-to-2, carry-save adder except possibly for a few signal inversions.

We present a new RNS modular multiplication for very large operands. The algorithm is based on Montgomery's (1985) method adapted to residue arithmetic. By choosing the moduli of the RNS system reasonably large, an effect corresponding to a redundant high-radix implementation is achieved, due to the carry-free nature of residue arithmetic. The actual computation in the multiplication takes place in constant time, where the unit of time is a few simple residue operations. However, it is necessary twice to convert values from one residue system into another, operations which take O(n) time on O(n) processors, where n is the number of moduli in the RNS systems. Thus these conversions are the bottlenecks of the method, and any future improvements in RNS base conversions, or the use of particular residue systems, can immediately be applied.

625-627

This note presents necessary and sufficient conditions for parallel and constant time conversions from one digit-set into another, and thus also for constant time addition. In the integer domain it is generally believed that such conversion and addition is possible if the target digit-set is redundant and complete. This is also the case when the digit-set is a contiguous set of integers. However, when this is not the case then such conversion and addition in the integer domain is not possible in general, and when more general rings are considered, the same problem may be present.

This paper presents an analysis of radix representations of elements from general rings; in particular, we study the questions of redundancy and completeness in such representations. Mappings into radix representations, as well as conversions between such, are discussed, in particular where the target system is redundant. Results are shown valid for normed rings containing only a finite number of elements with a bounded distance from zero, essentially assuring that the ring is "discrete." With only brief references to the more usual representations of integers, the emphasis is on various complex number systems, including the "classical" complex number systems for the Gaussian integers, as well as the Eisenstein integers, concluding with a summary on properties of some low-radix representations of such systems.

We present a new RNS modular multiplication for very large operands. The algorithm is based on Montgomery's method adapted to mixed radix, and is performed using a residue number system. By choosing the moduli of the RNS system reasonably large and implementing the system on a ring of fairly simple processors, an effect corresponding to a redundant high-radix implementation is achieved. The algorithm can be implemented to run in O(n) time on O(n) processors, where n is the number of moduli in the RNS system, and the unit of time is a simple residue operation, possibly by table look-up. Two different implementations are proposed, one based on processors attached to a broadcast bus, another on an oriented ring structure.

The authors present a new RNS modular multiplication for very large operands. The algorithm is based on Montgomery's method adapted to mixed radix, and is performed using a residue number system. By choosing the moduli of the RNS system reasonably large, and implementing the system an a ring of fairly simple processors, an effect corresponding to a redundant high-radix implementation is achieved. The algorithm call be implemented to run in O(n) time on O(n) processors, where n is the number of moduli in the RNS system, and the unit of time is a simple residue operation, possibly by table look-up.

This paper presents a thorough analysis of radix representations of elements from general rings. In particular, we study the questions of redundancy, completeness and mappings into such representations. After a brief description of the more usual representations of integers, a more detailed analysis of various complex number systems is performed. This includes the "classical" complex number systems for the Gaussian integers, as well as the Eisenstein integers.

The goal of many image processing tasks is to recognise objects, to match scenes and to classify images. The shape, gray or colour features of objects are mainly used to describe objects. The most efficient method used to describe such features of an object is to use various transformed moments. We express the moments as a linear combination of higher order prefix sums, obtained by iterating the prefix sum computation on previous prefix sums, starting with the original function values. Thus the p'th moment m/sub p/=/spl Sigma//sub x=1//sup N/ x/sup p/f(x) can be computed by O(N/spl middot/p) additions followed by p multiply-adds. The prefix summations can be realized in time O(N) using p+1 simple adders, and in time O(p/spl middot/log N) using parallel prefix computation and O(N) adders. In 1986 Hatamian published a computationally equivalent algorithm, based on a cascade of filters performing the summations. Our recursive derivation allows for explicit expressions and recursive equations for the coefficients used in the final moment calculation. Thus a number of alternative forms for the moment computation can be derived, based on different sets of prefix sums, allowing some simplifications in the implementations.

This paper describes DCT (IDCT) computations using the CORDIC algorithm. By rewriting the DCT, for a 1/spl times/8 DCT only 6 CORDIC computations are needed, whereas a 1/spl times/16 DCT requires 22 CORDIC computations. But these can all be pipelined through a single CORDIC unit, so 16/spl times/16 DCT's becomes feasible for HDTV compression. Only some simple adders, registers and a more complicated carry look-ahead adder are needed, end the computing speed can be very high. Limited only by the delay of a carry look-ahead adder, the delay time of the pipelined structure is 2-10 ns and the data rate as 100-500 MHz for an 8/spl times/8 DCT/IDCT and 72.2-366.6 MHz for a 16/spl times/16 DCT/IDCT when using two units.>

The problem of digit set conversion for fixed radix is investigated for the case of converting into a non redundant, as well as into a redundant, digit set. Conversion may be from very general digit sets, and covers as special cases multiplier recodings, additions, and certain multiplications. We generalize known algorithms for conversions into non redundant digit sets, as well as apply conversion to generalize the O(log n) time algorithm for conditional sum addition using parallel prefix computation, and a comparison is made with standard carry-lookahead techniques. Examples on multi-operand addition are used to illustrate the generality of this approach. O(1) time algorithms for converting into redundant digit sets are generalized based on a very simple lemma, which provides a framework for all conversions into redundant digit sets. Applications in multiplier recoding and partial product accumulation are used as exemplifications.>

A very simple multiplier cell is developed for use in a linear, purely systolic array forming a digit-serial multiplier for unsigned or 2'complement operands. Each cell produces two digit-product terms and accumulates these into a previous sum of the same weight, developing the product least significant digit first. Grouping two terms per cell, the ratio of active elements to latches is low, and only upper bound [n]/2 cells are needed for a full n by n multiply. A module-multiplier is then developed by incorporating a Montgomery type of module-reduction. Two such multipliers interconnect to form a purely systolic module exponentiator, capable of performing RSA encryption at very high clock frequencies, but with a low gate count and small area. It is also shown how the multiplier, with some simple back-end connections, can compute modular inverses and perform modular division for a power of two as modulus.>

Two algorithms for modular multiplication with very large moduli are analyzed specifically for their applicability when a high radix is used for the multiplier. Both algorithms perform modulo reductions interleaved with the addition of partial products; one algorithm is using the standard residue system, whereas the other utilizes a nonstandard system using reductions modulo a power of the base. The emphasis is on situations, as in cryptosystems, where modular exponentiation is to be realized by many repeated modular multiplications on very large operands, e.g., for cryptosystems with key lengths of 500-1000 b.>

Semantics are given for the four elementary arithmetic operations and the square root, to characterize what are termed exact floating point operations. The operands of the arithmetic operations and the argument of the square root are all floating point numbers in one format. In every case, the result is a pair of floating point numbers in the same format with no accuracy lost in the computation. These semantics make it possible to realize the following principle: it shall be a user option to discard any information in the result of a floating point arithmetic operation. The reliability and portability previously associated with only mathematical software implementations in integer arithmetic can thus be attained exploiting the generally higher efficiency of floating point hardware.>

In a class of cryptosystems, fast computation of modulo exponentials is essential. The authors present a parallel version of a well-known exponentiation algorithm that halves the worst-case computing time. It is described how a high radix modulo multiplication can be implemented by interleaving a serial-parallel multiplication scheme with an SRT division scheme. The problems associated with high radices are efficiently solved by the use of a redundant representation of intermediate operands. It is shown how the algorithms can be realized as a highly regular VLSI circuit. Simulations indicate that a radix 32 implementation of the algorithms is capable of computing 512-b operand exponentials in 3.2 ms. This is more than five times faster than other known implementations.>

The authors introduce a redundant binary representation of the rationals and an associated algorithm for computing the sum, difference, product, quotient, and other useful functions of two rational operands, using this representation. The algorithm extends R.W. Gosper's (1972) partial quotient arithmetic algorithm and allows the design of an online arithmetic unit with computations granularized at the signed bit level. Each input or output port can be independently set to receive/produce operands/result in either binary radix or the binary rational representation. The authors investigate by simulation the interconnection of several such units for the parallel computation of more complicated expressions in a tree-pipelined manner, with particular regard to measuring individual and compounded online delays.>

The authors develop and analyze a redundant continued-fraction representation of the rationals in the implementation of an arithmetic unit for computing the sum, difference, product, quotient, and other useful functions of two rational operands. Their representation of operands and results allows the computations of the unit to be performed in a signed bit-serial, online fashion. Several such units can then be interconnected for the computation of more complicated expressions in a pipelined manner. Redundancy is used to help achieve a small bounded online delay and uniform throughput.>

We describe a binary implementation of an algorithm of Gosper to compute the sum, difference, product, quotient and certain rational functions of two rational operands applicable to integrated approximate and exact rational computation. The arithmetic unit we propose is an eight register computation cell with bit serial input and output employing the binary lexicographic continued fraction (LCF) representation of the rational operands. The operands and results are processed in a most-significant-bit first on-line fashion with bit level logic leading to less delay in the computation cell when compared to operation on the full partial quotients of the standard continued fraction representation. Minimization of delay is investigated with the aim of supporting greater throughput in cascaded parallel computation with such computation cells.

Lexicographic continued fraction binary (LCF) representation provides an order preserving bitstring representation of the non negative real numbers where every rational number has a finite length bitstring representation. We investigate the precision of k-bit LCF approximation. The maximum gap size over [0,1] for (k+1)-bit LCF representation is shown to be less than 2−.81k, comparable to binary coded decimal in worst case representation efficiency. The distribution of gap sizes for (k+1)-bit LCF representation over [0,1] is shown on a logarithmic scale to be bell shaped between 2−.81kand 2−1.39k, becoming more peaked near the value corresponding to uniform spacing, 2−k, with increasing k.

Fraction number systems characterized by fixed-slash and floating-slash formats are specified. The structure of arithmetic over such systems is prescribed by the rounding obtained from "best rational approximation." Multitiered precision hierarchies of both the fixed-slash and floating-slash type are described and analyzed with regards to their support of both exact rational and approximate real computation.

We describe a new binary encoding for numbers termed lexicographic continued fraction (LCF) representation that provides a one-to-one order preserving finite bit string representation for every rational. Conversion either way between binary integer numerator-denominator pair representation and LCF representation is shown feasible in time linear with bit string length, given registers of length sufficient to hold the numerator and denominator. LCF bit string length is about 2 max{log2p, log2q} for the irreducible fraction p/q. Realization of arithmetic (+, −, ×, ÷ on LCF bit string encoded operands is shown feasible. Some relations between the theory of best rational approximation and the values represented by truncated LCF bit strings are noted to assess the feasibility of a finite precision arithmetic based on LCF representation.

The foundations of an arithmetic unit performing the add, subtract, multiply, and divide operations on rational operands are developed. The unit uses the classical Euclidean algorithm as one unified algorithm for all the arithmetic operations, including rounding. Binary implementations are discussed, based on techniques known from SRT division, and utilizing ripple-free borrow-save and carry-save addition. Average time behavior is investigated.

Based on the classical Euclidian Algorithm, we develop the foundations of an arithmetic unit performing Add, Subtract, Multiply and Divide on rational operands. The unit uses one unified algorithm for all operations, including rounding. A binary implementation, based on techniques known from the SRT division, is described. Finally, a hardware implementation using ripple-free, carry-save addition is analyzed, and adapted to a floating-slash representation of the rational operands.

Abstract The possibility of supporting high level languages through intermediate languages to be used for direct interpretation and as intermediate forms in compilers is investigated. An accomplished project in the construction of an interpreter and a code generator using one common intermediate form is evaluated. The subject is analysed in general, and a proposal for an improved design scheme is given.

An investigation of the feasibility of a finite precision approximate rational arithmetic based on fixed-slash representation of rational numbers is presented. Worst-case and average-case complexity analyses of the involved rounding algorithm (an extended shift-subtract gcd algorithm) are presented. The results are applied to a proposed hardware realization of a fixed-slash arithmetic unit.

Design and analysis of finite precision rational number systems based on fixed-slash and floating-slash representation is pursued. Natural formats for binary fixed-slash and binary floating-slash number representation in computer words are described. Compatibility with standard integer representation is obtained. Redundancy in the' representation is shown to be minimal. Arithmetic register requirements are considered. Worst case and average case rounding errors are determined, and the concept of adaptive variable precision in the rounding is developed.

This paper describes a combined arithmetic unit and language support system which allows user specifications of the arithmetic. Limited extensions to a high-level language, in connection with a generalized underlying arithmetic unit, allow a single skeletal unified numeric operand type to be refined into a variety of data types. The interpretation of operands by the operators is based on type descriptors, allowing one set of polymorphic arithmetic operators to be defined across all combinations of user-defined operand types. The arithmetic unit is realized in microcode to achieve efficiency.

It is proposed to substitute the standard data type real of a high level language, with a unified data representation which can include a variety of interpretations as well as formats, in order to allow experiments with an environment containing a spectrum of non-standard arithmetics, as well as standard. The implementation of a system is described where syntatic extensions to a language are made to support a microprogrammed virtual arithmetic unit which can treat variants such as integers, normalized, and unnormalized floating point numbers and intervals, within a unified representation.∗∗More specifically Pascal is chosen as the base language, because it allows the user to define new data types, and the extension then mainly consists in substituting the simple (unstructured) data type real with a skeletal structured type (which will be called numeric). The system is intended to be implemented on a microprogrammable processor (called MATHILDA) with a 64 bit wide datapath. The language Pascal has already been partially implemented based on a stack machine specifically designed for that language, and realized by interpretation in microcode. The present compiler was constructed with the aid of a parser-generator system, which will allow the language extensions to be made with a moderate effort.

A companion paper entitled, "A Unified Numeric Data Type in Pascal", proposes the substitution of the standard data type real of the language Pascal with a unified data representation termed numeric. The numeric data type can represent a variety of arithmetic operands such as integers, normalized floating point numbers, and centered-radius intervals. This paper describes an arithmetic unit which is capable of executing the standard arithmetic operations (addition, subtraction, multiplication, and division) on pairs of operands specified to be of the numeric data type. This arithmetic unit, called the UNRAU — Unified Numeric Representation Arithmetic Unit, supports operations on operands externally represented as 5-tuples (t, a, e, f, r). The UNRAU provides for automatic conversion among the various data types and can also be used to perform an explicit conversion on a single operand. It is intended to implement the UNRAU on a dynamically microprogrammable microprocessor to determine what host facilities are required to efficiently realize such an arithmetic unit and to experiment with the high level language support of such a unit.

A dynamically microprogrammable processor called MATHILDA is described. MATHILDA has been designed to be used as a tool in emulator and processor design research. It has a very general microinstruction sequencing scheme, sophisticated masking and shifting capability, high speed local storage, a 64-bit wide main data path, a horizontally encoded microinstruction, and other facilities which make it reasonably well suited for this purpose. This paper presents a brief overview of the MATHILDA system, and some of the concepts in more detail.