5 Chapter 5. Computing with Register Machines
5.1 Designing Register Machines
5.1.1 A Language for Describing Register Machines
5.1.1.1 Exercise 5.1
Design a register machine to compute factorials using the iterative algorithm specified by the following procedure. Draw data-path and controller diagrams for this machine.
(define (factorial n) (define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter 1)))) (iter 1 1))
Solution:
5.1.1.2 Exercise 5.2
Use the register-machine language to describe the iterative factorial machine of Exercise 5.1
Solution:
(controller |
(assign product (const 1)) |
(assign counter (const 1)) |
test-counter |
(test (op >) (reg counter) (reg n)) |
(branch (label factorial-done)) |
(assign product (op *) (reg product) (reg counter)) |
(assign counter (op +) (reg counter) (const 1)) |
(goto (label test-counter)) |
factorial-done) |
5.1.1.3 Exercise 5.3
Design a machine to compute square roots using Newton’s method, as described in 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.
;; simple version |
|
(controller |
(assign guess (const 1.0)) |
test-good-enough |
(test (op good-enough?) (reg guess) (reg x)) |
(branch (label sqrt-done)) |
(assign (op improve) (reg guess) (reg x)) |
(goto (label test-good-enough)) |
sqrt-done) |
|
;; expanded version |
|
(controller |
(assign guess (const 1.0)) |
(assign squared (op *) (reg guess) (reg guess)) |
(assign diff (op -) (reg squared) (reg x)) |
(assign absolute (op abs) (reg diff)) |
test-good-enough |
(test (op <) (reg absolute) (const 0.01)) |
(branch (label sqrt-done)) |
(assign quotient (op /) (reg x) (reg guess)) |
(assign sum (op +) (reg guess) (reg quotient)) |
(assign guess (op /) (reg sum) (const 2)) |
(goto (label test-good-enough)) |
sqrt-done) |