6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 4.3.15 We know that when the counter gets down to zero, there are no Iterative algorithm to compute abas a table more multiplications to do, so we are done. And when we get In this ta there, the answer is in the product column One column for each piece of information used The last row is the one where counter =0 The answer is in the product column of the last row Iterative algorithm to compute a b as a table Slide 4.3.1 And finally, we see that the starting point is just that anything to In this table One column for each piece of information used the zeroth power is 1 first row handles a product counter a cleanly he last row is the one where counter o f aue answer is in the product column of the last row 8M200 6001 SICP Slide 4.3.17 Iterative algorithm to compute a b So now we can capture this in a procedure. As with factorial, we are going to use a helper procedure And ( define exp-i (lambda (a b)(exp-i-help 1 b a))) as in that case, we can see that this procedure checks for a base (define exp-i-help case,and if there, just returns the value of prod. Otherwise, it (lambda (prod count a) reduces the computation to a simpler version of the same t 0) computation, with a new value for prod and a new value for count, both obtained by using the update rules we just saw (exp-i-help ( prod a)(- count 1)a)))) 1 001 SICP Iterative algorithm to compute a b Slide 43.18 Orders of growth And what is the order of growth here? In time, this is still linear, as there is one subcomputation to perform for each Space e(1)-constant increment in the size of b. In space, however, we again see that there are no deferred operations here, so this is constant Thus, just as with factorial, we see that we can create different procedures to compute exponentiation, with different classes of behaviors 1001 SICP6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 4.3.15 We know that when the counter gets down to zero, there are no more multiplications to do, so we are done. And when we get there, the answer is in the product column. Slide 4.3.16 And finally, we see that the starting point is just that anything to the zeroth power is 1. Slide 4.3.17 So now we can capture this in a procedure. As with factorial, we are going to use a helper procedure. And as in that case, we can see that this procedure checks for a base case, and if there, just returns the value of prod. Otherwise, it reduces the computation to a simpler version of the same computation, with a new value for prod and a new value for count, both obtained by using the update rules we just saw. Slide 4.3.18 And what is the order of growth here? In time, this is still linear, as there is one subcomputation to perform for each increment in the size of b. In space, however, we again see that there are no deferred operations here, so this is constant. Thus, just as with factorial, we see that we can create different procedures to compute exponentiation, with different classes of behaviors