Addition and subtraction
Addition and subtraction are performed on two integers having the same number of base b digits. To add or subtract two integers of different lengths, the smaller of the two integers is first padded with 0’s on the left (i.e., in the highorder positions).
14.7 Algorithm Multipleprecision addition
INPUT: positive integers x and y, each having n + 1 base b digits. OUTPUT: the sum x + у = (w_{n+}iw_{n} ■ ■ ■ wiwo)b in radix b representation.
 1. ct0 (c is the earn digit).
 2. For i from 0 to n do the following:
 2.1 Wii—ixi + yi+ c) mod b.
 2.2 If (xi + y_{t} + c) < b then C'iO; otherwise ct— 1.
 3. w_{n+1} tc.
 4. Retum((w_{n}+iw_{n} • • • uqiuo)).
 14.8 Note (computational efficiency) The base b should be chosen so that (ж, + у, + c) mod b can be computed by the hardware on the computing device. Some processors have instruction sets which provide an addwithcarry to facilitate multipleprecision addition.
14.9 Algorithm Multipleprecision subtraction
INPUT: positive integers x and y, each having n + 1 base b digits, with x > y. OUTPUT: the difference x  у = (w_{n}w_{n}i ■ ■ ■ ww_{0})b in radix b representation.
 1. ct—0.
 2. For i from 0 to n do the following:
 2.1 Wi<—(x, — yi + c) mod b.
 2.2 If (xi  y, + c) > 0 then e<—0; otherwise ca1.
 3. Retum((w_{n}w„_i • • • t«rw_{0})).
 14.10 Note (eliminating the requirement x > y) If the relative magnitudes of the integers x and у are unknown, then Algorithm 14.9 can be modified as follows. On termination of the algorithm, if c = 1, then repeat Algorithm 14.9 with x = (00 • • ■ 00)/, and у = (w_{n}w_{n}i ■ ■ ■ u’lU’o)&• Conditional checking on the relative magnitudes of x and у can also be avoided by using a complement representation (§14.2.1(ii)).
 14.11 Example (modified subtraction) Let x = 3996879 and у = 4637923 in base 10, so that x < y. Table 14.2 shows the steps of the modified subtraction algorithm (cf. Note 14.10). □
First execution of Algorithm 14.9 
Second execution of Algorithm 14.9 

i 
6 
5 
4 
3 
2 
1 
0 
i 
6 
5 
4 
3 
2 
1 
0 

Xi 
3 
9 
9 
6 
8 
7 
9 
Xi 
0 
0 
0 
0 
0 
0 
0 

Vi 
4 
G 
3 
7 
9 
2 
3 
yi 
9 
3 
5 
8 
9 
5 
6 

Wi 
9 
3 
5 
8 
9 
5 
6 
Wi 
0 
G 
4 
1 
0 
4 
4 

c 
1 
0 
0 
1 
1 
0 
0 
c 
1 
1 
1 
1 
1 
1 
1 
Table 14.2: Modified subtraction (see Example 14.11).