Book 1:17: Consider the problem of computing r for given integers x and y, where x...

Transcribed Image Text:

Book 1:17: Consider the problem of computing r for given integers x and y, where x is an n-bit number in binary. We want the whole answer, not modulo a third integer. We know two algorithms for doing this: the iterative algorithm which performs y - 1 multiplications by x; and the recursive algorithm based on the binary expansion of y. Compare the time requirements of these two algorithms, assuming that the time to multiply an n-bit number by an m-bit number is O(mn) (we are in the bit-model). (Your answer should be expressed in terms of n and y, such as yn, or whatever the correct answer is.) Book 1:17: Consider the problem of computing r for given integers x and y, where x is an n-bit number in binary. We want the whole answer, not modulo a third integer. We know two algorithms for doing this: the iterative algorithm which performs y - 1 multiplications by x; and the recursive algorithm based on the binary expansion of y. Compare the time requirements of these two algorithms, assuming that the time to multiply an n-bit number by an m-bit number is O(mn) (we are in the bit-model). (Your answer should be expressed in terms of n and y, such as yn, or whatever the correct answer is.)