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
59 lines
1.7 KiB
;; 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.
|
|
|