22 hours ago

my attempt to do the exercises in sicp.

## Saturday, June 28, 2008

### sicp exercise 1.22

; Exercise 1.22. Most Lisp implementations include a primitive called runtime that returns an integer

; that specifies the amount of time the system has been running (measured, for example, in microseconds).

; The following timed-prime-test procedure, when called with an integer n, prints n and checks to see

; if n is prime. If n is prime, the procedure prints three asterisks followed by the amount of time

; used in performing the test.

; (define (timed-prime-test n)

; (newline)

; (display n)

; (start-prime-test n (runtime)))

; (define (start-prime-test n start-time)

; (if (prime? n)

; (report-prime (- (runtime) start-time))))

; (define (report-prime elapsed-time)

; (display " *** ")

; (display elapsed-time))

; Using this procedure, write a procedure search-for-primes that checks the primality of consecutive

; odd integers in a specified range. Use your procedure to find the three smallest primes larger than

; 1000; larger than 10,000; larger than 100,000; larger than 1,000,000. Note the time needed to test

; each prime. Since the testing algorithm has order of growth of O(sqrt(n)), you should expect that testing

; for primes around 10,000 should take about sqrt(10) times as long as testing for primes around 1000.

; Do your timing data bear this out? How well do the data for 100,000 and 1,000,000 support the sqrt(n)

; prediction? Is your result compatible with the notion that programs on your machine run in time

; proportional to the number of steps required for the computation?

(define (runtime) (gettimeofday))

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

(define (smallest-divisor n)

(define (square number) (* number number))

(define (divides? n divisor) (= (remainder n divisor) 0))

(define (find-divisor n divisor)

(cond ((> (square divisor) n) n)

((divides? n divisor) divisor)

(else (find-divisor n (+ divisor 1)))))

(find-divisor n 2))

(define (prime? n) (= (smallest-divisor n) n))

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

;(timed-prime-test 3)

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

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment