Exercise 5.3. Design a machine to compute square roots using Newton’s method, as described in section 1.1.7:
(define (sqrt x)
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess)
(average guess (/ x guess)))
(define (sqrt-iter guess)
(if (good-enough? guess)
guess
(sqrt-iter (improve guess))))
(sqrt-iter 1.0))
Begin by assuming that good-enough? and improve operations are available as primitives. Then show how to expand these in terms of arithmetic operations. Describe each version of the sqrt machine design by drawing a data-path diagram and writing a controller definition in the register-machine language.
把 good-enough? 和 improve 当做原子操作的时候，我们可以如下画 data-path 图：
data-path diagram
+---+
| 1 |
+-+-+
|
v
+---+ -----------------
+---------->| g | --->( good-enough? )
| +-+-+ -----------------
| |
g<-t X v
| +-----------+
| \ improve /
| \---+---/
| |
| X t<-i
| v
| +---+
| | t |
| +-+-+
| |
+------------+这个图对应的语言描述为：
(controller
(assign (reg g) (const 1.0))
test-g
(test (op good-enough?) (reg g))
(branch (label done))
(assign (reg t) (op improve) (reg g))
(assign (reg g) (reg t))
(goto (label test-g))
done)
接下面，我们要把 good-enough? 用自己的方式来实现：
data-path diagram
+---+
| g |
+-+-+
|
v
----------
\ square /
+---+--+
|
v
+---+ ---------- +---+
| t1|-----> \ - / <-----| x |
+---+ +---+--+ +---+
v
+----+
| t2 |
+--+-+
v
----------
\ abs /
+--+---+
|
v
+----+
| t3 |
+-+--+
|
v
(<)
^
|
+---+---+
| 0.01 |
+-------+将上图的 g 与之前图中的 g 合并就可以得到最终的图了。相应的程序为：
(controller
(assign (reg g) (const 1.0))
test-g
; good-enough?
(assign (reg t1) (op square) (reg g))
(assign (reg t2) (op -) (reg t1) (reg x))
(assign (reg t3) (op abs) (reg t2))
(test (op <) (reg t3) (const 0.01))
(branch (label done))
(assign (reg t) (op improve) (reg g))
(assign (reg g) (reg t))
(goto (label test-g))
done)
再实现 improve（图略）：
(controller
(assign (reg g) (const 1.0))
test-g
; good-enough?
(assign (reg t1) (op square) (reg g))
(assign (reg t2) (op -) (reg t1) (reg x))
(assign (reg t3) (op abs) (reg t2))
(test (op <) (reg t3) (const 0.01))
(branch (label done))
; improve
(assign (reg t4) (op /) (reg x) (reg g))
(assign (reg t) (op average) (reg g) (reg t4))
(assign (reg g) (reg t))
(goto (label test-g))
done)