Mathematics Problem of the Week
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 * xreturn product
However, this is not the only way to compute an exponent. In fact, it's a very slow way to do it.
- Write either a program or precise pseudocode to show how to compute x^k with fewer multiplications.
- 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).
