; Exercise 1.23. The smallest-divisor procedure shown at the start of this section does lots of needless

; testing: After it checks to see if the number is divisible by 2 there is no point in checking to see

; if it is divisible by any larger even numbers. This suggests that the values used for test-divisor

; should not be 2, 3, 4, 5, 6, ..., but rather 2, 3, 5, 7, 9, .... To implement this change, define a

; procedure next that returns 3 if its input is equal to 2 and otherwise returns its input plus 2.

; Modify the smallest divisor procedure to use (next test-divisor) instead of (+ test-divisor 1).

; With timed-prime-test incorporating this modified version of smallest-divisor, run the test for each of

; the 12 primes found in exercise 1.22. Since this modification halves the number of test steps,

; you should expect it to run about twice as fast. Is this expectation confirmed? If not, what is the

; observed ratio of the speeds of the two algorithms, and how do you explain the fact that it is

; different from 2?

(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 (next num)(if (even? num) (+ num 1) (+ num 2)))

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

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

; testing: After it checks to see if the number is divisible by 2 there is no point in checking to see

; if it is divisible by any larger even numbers. This suggests that the values used for test-divisor

; should not be 2, 3, 4, 5, 6, ..., but rather 2, 3, 5, 7, 9, .... To implement this change, define a

; procedure next that returns 3 if its input is equal to 2 and otherwise returns its input plus 2.

; Modify the smallest divisor procedure to use (next test-divisor) instead of (+ test-divisor 1).

; With timed-prime-test incorporating this modified version of smallest-divisor, run the test for each of

; the 12 primes found in exercise 1.22. Since this modification halves the number of test steps,

; you should expect it to run about twice as fast. Is this expectation confirmed? If not, what is the

; observed ratio of the speeds of the two algorithms, and how do you explain the fact that it is

; different from 2?

(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 (next num)(if (even? num) (+ num 1) (+ num 2)))

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

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

## No comments:

Post a Comment