Show description

Make sure your algorithm correctly computes the sign bit of the result, and also strips leading zero digits from the result. 15. Work out the details of an algorithm that compares two signed integers a and b, determining which of a < b, a = b, or a > b holds. 16. Suppose that we run the division with remainder algorithm in Fig. 1 for > 1 without normalizing b, but instead, we compute the value qi in line 4 as follows: qi ← (ri+ B 2 + ri+ −1 B + ri+ −2 )/(b −1 B +b −2 ) . Show that qi is either equal to the correct quotient digit, or the correct quotient digit plus 1.

4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. for i ← 0 to k − 1 do ri ← ai rk ← 0 for i ← k − down to 0 do qi ← (ri+ B + ri+ −1 )/b −1 if qi ≥ B then qi ← B − 1 carry ← 0 for j ← 0 to − 1 do tmp ← ri+j − qi bj + carry (carry, ri+j ) ← divmod(tmp, B) ri+ ← ri+ + carry while ri+ < 0 do carry ← 0 for j ← 0 to − 1 do tmp ← ri+j + bi + carry (carry, ri+j ) ← divmod(tmp, B) ri+ ← ri+ + carry qi ← qi − 1 output the quotient q = (qk− · · · q0 )B and the remainder r = (r −1 · · · r0 )B Fig. 1. Division with Remainder Algorithm Finally, consider the general case, where b may not be normalized.

Let a, b, n ∈ Z with n > 0, and let d := gcd(a, n). If d | b, then the congruence az ≡ b (mod n) has a solution z, and any integer z is also a solution if and only if z ≡ z (mod n/d). If d b, then the congruence az ≡ b (mod n) has no solution z. Proof. For the first statement, suppose that d | b. 6, and the fact that a/d and n/d are relatively prime. For the second statement, we show that if az ≡ b (mod n) for some TEAM LinG 18 Congruences integer z, then d must divide b. To this end, assume that az ≡ b (mod n) for some integer z.