On 09/21/2012 04:32 AM, nalaginrut wrote:
hi guys!
I checked out the slib and realized most of the part of slib we do have
it in our core/modules.
Unfortunately, "prime" is not in the feature list of slib when I run
slib:feature. But I need it, then I try to port it to Guile directly.
If all you need is a probabilistic primality test, here's a simple
implementation of the Miller-Rabin test:
(set! *random-state* (random-state-from-platform))
(define* (prime? n #:key (trials 100))
(define n-1 (- n 1))
(define (composite-by-witness? a)
(let loop ((b (/ n-1 2)))
(and (not (= (modulo-expt a b n) n-1))
(if (odd? b)
(not (= (modulo-expt a b n) 1))
(loop (/ b 2))))))
(or (= n 2)
(and (> n 2)
(odd? n)
(let loop ((trials trials))
(or (zero? trials)
(and (not (composite-by-witness? (+ 1 (random n-1))))
(loop (- trials 1))))))))
Mark
