Multipleprecision integer arithmetic
This section deals with the basic operations performed on multipleprecision integers: addition, subtraction, multiplication, squaring, and division. The algorithms presented in this section are commonly referred to as the classical methods.
Radix representation
Positive integers can be represented in various ways, the most common being base 10. For example, a = 123 base 10 means a = 1 • 10^{2} + 2 • 10^{1} + 3 • 10°. For machine computations, base 2 (binary’ representation) is preferable. If a = 1111011 base 2, then a = 2^{(i} + 2^{5} +
 2^{4} + 2^{3} + 0 • 2^{2} + 2^{1} + 2°.
 14.1 Fact If b > 2 is an integer, then any positive integer a can be expressed uniquely as a =
a_{n}b^{n} + a„_i6^{n_1} I1 aib + a_{0}, where a» is an integer with 0 < a, < b for 0 < i < n,
and a_{n} ф 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. a_{n} is called the most significant digit or highorder digit; ao the least significant digit or loworder digit. If b = 10, the standard notation is a = a_{n}a_{n}i ■ ■ ■ ai«_{0}.
 (ii) It is sometimes convenient to pad highorder 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 (a_{n}a_{n}_i • • • а!ао)б is the base 6 representation of a and a_{n} ф 0, then the precision or length of a is n+1. If n = 0, then a is called a singleprecision integer, otherwise, a is a multipleprecision integer, a = 0 is also a singleprecision integer.
The division algorithm for integers (see Definition 2.82) provides an efficient method for determining the base b representation of a nonnegative 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 = (a_{n} ■ ■ ■ aiao)b, where n > 0 and a_{n} ф 0 if n> 1.
 1. i'tO, 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<— ciiS—x — qb.
 3. Retum((a;a,_i • • • aiao)).
Signedmagnitude 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. Nonnegative integers in the range [0,6^{n_1}  1] are represented by base b sequences of length n with the highorder digit being 0. Suppose a; is a positive integer in this range represented by the sequence • • • zizo)b where x_{n} = 0. Then —x is
represented by the sequence x = (x_{n}x_{n} _ 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: Signedmagnitude and two's complement representations of integers in [7,7].