MIT 6.00 Lecture 8 Notes on exp()

In Lecture 8 a recursive algorithm for finding a to the b is shown. The algorithm flip-flops between two cases (even, odd) until it reaches the base case of b == 0. For odd cases the problem is reduced by one, for even cases the problem is reduced by half.

I think it can be hard to see where the final result comes from at first. What can exp() return? It can return 1, a or *a. 1 is returned for the edge case b == 0 so returning a or *a are the typical results. Any particular result is going to be of the form:

result = a*a*a .  .  .


For 2**15:

    exp3(2,15)
2*exp3(2,14)
    exp3(4,7)
4*exp3(4,6)
    exp3(16,3)
16*exp3(16,2)
    exp3(256,1)
b == 1
a: 256
result: 32768


result = 2*4*16*256 => 32768

Also notice that in the below code that the even test is (b%2)*2 == 0 not == b.

Python Code:

def exp(a,b,mult):
    print "Call %d*exp3(%d,%d)" % (mult,a,b)
    if b == 0:
        print 'b == 0'
        return 1

    if b == 1:
        print 'b == 1'
        print "a: %d" % (a)
        return a

    if (b%2)*2 == 0:
        print '\tif (b%2)*2 == 0: ',
        print "[b: %d]" % (b)
        return exp(a*a, b/2, 1)
    else:
        print "\telse              [b: %d]" % (b)
        return a*exp(a, b-1, a)

if __name__ == '__main__':
    for i in range(0,16):
        print "===> 2^%d" % (i)
        print "result: %d\n" % exp(2,i,1)

'''
exp(2,4)
  exp(2*2, 4/2)
    exp(4*4, 2/2)
    b == 1
    return 16

==> 16

exp(2,5)
  2*exp(2, 5-1)
    exp(2*2, 4/2)
      exp(4*4, 2/2)
        b == 1
        return 16

==> 16 * 2 = 32

exp(2,6)
  exp(2*2, 6/2)
    4*exp(4, 3-1)
      exp(4*4, 2/2)
        b == 1
        return 16

==> 16 * 4 = 64          
'''

Output:

===> 2^0
Call 1*exp3(2,0)
b == 0
result: 1

===> 2^1
Call 1*exp3(2,1)
b == 1
a: 2
result: 2

===> 2^2
Call 1*exp3(2,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(4,1)
b == 1
a: 4
result: 4

===> 2^3
Call 1*exp3(2,3)
        else              [b: 3]
Call 2*exp3(2,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(4,1)
b == 1
a: 4
result: 8

===> 2^4
Call 1*exp3(2,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(4,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(16,1)
b == 1
a: 16
result: 16

===> 2^5
Call 1*exp3(2,5)
        else              [b: 5]
Call 2*exp3(2,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(4,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(16,1)
b == 1
a: 16
result: 32

===> 2^6
Call 1*exp3(2,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(4,3)
        else              [b: 3]
Call 4*exp3(4,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(16,1)
b == 1
a: 16
result: 64

===> 2^7
Call 1*exp3(2,7)
        else              [b: 7]
Call 2*exp3(2,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(4,3)
        else              [b: 3]
Call 4*exp3(4,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(16,1)
b == 1
a: 16
result: 128

===> 2^8
Call 1*exp3(2,8)
        if (b%2)*2 == 0:  [b: 8]
Call 1*exp3(4,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 256

===> 2^9
Call 1*exp3(2,9)
        else              [b: 9]
Call 2*exp3(2,8)
        if (b%2)*2 == 0:  [b: 8]
Call 1*exp3(4,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 512

===> 2^10
Call 1*exp3(2,10)
        if (b%2)*2 == 0:  [b: 10]
Call 1*exp3(4,5)
        else              [b: 5]
Call 4*exp3(4,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 1024

===> 2^11
Call 1*exp3(2,11)
        else              [b: 11]
Call 2*exp3(2,10)
        if (b%2)*2 == 0:  [b: 10]
Call 1*exp3(4,5)
        else              [b: 5]
Call 4*exp3(4,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 2048

===> 2^12
Call 1*exp3(2,12)
        if (b%2)*2 == 0:  [b: 12]
Call 1*exp3(4,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(16,3)
        else              [b: 3]
Call 16*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 4096

===> 2^13
Call 1*exp3(2,13)
        else              [b: 13]
Call 2*exp3(2,12)
        if (b%2)*2 == 0:  [b: 12]
Call 1*exp3(4,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(16,3)
        else              [b: 3]
Call 16*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 8192

===> 2^14
Call 1*exp3(2,14)
        if (b%2)*2 == 0:  [b: 14]
Call 1*exp3(4,7)
        else              [b: 7]
Call 4*exp3(4,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(16,3)
        else              [b: 3]
Call 16*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 16384

===> 2^15
Call 1*exp3(2,15)
        else              [b: 15]
Call 2*exp3(2,14)
        if (b%2)*2 == 0:  [b: 14]
Call 1*exp3(4,7)
        else              [b: 7]
Call 4*exp3(4,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(16,3)
        else              [b: 3]
Call 16*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 32768