since we see that the remainder went from to only in the example indeedthe remainder does not decrease by constant factor in one iteration howeverwe can prove that after two iterationsthe remainder is at most half of its original value this would show that the number of iterations is at most log (log nand establish the running time this proof is easyso we include it here it follows directly from the following theorem theorem if nthen mod / proof there are two cases if < / then since the remainder is smaller than nthe theorem is true for this case the other case is / but then goes into once with remainder / proving the theorem one might wonder if this is the best bound possiblesince log is about for our exampleand only seven operations were performed it turns out that the constant can be improved slightlyto roughly log nin the worst case (which is achievable if and are consecutive fibonacci numbersthe average-case performance of euclid' algorithm requires pages and pages of highly sophisticated mathematical analysisand it turns out that the average number of iterations is about ( ln ln )/ exponentiation our last example in this section deals with raising an integer to power (which is also an integernumbers that result from exponentiation are generally quite largeso an analysis works only if we can assume that we have machine that can store such large integers (or compiler that can simulate thiswe will count the number of multiplications as the measurement of running time the obvious algorithm to compute xn uses - multiplications recursive algorithm can do better < is the base case of the recursion otherwiseif is evenwe have xn xn/ xn/ and if is oddxn ( - )/ ( - )/ for instanceto compute the algorithm does the following calculationswhich involve only nine multiplications ( )xx ( xx ( xx ( xx ( the number of multiplications required is clearly at most log nbecause at most two multiplications (if is oddare required to halve the problem againa recurrence formula can be written and solved simple intuition obviates the need for brute-force approach figure implements this idea it is sometimes interesting to see how much the code can be tweaked without affecting correctness in figure lines to are actually unnecessarybecause if is then line does the right thing line can also be rewritten as return powxn