Re: About srfi-58

[Mark H Weaver]

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