hi Mark! Thanks for reply! The prime algorithm is good to me. :-) But do you think we may take this chance to add srfi-58 incidentally?
On Fri, 2012-09-21 at 11:45 -0400, Mark H Weaver wrote: > 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
