• API
• FAQ
• Tools
• Archive
daily pastebin goal
2%
SHARE
TWEET

# Untitled

a guest Dec 12th, 2018 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. ;; 8/29/2012
2. ;; Matthew Jenkins - github.com/jenkinsm
3. ;; SICP - problem 1.18
4.
5. ;; Using the results of exercises 1.16 and 1.17, devise a procedure that
6. ;; generates an iterative process for multiplying two integers in terms of
7. ;; adding, doubling, and halving and uses a logarithmic number of steps.
8.
9. ;; to recap: here was our final procedure for problem 1.16
10.
11. (define (square n)
12.   (* n n))
13.
14. (define (even? n)
15.   (= (remainder n 2) 0))
16.
17. (define (expt-l b n)
18.   (expt-l-iter b n 1))
19.
20. (define (expt-l-iter b n a)
21.   (cond ((= n 0) a)
22.     ((even? n) (expt-l-iter (square b) (/ n 2) a))
23.     (else (expt-l-iter b (- n 1) (* a b)))))
24.
25. ;; and problem 1.17
26.
27. (define (double n)
28.   (* n 2))
29.
30. (define (halve n)
31.   (/ n 2))
32.
33. (define (fast-mult a b)
34.   (cond ((= b 0) 0)
35.     ((even? b) (double (fast-mult a (halve b))))
36.     (else (+ a (fast-mult a (- b 1))))))
37.
38. ;; and here's our iterative procedure.
39.
40. ;; question 1.16 states that a good way to think about iterative algorithms is
41. ;; to find an invariant quantity - in 1.16 it was a*b^n, here it is a*b+c.
42.
43. (define (log-mult a b)
44.   (log-iter-mult a b 0))
45.
46. (define (log-iter-mult a b c)
47.   (cond ((= b 1) (+ a c))
48.     ((even? b) (log-iter-mult (double a) (halve b)))
49.     (else (log-iter-mult a (- b 1) (+ c a)))))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top