Re: About srfi-58

[nalaginrut]

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