Exercise · Algorithms and Complexity · lesson 9 of 9
Exercise: fast exponentiation
Write a function long long power(long long base, int exp) that returns base raised to the power exp. The number of multiplications must grow as O(log exp), not as O(exp). For an even exponent, power(b, 2 * k) equals p * p, where p is the value of power(b, k).
power(2, 10)→1024power(3, 13)→1594323power(-2, 5)→-32
Constraints: exp is at least 0, and any number to the power 0 is 1. The base may be negative, and the result always fits in a long long.
