272 ARITHMETIC 4.3.2 On binary computers it is (1 on 1 web hosting)
272 ARITHMETIC 4.3.2 On binary computers it is sometimes desirable to choose the mj in a different way, by selecting mj = 2e3 - 1. (14 In other words, each modulus is one less than a power of 2. Such a choice of rnj often makes the basic arithmetic operations simpler, because it is relatively easy to work modulo 2ej -1, as in ones complement arithmetic. When the moduli are chosen according to this strategy, it is helpful to relax the condition 0 5 uj < rnj slightly, so that we require only 0 5 Uj < 2e , Uj E u (modulo 2e - 1). (15) Thus, the value uj = mj = 2e~ - 1 is allowed as an optional alternative to Uj = 0, since this does not affect the validity of Theorem C, and it means we are allowing ZL~ to be any ej-bit binary number. Under this assumption, the operations of addition and multiplication modulo mj become the following: uj + vj7 ifUj+Vj < 2e3; Uj $ Vj = (16) ((Uj + vj)mod2ej) + 1, if uj + vj 2 2e3. (17) (Here $ and @ refer to the operations done on the individual components of (WY... , u,) and (VI , . . . , v,) when adding or multiplying, respectively, using the convention (15).) Equation (12) may be used for subtraction. These operations can be performed efficiently even when mj is larger than the computer s word size, since it is a simple matter to compute the remainder of a positive number modulo a power of 2, or to divide a number by a power of 2. In (17) we have the sum of the upper half and the lower half of the product, as discussed in exercise 3.2.1.1-8. If moduli of the form 29 -1 are to be used, we must know under what con- ditions the number 2e - 1 is relatively prime to the number 2f -1. Fortunately, there is a very simple rule, gcd(ze -1,2f -1) = 2gcd@lf) -1, (18) which states in particular that 2e - 1 and 2f -1 are relatively prime if and only if e md f are relatively prime. Equation (18) follows from Euclid s algorithm and the identity (2e -1) mod (2f -1) = 2e mod f -1. (19) (See exercise 6.) Thus we could choose for example ml = 235 - 1, m2 = 234 - 1, m3 = 233 -1, m4 = 231 -1, m.tj = 22g -1, if we had a computer with word size 235; this would permit efficient addition, subtraction, and multiplication of integers in a range of size m1m2m3m4m5 > 2161.