Most Lisp implementations include a primitive called
that returns an integer that specifies the amount of time the system has been running (measured, for example, in microseconds). The following
procedure, when called with an integer
and checks to see if
is prime. If it's 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
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 Θ(√n), you should expect that testing for primes around 10,000 should take about √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 √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?
There are no comments yet.
You must log in to post a comment.Login
;#lang racket/base ;(require rackunit) ;(require sicp) (define (square x) (* x x)) (define (smallest-divisor n) (find-divisor n 2)) (define (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (+ test-divisor 1))))) (define (divides? a b) (= (remainder b a) 0)) (define (prime? n) (= (smallest-divisor n) n)) (define (timed-prime-test n out) (newline) (display n out) (start-prime-test n (runtime) out)) (define (start-prime-test n start-time out) (if (prime? n) (report-prime (- (runtime) start-time) out))) (define (report-prime elapsed-time out) (display " *** " out) (displayln (floor elapsed-time) out)) (define op1 (open-output-string)) (search-for-primes 1 6 op1) (define display-result (get-output-string op1)) (check-equal? display-result "1 *** 0\n3 *** 0\n5 *** 0\n") (close-output-port op1)