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 high-order positions).

INPUT: positive integers x and y, each having n + 1 base b digits. OUTPUT: the sum x + у = (wn+iwn ■ ■ ■ wiwo)b in radix b representation.

• 1. c-t-0 (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 + yt + c) < b then C'i-O; otherwise c-t— 1.
• 3. wn+1 -t-c.
• 4. Retum((wn+iwn • • • 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 add-with-carry to facilitate multiple-precision addition.

14.9 Algorithm Multiple-precision subtraction

INPUT: positive integers x and y, each having n + 1 base b digits, with x > y. OUTPUT: the difference x - у = (wnwn-i ■ ■ ■ ww0)b in radix b representation.

• 1. c-t—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 ca--1.
• 3. Retum((wnw„_i • • • t«rw0)).
• 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 у = (wnwn-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).