##this a an O(n) time algorithm 
def power(x, n):
    if n < 0:
        x = 1.0/x
        n = -n
    out = 1
    for k in range(n):
        out *= x
    return out
# can you make an iterative version of this?  
# the Kleinier Problem
def pwr(x, n):
    print("BABIIES")
    if n < 0:
        x = 1.0/x
        n = -n
    if n == 0:
        return 1
    if n % 2 == 0:
        return pwr(x*x, n//2)
    ## what must be true?  n is odd
    return x*pwr(x*x, n//2)
def iterP(x, n):
    if n < 0:
        x = 1.0/x
        n = -n
    base = x
    while n > 1:
        if n % 2 == 0:
            x = x*x
        elif n % 2 == 1:
            x = x*x
            x *= base
        n //= 2
        print(n, x)
    return x


print(iterP(2,5))
print(iterP(2,-5))
print(iterP(1.0000001, 10000000))