some solutions for MIT Press's "structure and interpretation of computer programs", I guess
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

#### 59 lines 1.7 KiB Raw Permalink Blame History

 `;; chicken scheme doesn't provide a (runtime) primitive,` `;; and (current-milliseconds) is the best i could get` `(define (square x)` ` (* x x))` `(define (exptmod base expn m)` ` (cond ((= expn 0) 1)` ` ((even? expn)` ` (remainder` ` (square (exptmod base (/ expn 2) m))` ` m))` ` (else` ` (remainder` ` (* base (exptmod base (- expn 1) m))` ` m))))` `(define (fermat-test n)` ` (define (try-it a)` ` (= (exptmod a n n) a))` ` (try-it (+ 1 (random (- n 1)))))` `(define (fast-prime? n times)` ` (cond ((= times 0) #t)` ` ((fermat-test n) (fast-prime? n (- times 1)))` ` (else #f)))` `(define (timed-prime-test n)` ` (start-prime-test n (current-milliseconds)))` `(define (start-prime-test n start-time)` ` (if (fast-prime? n 10)` ` (report-prime n (- (current-milliseconds) start-time))))` `(define (search-for-primes min-bound max-bound)` ` (define (iter cur max-bound)` ` (if (<= cur max-bound) (timed-prime-test cur))` ` (if (<= cur max-bound) (iter (+ cur 2) max-bound)))` ` (iter (if (even? min-bound) (+ min-bound 1) min-bound)` ` (if (even? max-bound) (+ max-bound 1) max-bound)))` `(define (report-prime n elapsed-time)` ` (display n)` ` (display " *** ")` ` (display elapsed-time)` ` (newline))` `;; 1009 1.0, 1013 0.0, 1019 0.0` `;; 10007 1.0, 10009 0.0, 10037 1.0` `;; 100003 3.0, 100019 1.0, 100043 1.0` `;; 1000003 1.0, 1000033 1.0, 1000037 1.0` `;; the discrepancy in this particular implementation is caused by` `;; the fact that no matter what, you're testing it 10, 50, 100 times;` `;; obviously it'll be slower with a large number of times to run,` `;; no matter how efficient the algorithm is.` `;;` `;; the other implementation doesn't have this problem, due to the ` ```;; way it's implemented. ``` ``` ```