Fast exponentiation
Problem
Raising to a power is much faster than n multiplications! To do this, use the following recurrence relations:
\(a^n=(a^2)^{n/2}\) even n,
\(a^n=a \cdot a^{n-1}\) for odd n.
Implement the fast exponentiation algorithm. If you do everything right, then the complexity of your algorithm will be O(logn) .
Input
Enter a real number a and an integer n.
Imprint
Print the answer to the problem, with an accuracy of 6 decimal places.
You can't use standard exponentiation.
Examples
| # |
Input |
Output |
| 1 |
2
7 |
128 |
| 2 |
1.00001
100000
|
2.71827 |
Запрещенные операторы: pow; **; log