SubscribePOW • Official Rules • Weekly Winners • Past Problems

Week Ten: COMPUTIN' EXPONENTS
Solutions due by high noon on Friday, November 13, 2009

Suppose you need to compute x to the kth power, where x and k are both large numbers. The straightforward way to do so is with k-1 multiplications, as in the following pseudocode:

exponent(x, k):

product = x
repeat k-1 times:

product = product * x

return product

However, this is not the only way to compute an exponent. In fact, it's a very slow way to do it.

1. Write either a program or precise pseudocode to show how to compute x^k with fewer multiplications.
2. Give an upper bound on how many multiplications it takes and an explanation of why.

Submit solutions to Maegan Bos via email, departmental mailbox, or at her office (VAL 210-1).