About srfi-58

About srfi-58

[nalaginrut]

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.

And I encountered something "A:fixN32b" can't be found. I think this
"prime" needs srfi-58. But I remember Guile has it's own array
notations, srfi-58 will introduce another one.

So let me raise a topic about the proper implementation of srfi-58. If
we have something useful in this thread, we may do it.
In my opinion, we have to add a global variable to check if the user
used srfi-58, and scm_read_array could call a brand new
scm_i_srfi_58_read_array if it's true. 
But I don't think introduce a global variable is a good way. Maybe add
new read-opts is better? And if we do it in the C level, it's not so
interesting to implement the array parser. 

Anyone provide better solution? Any other consideration about srfi-58 is
welcome. ;-)

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

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