PPL (201-1289101)

Solution to HW1

Questions Back to Course Home Page

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; 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