Some Crazy Loop Fun

Divide and Conquer Power Algorithm

You wil produce two functions, power_rec and power_iter based on the algorithm outlined here. The function power_rec is the recurisive version and power_iter uses a loop to implement the algorithm.

def power(x, n):
    if n == 0: return 1
    if n < 0:
        x = 1/x
        n = -n
    return n*power(x, n -1)

Computing 2¹⁰⁰ uses about 100 frames.

Using this method renders computing 1.000000001^1000000000 out of the question. Python can do this in the blink of an eye.

>>> 1.000000001**1000000000
2.7182820520115603

A Divide and Conquer Algorithm

       310 = 95
           = 9*94
           = 9*812
           = 9*6561
           = 59049

When an exponent is odd, we break off an extra power. When an exponent is even, we square the base and halve the exponent.

       4.2520 = 18.062510
              = 326.253906255
              = 326.25390625*326.253906254
              = 326.25390625*106441.611343383792
                326.25390625*11329816625.375969
              = 3696396931125.1025