# weima learns to program

my attempt to do the exercises in sicp.

## Saturday, June 28, 2008

### sicp exercise 1.24

;  Exercise 1.24. Modify the timed-prime-test procedure of exercise 1.22 to use fast-prime? (the Fermat
;  method), and test each of the 12 primes you found in that exercise. Since the Fermat test has O(log n)
;  growth, how would you expect the time to test primes near 1,000,000 to compare with the time needed
;  to test primes near 1000? Do your data bear this out? Can you explain any discrepancy you find?

(define (runtime) (gettimeofday))
(define (difftime start end)
(+
(*
(- (car end) (car start))
100000)
(- (cdr end) (cdr start))))

(define (square num) (* num num))

(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m)) m))
(else
(remainder (* base (expmod base (- exp 1) m)) m))))

(define (prime? n)
(define (prime-impl n base)
(= (expmod base n n) base))
(prime-impl n (random (- n 1))))

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

(define (start-prime-test n start-time)
(if (prime? n)
(report-prime n (difftime start-time (runtime)))
#f))

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

(define (search-for-primes start end max)
(define (search-for-primes-impl start count)
(cond ((> start end) 0)
((= count max) 0)
(else (if (timed-prime-test start)
(search-for-primes-impl (+ start 1) (+ count 1))
(search-for-primes-impl (+ start 1) count)))))
(search-for-primes-impl start 0))

(search-for-primes   1000   10000 3)
(search-for-primes  10000  100000 3)
(search-for-primes 100000 1000000 3)

; the time taken to find the 12 primes is lower than the time taken in problems 1.23 and 1.22.
; But i dont find any discrepency, as asked in this problem :(