[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: About srfi-58

From: Mark H Weaver
Subject: Re: About srfi-58
Date: Fri, 21 Sep 2012 11:45:39 -0400
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:10.0.6esrpre) Gecko/20120817 Icedove/10.0.6

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))))))))


reply via email to

[Prev in Thread] Current Thread [Next in Thread]