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. OK, I Understand
 
Top