[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))))))))
Mark
- About srfi-58, nalaginrut, 2012/09/21
- Re: About srfi-58,
Mark H Weaver <=