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