PPL (201-1289101)
Solution to HW1
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Question 1. Call: (targ1 b n)
;;
;; This version of exponentiation is iterative and takes time logarithmic in n
;;
(define (targ1 b n)
(exp-log-iter 1 b n ))
(define (exp-log-iter a b n)
(cond ((= n 0) a)
((even? n)
(exp-log-iter a (* b b) (/ n 2)))
(else (exp-log-iter (* a b) b (- n 1)))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Question 2. Transformation: p' = pp + qq; q' = qq + 2pq. Call: (fib n)
;;
;; This version of fib is iterative and takes time logarithmic in n.
;;
(define (fib n)
(fib_iter 1 0 0 1 n))
(define (fib_iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib_iter a
b
(+ (* p p) (* q q))
(+ (* q q) (* 2 p q))
(/ count 2)))
(else (fib_iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Question 3. Product & factorial
;;
;; recursive version of product
(define (product-r term a next b)
(if (< b a)
1
(* (term a) (product-r term (next a) next b))))
;; iterative version of product
(define (product-i term a next b)
(define (iter a result)
(if (< b a)
result
(iter (next a) (* result (term a)))))
(iter a 1))
;; Using product to compute factorial:
(define (identity x) x)
(define (fact-prod-i n)
(product-i identity 1 1+ n))
(define (fact-prod-r n)
(product-r identity 1 1+ n))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Question 4. Accumulate
;;
;; Accumulate is a generalization of sum and product.
;; iterative accumulate
(define (accumulate-i combiner null-value term a next b)
(define (acc-iter a result)
(if (< b a)
result
(acc-iter (next a) (combiner result (term a)))))
(acc-iter a null-value))
;; recursive accumulate
(define (accumulate-r combiner null-value term a next b)
(if (< b a)
null-value
(combiner (term a)
(accumulate-r combiner null-value term (next a) next b))))
;; Using accumulate to redefine sum
(define (sum-acc-i term a next b)
(accumulate-i + 0 term a next b))
(define (sum-acc-r term a next b)
(accumulate-r + 0 term a next b))
;; Using accumulate to redefine product
(define (prod-acc-i term a next b)
(accumulate-i * 1 term a next b))
(define (prod-acc-r term a next b)
(accumulate-r * 1 term a next b))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; That's all folks
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Last modified Mar 18th, 1997
Michael Elhadad