;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;       Ex1.19
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; recursive fib
(define (fib-rec n)
   (cond ((= n 0) 0)
         ((= n 1) 1)
         (else (+ (fib-rec (- n 1))
                  (fib-rec (- n 2)) ))))
; iterative fib
(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))
                    (+ (* 2 p q) (* q q))
                    (/ count 2)))
         (else (fib-iter (+ (* b q) (* a q) (* a p))
                         (+ (* b p) (* a q))
                         p
                         q
                         (- count 1)))))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;  Ex1.22
;;    You can test:
;;     (search-for-prime 1000 3)
;;     (search-for-prime 10000 3)
;;     (search-for-prime 100000 3)
;;     (search-for-prime 1000000 3) 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (timed-prime-test n)
   (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
   (if (prime? n)
       (begin
         (newline)
         (display n)
         (report-prime (- (runtime) start-time)))
       #f ))

(define (report-prime elapsed-time)
   (display " *** ")
   (display elapsed-time)
   #t )

(define (prime? x)
   (define (iter n bound)
      (if (> n bound)
          #t
          (if (= (modulo x n) 0)
              #f
              (iter (+ n 1) bound) ) ) )
   (iter 2 (sqrt x)) )

(define (search-for-prime x n)
   (cond ((even? x) (search-for-prime (+ x 1) n))
         ((> n 0)
          (if (timed-prime-test x)
              (search-for-prime (+ x 2) (- n 1))
              (search-for-prime (+ x 2) n) ) ) ) ) 


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;  Ex1.32
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; a. (recursive version)
(define (accumulate combiner null-value term a next b)
   (if (> a b)
       null-value
       (combiner (term a)
                 (accumulate combiner
                             null-value
                             term
                             (next a)
                             next
                             b ) ) ) )
(define (sum term a next b)
        (accumulate + 0 term a next b))
(define (product term a next b)
        (accumulate * 1 term a next b))

; b. (iterative version)
(define (accumulate-iter combiner null-value term a next b)
   (define (iter x result)
      (if (> x b)
          result
          (iter (next x) (combiner result (term x)) ) ) )
   (iter a null-value) )

(define (sum-iter term a next b)
        (accumulate-iter + 0 term a next b))
(define (product-iter term a next b)
        (accumulate-iter * 1 term a next b)) 


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;  Ex1.43
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (repeated f n)
   (lambda (x)
      (if (<= n 0)
          x
          ((repeated f (- n 1)) (f x)) ) ) )