Introduction

In many applications integer computations are to be performed modulo some given constant. One such area is cryptology, where often multiplications, inversions, and exponentiations are to be performed modulo some very large integer. Hence we shall here investigate algorithms for such operations in their own right, but also because these can be used as primitives for the implementation of multiple modulus systems, also denoted residue number systems and abbreviated to RNSs. Here an integer is represented by a set of residues (the values of the integer modulo a set of given integer moduli, often chosen to be prime numbers).

In such systems computations in a large integer domain can be performed truly in parallel on completely independent processors (often called “channels”), one for each modulus from the set of moduli, and thus operating in a much smaller domain. Due to this independence, additions can be performed “carry-free” in the sense that there is no interaction between the computations of the channels, each of which is operating on integers from a smaller domain. The same applies to multiplication, and as we have pointed out in Chapter 3, such arithmetic is one way to minimize the hj-separable sets, and thus to decrease the computation time by exploiting parallelism. Addition, subtraction, and multiplication in particular can thus be efficiently implemented, whereas other operations like division and comparisons are much more difficult.

Introduction

The product of two radix polynomials is a radix polynomial whose digits can be expressed as sums of digit products from the operand polynomials. The digits thus expressed are in general from some much larger digit set, and a conversion must be performed in some way to deliver the result in the same digit set as that of the operands. The order in which digit products are generated, and later accumulated, is algorithm specific.

Often intermediate products (called partial products) are formed by multiplying a digit from one operand (the multiplier) by the complete other operand (the multiplicand), followed by accumulation of shifted versions of these, to account for the different weights of the multiplier digits. Hence there are three recognizable steps in forming the product:

1. (i) formation of digit or partial products,

2. (ii) summation of digit or partial products,

3. (iii) final digit set conversion,

where these steps individually or in combination can be performed in parallel or sequentially in various ways.

The order in which digit products or partial products are formed and how accumulation is performed thus characterize the algorithms. Some implicitly perform a base and digit set conversion, utilizing a higher radix to reduce the number of terms that have to be added. The different algorithms can also be characterized according to the way operands are delivered/consumed, and how the result is produced, whether word parallel or digit serial, and in the last case in which order.

Introduction

From the earliest cultures humans have used methods of recording numbers (integers), by notches in wooden sticks or collecting pebbles in piles or rows. Conventions for replacing a larger group or pile, e.g., five, ten, or twelve objects, by another object or marking, are also found in some early cultures. Number representations like these are examples of positional number systems, in which objects have different weight according to their relative positions in the number. The weights associated with different positions need not be related by a constant ratio between the weights of neighboring positions. In time, distance, old currency, and other measuring systems we find varying ratios between the different units of the same system, e.g., for time 60 minutes to the hour, 24 hours to the day, and 7 days to the week, etc.

Systems with a constant ratio between the position weights are called radix systems; each position has a weight which is a power of the radix. Such systems can be traced back to the Babylonians who used radix 60 for astronomical calculations, however without a specific notation for positioning of the unit, so it can be considered a kind of floating-point notation. Manipulating numbers in such a notation is fairly convenient for multiplication and division, as is known for anyone who has used a slide rule. Our decimal notation with its fixed radix point seems to have been developed in India about 600 CE, but without decimal fractions.

Introduction

Floating-point number systems evolved from the process of expressing numbers in “scientific decimal notation,” e.g., 2.734 × 106 and −5.23 × 10−4. In practice, the display of a value in scientific notation generally employed the length (precision) of the display as a measure of the accuracy of the display. Values such as α = 6.0247 × 1023 for Avogadro's number or π = 3.14159 × 100 for the natural constant π were subject to various interpretations regarding the final digit with respect to the correspondence to the presumed infinitely precise specification of the real number for which the scientific notation was an approximation. Terms such as correct, rounded, and significant were often explicitly or implicitly implied with the display.

Specifically, the digits were termed correct if they agreed with the initial digits of an infinitely precise specification, such as 3.1415 or 3.141592 for π. This interpretation is now popularly termed the round-towards-zero result. The notions of rounded and significant digits did not convey such an unambiguous interpretation. Saying that 2.734 × 10−6 was a rounded value of x did not necessarily mean that ∣x − 2.734 × 10−6∣ was guaranteed to be at most .5 × 10−9. More particularly, disregarding inherent measurement error, the rounding of the exact “midpoint” value x = 2.7345 × 10−6 to four places was subject to different interpretations. Most ambiguous was the statement that the digits 6.0247 × 1023 were significant in representing a number such as Avogadro's constant. This probably meant only that the relative error was less than one-half part in 6024 but not necessarily less than one-half part in 60247.

This book builds a solid foundation for finite precision number systems and arithmetic, as used in present day general purpose computers and special purpose processors for applications such as signal processing, cryptology, and graphics. It is based on the thesis that a thorough understanding of number representations is a necessary foundation for designing efficient arithmetic algorithms.

Although computational performance is enhanced by the ever increasing clock frequencies of VLSI technology, selection of the appropriate fundamental arithmetic algorithms remains a significant factor in the realization of fast arithmetic processors. This is true whether for general purpose CPUs or specialized processors for complex and time-critical calculations. With faster computers the solution of ever larger problems becomes feasible, implying need for greater precision in numerical problem solving, as well as for larger domains for the representation of numerical data. Where 32-bit floating-point representations used to be the standard precision employed for routine scientific calculations, with 64-bit double-precision only occasionally required, the standard today is 64-bit precision, supported by 128-bit accuracy in special situations. This is becoming mainstream for commodity microprocessors as the revised IEEE standard of 2008 extends the scalable hierarchy for floating-point values to include 128-bit formats. Regarding addressing large memories, the trend is that the standard width of registers and buses in modern CPUs is to be 64 bits, since 32 bits will not support the larger address spaces needed for growing memory sizes. It follows that basic address calculations may require larger precision operands.