sicp-ex-5.3



<< Previous exercise (5.2) | Index | Next exercise (5.4) >>


meteorgan

  
  
 (define sqrt-machine 
   (make-machine 
    '(x guess temp) 
    (list (list '- -) (list '< <) (list '/ /) (list '+ +) (list '* *) (list '> >)) 
    '((assign guess (const 1.0)) 
     test-g 
     (assign temp (op *) (reg guess) (reg guess)) 
     (assign temp (op -) (reg temp) (reg x)) 
     (test (op >) (reg temp) (const 0)) 
     (branch (label iter)) 
     (assign temp (op -) (const 0) (reg temp)) 
     iter 
     (test (op <) (reg temp) (const 0.001)) 
     (branch (label sqrt-done)) 
     (assign temp (op /) (reg x) (reg guess)) 
     (assign temp (op +) (reg temp) (reg guess)) 
     (assign guess (op /) (reg temp) (const 2)) 
     (goto (label test-g)) 
     sqrt-done))) 
 (set-register-contents! sqrt-machine 'x 2) 
 (start sqrt-machine) 
  
 (get-register-contents sqrt-machine 'guess) 
 =>1.4142156862745097 
  
  
 ;; 1. assuming that good-enough? and improve are primtives 
  
 (controller 
  (assign x (op read)) 
  (assign guess (const 1.0)) 
  
  test-good 
  (test (op good-enough?) (reg guess) (reg x)) 
  (branch (label done)) 
  (assign t (op improve) (reg guess) (reg x)) 
  (assign guess (reg t)) 
  (goto test-good) 
  done 
  
  (perform (op print) (reg guess)) 
  ) 
  
 ;; 2. inline improve 
  
 (controller 
  (assign x (op read)) 
  (assign guess (const 1.0)) 
  
  test-good 
  (test (op good-enough?) (reg guess) (reg x)) 
  (branch (label done)) 
  
  ;; improve procedure 
  (assign div (op /) (reg x) (reg guess)) 
  (assign avg (op average) (reg guess) (reg div)) 
  
  (assign t (reg avg)) 
  (assign guess (reg t)) 
  (goto test-good) 
  done 
  
  (perform (op print) (reg guess)) 
  ) 
  
 ;; 2a inline average 
 (controller 
  (assign x (op read)) 
  (assign guess (const 1.0)) 
  
  test-good 
  (test (op good-enough?) (reg guess) (reg x)) 
  (branch (label done)) 
  
  ;; improve procedure 
  (assign div (op /) (reg x) (reg guess)) 
  
  ;; average procedure 
  (assign sum (op +) (reg guess) (reg div)) 
  (assign avg (op /) (reg sum) (const 2)) 
  
  (assign t (reg avg)) 
  (assign guess (reg t)) 
  (goto test-good) 
  done 
  
  (perform (op print) (reg guess)) 
  ) 
  
 3. inline good-enough? 
 (controller 
  (assign x (op read)) 
  (assign guess (const 1.0)) 
  
  test-good 
   
  ;; good-enough? procedure 
  (assign square (op *) (reg guess) (reg guess)) 
  (assign diff (op -) (reg square) (reg x)) 
  (test (op <) (reg diff) (const 0)) 
  (branch test-abs-neg) 
  test-abs-pos 
  (assign abs (reg diff)) 
  test-abs-neg 
  (assign abs (op *) (reg diff) (const -1)) 
  (test (op <) (reg abs) (const 0.001)) 
  
  (branch (label done)) 
  
  ;; improve procedure 
  (assign div (op /) (reg x) (reg guess)) 
  ;; average procedure 
  (assign sum (op +) (reg guess) (reg div)) 
  (assign avg (op /) (reg sum) (const 2)) 
  
  (assign t (reg avg)) 
  (assign guess (reg t)) 
  (goto test-good) 
  done 
  
  (perform (op print) (reg guess)) 
  ) 


codybartfast




With good-enough? And improve
=============================

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

  ┌───────┐
  │   x   ├──────────┐
  └───────┘          │
                     │
                     │
      ^              │
     / \             ├───────┐
    /   \            │       │
   /0.001\           v       │
   ───┬───          ,─.      │
      └───────────>(g-e)     │
                    `─'      │
                     ^       │
  ┌───────┐          │       │
  │   g   ├──────────┤       │
  └───────┘          │       │
      ^              V       V
      │             ───────────
      X g<-imp       \  imp  /
      │               ───┬───
      └──────────────────┘

Controller Diagram:
-------------------

  ┌───────┐
  │       v
  │       ^
  │      / \ yes
  │     (g-e)───> done
  │      \ /
  │       V
  │       │
  │       │ no
  │       v
  │  ┌─────────┐
  │  │  g<-imp │
  │  └────┬────┘
  └───────┘

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

  (controller
   test-g-e
     (test (op g-e) (reg g) (reg x) (const 0.001))
     (branch (label sqrt-done))
     (assign g (op imp) (reg g) (reg x))
     (goto (label test-g-e))
   sqrt-done)


Arithmetic Only
===============

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

                     ┌──────────────┐            ┌───────┐
                     │          ┌───┴───┐        │   t   │
                     │          v       v        └─────┬─┘
                     │         ───────────         ^   │
                     │          \  mul  /          │   │
                     │           ───┬───    t<-mul │   │
                     │              └────────────X─┤   │
                     │                             │   │
  ┌───────┐          │                             │   │
  │   x   ├───┬───── │ ─────────┐       ┌───────── │ ──┤
  └───────┘   │      │          v       v          │   │
              │      │         ───────────         │   │
              │      │          \  sub  /          │   │
              │      │           ───┬───    t<-sub │   │
              │      │              └────────────X─┤   │
              │      │                             │   │
              │      │       ^                     │   │
              │      │      /0\                    │   │
              │      │      ─┬─                    │   │
              │      │       │     ,─.             │   │
              │      │       ├───>( < )<────────── │ ──┤
              │      │       │     `─'             │   │
              │      │       │                     │   │
              │      │       │                     │   │
              │      │       └──┐       ┌───────── │ ──┤
              │      │          v       v          │   │
              │      │         ───────────         │   │
              │      │          \  sub  /          │   │
      ^       │      │           ───┬───   t<-sub0 │   │
     / \      │      │              └────────────X─┤   │
    /   \     │      │                             │   │
   /0.001\    │      │                             │   │
   ───┬───    │      │             ,─.             │   │
      └────── │ ──── │ ──────────>( > )<────────── │ ──┤
              │      │             `─'             │   │
              │      │                             │   │
              │      │                             │   │
              │      ├──────────────────┐          │   │
              │      │                  │          │   │
              └───── │ ─────────┐       │          │   │
                     │          V       V          │   │
                     │         ───────────         │   │
                     │          \  div  /          │   │
                     │           ───┬───    t<-div │   │
                     │              └────────────X─┤   │
                     │                             │   │
  ┌───────┐          │                             │   │
  │   g   ├──────────┴──────────┐       ┌───────── │ ──┤
  └───────┘                     v       v          │   │
      ^                        ───────────         │   │
      │                         \  add  /          │   │
      X g<-div                   ───┬───    t<-add │   │
      │                             └────────────X─┘   │
      │                                                │
      │                         ┌──────────────────────┘
      │                         │
      │                         │       ^
      │                         │      /2\
      │                         │      ─┬─
      │                         V       V
      │                        ───────────
      │                         \  div  /
      │                          ───┬───
      └─────────────────────────────┘

Controller Diagram:
-------------------

  ┌───────┐
  │       v
  │  ┌─────────┐
  │  │  t<-mul │
  │  └────┬────┘
  │       │
  │       v
  │  ┌─────────┐
  │  │  t<-sub │
  │  └────┬────┘
  │       │
  │       v
  │       ^
  │      / \ yes
  │     ( < )─────┐
  │      \ /      │
  │       V       │
  │       │       │
  │       │ no    │
  │       v       │
  │  ┌─────────┐  │
  │  │ t<-sub0 │  │
  │  └────┬────┘  │
  │       ├───────┘
  │       │
  │       v
  │       ^
  │      / \ yes
  │     ( > )───> done
  │      \ /
  │       V
  │       │
  │       │ no
  │       v
  │  ┌─────────┐
  │  │  t<-div │
  │  └────┬────┘
  │       │
  │       v
  │  ┌─────────┐
  │  │  t<-add │
  │  └────┬────┘
  │       │
  │       v
  │  ┌─────────┐
  │  │  g<-div │
  │  └────┬────┘
  └───────┘

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

  (controller
   test-g-e
     (assign t (op mul) (reg g) (reg g))
     (assign t (op sub) (reg x) (reg t))
     (test (op <) (const 0) (reg t))
     (branch (label test-g-e-final))
     (assign t (op sub) (const 0) (reg t))
   test-g-e-final
     (test (op >) (const 0.001) (reg t))
     (branch (label sqrt-done))
     (assign t (op div) (reg x) (reg g))
     (assign t (op add) (reg g) (reg t))
     (assign g (op div) (reg t) (const 2))
     (goto (label test-g-e))
   sqrt-done)