Module: (Python) Subroutines. recursion


Problem

7 /12


Fast exponentiation

Problem

Raising to a power is faster than n multiplications! To do this, use the following recurrence relations:
\(a^n=(a^2)^{n/2},\ for \ 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
The program receives a real number a and an integer n as input. Each number on a separate line.

Imprint 
Output \(a^n\).
 
Examples
# Input Output
1 2
7		 128
2 1.00001
100000		 2.71827

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!