Fast exponentiation is used for computing xn or x to the power n.
A naive approach would compute the following:
xn = (x • x • ... • x) n times
The overall time complexity is O(n).
We will use the method of exponentiation by squaring for fast computation. It is derived by observing the following to compute xn:
- (xn/2)2 if n is even
- x • (xn/2)2 if n is odd
where n/2 is the floor division.
In essence, we have reduced our problem size by half from size n to size n/2. Using this approach, we will have at most log n steps.
Best Case: Ω(log n)
Average Case: θ(log n)
Worst Case: O(log n)
where n represents the power to be computed.
Worst Case: O(1)
Computes xn. The function power has the following parameters:
x: a doublen: an integer representing the power to be computed
Return value: a double which is the result of xn.
A single line containing two space-separated values, the first being a double value representing x and the second being an integer value representing n.
A single double value with 6 degrees of precision which is the result of xn.
10 0
1.000000
2 3
8.000000
2 -3
0.125000