[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: About srfi-58
From: |
nalaginrut |
Subject: |
Re: About srfi-58 |
Date: |
Mon, 24 Sep 2012 10:18:59 +0800 |
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