5.4 Exercise 5.4

A controller instruction sequence for recursive exponentiation:

(controller

(assign continue (label expt-done))

expt-loop

(test (op =) (reg n) (const 0))

(branch (label base-case))

(save continue)

(assign n (op -) (reg n) (const 1))

(save n)

(assign continue (label after-expt))

(goto (label expt-loop))

after-expt

(restore n)

(restore continue)

(assign val (op *) (reg b) (reg val))

(goto (reg continue))

base-case

(assign val (const 1))

(goto (reg continue))

expt-done)

A controller instruction sequence for iterative exponentiation:

(controller

(assign counter (reg n))

(assign product (const 1))

expt-iter

(test (op =) (reg counter) (const 0))

(branch (label after-expt))

(assign counter (op -) (reg counter) (const 1))

(assign product (op *) (reg b) (reg product))

(goto (label expt-iter))

after-expt

(assign val (reg product))

(goto (label expt-done))

expt-done)

As we’ve seen before, the recursive version will place vlaues for future work on the stack, rather than continually channeling them through the input values of the inner subroutine. However, the cost of doing this is now more explicit, because you can no longer rely on the implicit call stack to do this.