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

14.7 Algorithm Multiple-precision addition

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).

 
Source
< Prev   CONTENTS   Source   Next >