sicp-ex-5.4

  
  
  
 (a) 
 (define expt-machine 
   (make-machine 
    '(b n r continue) 
    (list (list '= =) (list '* *) (list '- -)) 
    '((assign continue (label expt-done)) 
      expt-loop 
      (test (op =) (reg n) (const 0)) 
      (branch (label expt-base)) 
      (save continue) 
      (assign n (op -) (reg n) (const 1)) 
      (assign continue (label after-expt)) 
      (goto (label expt-loop)) 
      after-expt 
      (restore continue) 
      (assign r (op *) (reg r) (reg b)) 
      (goto (reg continue)) 
      expt-base 
      (assign r (const 1)) 
      (goto (reg continue)) 
      expt-done))) 
 (set-register-contents! expt-machine 'b 2) 
 (set-register-contents! expt-machine 'n 10) 
 (start expt-machine) 
  
 (get-register-contents expt-machine 'r) 
 => 1024 
  
 (b) 
 (define expt-machine 
   (make-machine 
    '(product b n product) 
      (assign product (const 1)) 
      expt-loop 
      (test (op =) (reg n) (const 0)) 
      (branch (label expt-done)) 
      (assign product (op *) (reg product) (reg b)) 
      (assign n (op -) (reg n) (const 1)) 
      (goto (label expt-loop)) 
      (goto (expt-loop)) 
      expt-done)) 
  
  

Recursive Exponentiation
========================

Controller:
-----------

  (controller
     (assign continue (label expn-done))
   test
     (test (op =) (reg n) (const 0))
     (branch (label base-case))
     (save continue)
     (assign continue (label after-expn))
     (assign n (op sub) (reg n) (const 1))
     (goto (label test))
   after-expn
     (restore continue)
     (assign p (op mul) (reg p) (reg b))
     (goto (reg continue))
   base-case
     (assign p (const 1))
     (goto (reg continue))
   expn-done)

Data-path:
----------

        ^    ┌───────┐      ^
       /0\   │   n   │     /1\
       ─┬─   └┬─────┬┘     ─┬─
        │     │  ^  │       │
        v     │  │  v       v
       ,─.    │  X ───────────
      ( = )<──┘  │  \  sub  /
       `─'       │   ───┬───
                 └──────┘

  ┌───────┐             ┌───────┐
  │   p   ├──┐       ┌──┤   b   │
  └───────┘  v       v  └───────┘
      ^     ───────────
      │      \  mul  /
      X       ───┬───
      └──────────┘

  ┌──────────┐       ┌──────────┐
  │ continue ├────X─>│   stack  │
  │          │<─X────┤          │
  └──────────┘       └──────────┘


Iterative Exponentiation
========================

Controller:
-----------

  (controller
   test
     (test (op =) (reg n) (const 0))
     (branch (label expn-done))
     (assign p (op mul) (reg p) (reg b))
     (assign n (op sub) (reg n) (const 1))
     (goto (label test))
   expn-done)

Data-path:
----------

        ^    ┌───────┐      ^
       /0\   │   n   │     /1\
       ─┬─   └┬─────┬┘     ─┬─
        │     │  ^  │       │
        v     │  │  v       v
       ,─.    │  X ───────────
      ( = )<──┘  │  \  sub  /
       `─'       │   ───┬───
                 └──────┘

  ┌───────┐             ┌───────┐
  │   p   ├──┐       ┌──┤   b   │
  └───────┘  v       v  └───────┘
      ^     ───────────
      │      \  mul  /
      X       ───┬───
      └──────────┘

https://drive.google.com/file/d/1EtHjkm2wZaJ8LCu_NULYSYh55XXtRTTQ/view?usp=sharing

This recursive controller uses only 3 registers.

;;;;;;;;;;
(controller
 (assign continue (label expt-done))
 (assign b (op read))
 (assign n (op read))
 expt-loop
 (test (op =) (const 0) (reg n))
 (branch (label base-case))
 (save continue)
 (assign continue (label after-expt))
 (assign n (op -) (reg n) (const 1))
 (goto (label expt-loop))
 after-expt
 (restore continue)
 (assign n (op *) (reg b) (reg n))
 (goto (reg continue))
 base-case
 (assign n (const 1))
 (goto (reg continue))
 expt-done
 (perform (op print) (reg n)))


(controller
 (assign b (op read))
 (assign counter (op read))
 (assign product (const 1))
 expt-loop
 (test (op =) (reg counter) (const 0))
 (branch (label expt-done))
 (assign counter (op -) (reg counter) (const 1))
 (assign product (op *) (reg b) (reg product))
 (goto (label expt-loop))
 expt-done)
 (perform (op print) (reg product)))