 Multiple-precision integer arithmetic

This section deals with the basic operations performed on multiple-precision integers: addition, subtraction, multiplication, squaring, and division. The algorithms presented in this section are commonly referred to as the classical methods.

Positive integers can be represented in various ways, the most common being base 10. For example, a = 123 base 10 means a = 1 • 102 + 2 • 101 + 3 • 10°. For machine computations, base 2 (binaryrepresentation) is preferable. If a = 1111011 base 2, then a = 2(i + 25 +

• 24 + 23 + 0 • 22 + 21 + 2°.
• 14.1 Fact If b > 2 is an integer, then any positive integer a can be expressed uniquely as a =

anbn + a„_i6n_1 -I-----1- aib + a0, where a» is an integer with 0 < a, < b for 0 < i < n,

and an ф 0.

14.2 Definition The representation of a positive integer о as a sum of multiples of powers of b, as given in Fact 14.1, is called the base b or radix b representation of a.

• 14.3 Note (notation and terminology)
• (i) The base b representation of a positive integer a given in Fact 14.1 is usually written as a = (a„a„_i • • • aiao)b- The integers a,, 0 < i < n, are called digits. an is called the most significant digit or high-order digit; ao the least significant digit or low-order digit. If b = 10, the standard notation is a = anan-i ■ ■ ■ ai«0.
• (ii) It is sometimes convenient to pad high-order digits of a base b representation with 0’s; such a padded number will also be referred to as the base b representation.
• (iii) If (anan_i • • • а!ао)б is the base 6 representation of a and an ф 0, then the precision or length of a is n+1. If n = 0, then a is called a single-precision integer-, otherwise, a is a multiple-precision integer, a = 0 is also a single-precision integer.

The division algorithm for integers (see Definition 2.82) provides an efficient method for determining the base b representation of a non-negative integer, for a given base b. This provides the basis for Algorithm 14.4.

14.4 Algorithm Radix b representation INPUT: integers a and b, a > 0, b > 2.

OUTPUT: the base b representation a = (an ■ ■ ■ aiao)b, where n > 0 and an ф 0 if n> 1.

• 1. i't-O, X't— a, q|_fj, - qb. (|_-J is the floor function; see page 49.)
• 2. While q > 0, do the following:
• 2.1 i<— i + 1, x<— q, q<— cii-S—x — qb.
• 3. Retum((a;a,_i • • • aiao)).

Signed-magnitude representation has the drawback that when certain operations (such as addition and subtraction) are performed, the sign digit must be checked to determine the appropriate maimer to perform the computation. Conditional branching of this type can be costly when many operations are performed.

(ii) Complement representation

Addition and subtraction using complement representation do not require the checking of the sign digit. Non-negative integers in the range [0,6n_1 - 1] are represented by base b sequences of length n with the high-order digit being 0. Suppose a; is a positive integer in this range represented by the sequence • • • zizo)b where xn = 0. Then —x is

represented by the sequence x = (xnxn _ j • • • xi xo) +1 where ж* = b — l—x, and + is the standard addition with cany. Table 14.1 illustrates the binary complement representation of the integers in the range [-7,7]. In the binary case, complement representation is referred to as two’s complement representation.

 Sequence Signed- magnitude Two’s complement Sequence Signed- magnitude Two’s complement 0111 7 7 1111 -7 -1 0110 G 6 1110 -G -2 0101 5 5 1101 -5 -3 0100 4 4 1100 -4 ^4 ООП 3 3 1011 -3 -5 0010 2 2 1010 -2 -6 0001 1 1 1001 -1 -7 0000 0 0 1000 -0 -8

Table 14.1: Signed-magnitude and two's complement representations of integers in [-7,7].