126 lines
3.6 KiB
Scheme
126 lines
3.6 KiB
Scheme
(import chicken.time) ; for current-milliseconds
|
|
(import chicken.random) ; for pseudo-random-integer
|
|
|
|
(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)
|
|
;(= n (smallest-divisor n)))
|
|
|
|
(define (square x) (* x x))
|
|
|
|
|
|
(define (timed-prime-test n)
|
|
;(newline)
|
|
;(display n)
|
|
(start-prime-test n (current-milliseconds)))
|
|
|
|
(define (start-prime-test n start-time)
|
|
(if (prime? n)
|
|
(report-prime n (- (current-milliseconds) start-time))))
|
|
|
|
(define (report-prime n elapsed-time)
|
|
(display n)
|
|
(display " *** ")
|
|
(display elapsed-time)
|
|
(newline))
|
|
|
|
|
|
(define (search-for-primes min max)
|
|
(if (<= min max)
|
|
(cond ((odd? min) (timed-prime-test min)
|
|
(search-for-primes (+ min 2) max))
|
|
(else (search-for-primes (+ min 1) max)))))
|
|
|
|
|
|
; (search-for-primes 100000 100100): First 3 take 1 ms each
|
|
; (search-for-primes 1000000 1000100): First 3 take 4, 3, 5 ms each
|
|
; (search-for-primes 10000000 10000200): First 3 take 14, 12, 13 ms each
|
|
|
|
; (sqrt 10) is 3.1622, so time increase is around sqrt(n), as expected.
|
|
|
|
|
|
(define (next n)
|
|
(if (= n 2)
|
|
3
|
|
(+ n 2)))
|
|
|
|
|
|
;(define (find-divisor n test-divisor)
|
|
;(cond ((> (square test-divisor) n) n)
|
|
;((divides? test-divisor n) test-divisor)
|
|
;(else (find-divisor n (next test-divisor)))))
|
|
|
|
; Now (search-for-primes 10000000 10000200): takes 7, 7, 10 ms each. So approximately
|
|
; half for the first two but a bit more for the third. This will be quicker, if the
|
|
; procedure has to search through lots of candidate divisors. Each call to next is
|
|
; more expensive that adding 1, which may account for the difference.
|
|
|
|
; Increase the size of the integers (to reduce noisy measurements):
|
|
; (search-for-primes 10000000000 10000000200)
|
|
; This takes ~141ms for the +1 case and ~87ms for the next case: A speedup of around
|
|
; 1.6. This must be accounted for by the extra comparison.
|
|
|
|
|
|
; 1.24
|
|
|
|
(define (fermat-test n)
|
|
(define (try-it a)
|
|
(= (expmod a n n) a))
|
|
(try-it (+ 1 (pseudo-random-integer (- n 1)))))
|
|
|
|
(define (expmod base exp m)
|
|
(cond ((= exp 0) 1)
|
|
((even? exp)
|
|
(remainder (square (expmod base (/ exp 2) m))
|
|
m))
|
|
(else
|
|
(remainder (* (expmod base (- exp 1) m) base)
|
|
m))))
|
|
|
|
(define (fast-prime? n times)
|
|
(cond ((= times 0) #t)
|
|
((fermat-test n) (fast-prime? n (- times 1)))
|
|
(else #f)))
|
|
|
|
(define (prime? n)
|
|
(fast-prime? n 10))
|
|
|
|
; Now prime test as above takes 2-3 ms for the first three answers
|
|
; (search-for-primes (square 10000000000) (+ 500 (square 10000000000)))
|
|
; This should be about double, given the the algorithm is logarithmic in time.
|
|
; We get 6, 8, 8 ms (more like 3 times as long). Maybe this is from the higher
|
|
; overhead of the random number generator? Or more likely, because we are running
|
|
; the Fermat test 10 times.
|
|
|
|
; 1.25: The answer should be the same if we take remainders after exponentiating,
|
|
; but exponentiating first keeps the numbers smaller, thus enabling testing of
|
|
; larger primes with less memory.
|
|
|
|
; 1.26: Writing out the multiplication instead of using square means that the
|
|
; argument is computed twice (once for each argument to * rather than once for
|
|
; square. So we are no longer halving the number of steps needed. Hence, this is
|
|
; no longer a log n algorithm.
|
|
|
|
; 1.27
|
|
|
|
; Test if a^n is congruent to a mod n for all a<n
|
|
|
|
(define (fermat n)
|
|
(define (fermat-rec a n)
|
|
(if (= a 1)
|
|
#t
|
|
(and (= (expmod a n n) a)
|
|
(fermat-rec (- a 1) n))))
|
|
(fermat-rec (- n 1) n))
|
|
|
|
|