# This is a phython3 script
import time, timeit

# functions/methods that compute the power a^b:

def SlowExponentiation(a,b):
    x = a
    for i in range(b-1):
        x *= a;
    return x

def Exponentiation(a,b):
    return a**b; 

def FastExponentiationBook(a,b):
    (x,y,z) = (a,1,b);
    while(True):
        if(z==0):
            return y
        r = z%2
        z = z//2
        if(r==1):
            y = x*y
        x = x*x

def FastExponentiation(x,z):
    y =1
    while(z):
        if(z%2):
            y *= x
        z //= 2
        x *= x
    return y

N = 9999
print('Evaluating SlowExponentiation takes     ',timeit.timeit('SlowExponentiation(7,10)', setup='from __main__ import SlowExponentiation', number=N),' seconds.')
print('Evaluating Exponentiation takes         ',timeit.timeit('Exponentiation(7,10)', setup='from __main__ import Exponentiation', number=N),' seconds.')
print('Evaluating FastExponentiationBook takes ',timeit.timeit('FastExponentiationBook(7,10)', setup='from __main__ import FastExponentiationBook', number=N),' seconds.')
print('Evaluating FastExponentiation takes     ',timeit.timeit('FastExponentiation(7,10)', setup='from __main__ import FastExponentiation', number=N),' seconds.')
print('Evaluating directly takes               ',timeit.timeit('7**10', number=N),' seconds.\n\n')


def FastExponentiationAnalysis(a,b):
    (x,y,z) = (a,1,b);
    (Div,Multi,Comp,Count) = (0,0,0,0);
    while(z):
        if(z%2):
            y *= x
            Multi += 1
        Comp += 2
        z //= 2
        Div += 1
        x *= x
        Multi += 1
        Count += 1
    print("call with a=",a,"  b=",b)
    print("# iterations:",Count)    
    print("# comparisons:",Comp)
    print("# mutiplications:",Multi)    
    print("# divisions (by two):",Div)
    print("# total:",Multi+Comp+Div,"\n")    
    return y

FastExponentiationAnalysis(2,1)
FastExponentiationAnalysis(2,2)
FastExponentiationAnalysis(2,3)
FastExponentiationAnalysis(2,4)
FastExponentiationAnalysis(2,15)
FastExponentiationAnalysis(3,15)
FastExponentiationAnalysis(6,15)
FastExponentiationAnalysis(7,15)