Implement the power function using fast exponentiation. Halving the exponent makes this efficient.
Your function takes a base and exponent , returning .
Requirements:
- (base case)
- If is even:
- If is odd:
- Handle negative exponents:
Examples:
power(2, 10)->power(3, 0)->power(2, -2)->
This runs in time instead of because you halve the exponent each step.