chap patterns of algorithms the cost of particular algorithm can decrease when increases in value (say when going from value of to to but generally increases when increases in length exponentiation we will start our examination of standard numerical algorithms by considering how to perform exponentiation that ishow do we compute mn we could multiply by total of times can we do betteryesthere is simple divide and conquer approach that we can use we can recognize thatwhen is evenmn mn/ mn/ if is oddthen mn mbn/ mbn/ this leads to the following recursive algorithm power(baseexpif exp return half power(baseexp/ )/integer division of exp half half halfif (odd(exp)then half half basereturn halfpower has recurrence relation = (nf (bn/ mod whose solution is (nblog nc ( where is the number of ' in the binary representation of how does this cost compare with the problem sizethe original problem size is log log nand the number of multiplications required is log this is far better (in factexponentially betterthan performing multiplications largest common factor we will next present euclid' algorithm for finding the largest common factor (lcffor two integers the lcf is the largest integer that divides both inputs evenly first we make this observationif divides and mthen divides we know this is true because if divides then ak for some integer aand if