3 days ago

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 :(

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment