1 665c255d 2023-08-04 jrmu ;; Exercise 1.18.  Using the results of exercises 1.16 and 1.17, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.40 
 2 665c255d 2023-08-04 jrmu 
 3 665c255d 2023-08-04 jrmu ;; invariant quantity
 4 665c255d 2023-08-04 jrmu ;; t + a * b = {
 5 665c255d 2023-08-04 jrmu ;;    t if b = 0
 6 665c255d 2023-08-04 jrmu ;;    t + 2 * a * (b/2) if b even
 7 665c255d 2023-08-04 jrmu ;;    (t+a) + a * (b-1) if b odd
 8 665c255d 2023-08-04 jrmu ;; }
 9 665c255d 2023-08-04 jrmu 
10 665c255d 2023-08-04 jrmu (define (fast-mult-iter a b t)
11 665c255d 2023-08-04 jrmu   (cond ((= b 0) t)
12 665c255d 2023-08-04 jrmu 	((even? b) (double fast-mult-iter a (halve b) t))
13 665c255d 2023-08-04 jrmu 	(else (fast-mult-iter a (- b 1) (+ t a)))))
14 665c255d 2023-08-04 jrmu 
15 665c255d 2023-08-04 jrmu (define (test-case actual expected)
16 665c255d 2023-08-04 jrmu   (load-option 'format)
17 665c255d 2023-08-04 jrmu   (newline)
18 665c255d 2023-08-04 jrmu   (format #t "Actual: ~A Expected: ~A" actual expected))
19 665c255d 2023-08-04 jrmu (test-case (fast-mult 0 0) 0)
20 665c255d 2023-08-04 jrmu (test-case (fast-mult 0 1) 0)
21 665c255d 2023-08-04 jrmu (test-case (fast-mult 0 8) 0)
22 665c255d 2023-08-04 jrmu (test-case (fast-mult 5 0) 0)
23 665c255d 2023-08-04 jrmu (test-case (fast-mult 2 1) 2)
24 665c255d 2023-08-04 jrmu (test-case (fast-mult 3 3) 9)
25 665c255d 2023-08-04 jrmu (test-case (fast-mult 5 4) 20)
26 665c255d 2023-08-04 jrmu (test-case (fast-mult 12 13) 156)
27 665c255d 2023-08-04 jrmu (test-case (fast-mult 12 24) 288)
28 665c255d 2023-08-04 jrmu 
29 665c255d 2023-08-04 jrmu 
30 665c255d 2023-08-04 jrmu