sicp-ex-5.4



<< Previous exercise (5.3) | Index | Next exercise (5.5) >>


meteorgan

  
  
  
 (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)) 
  
  

codybartfast




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       ───┬───
      └──────────┘


revc

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