[plt-scheme] Implementing Rabin-Miller

From: Eli Barzilay (eli at barzilay.org)
Date: Tue Oct 15 15:31:16 EDT 2002

On Oct 15, John Clements wrote:
> On Tuesday, October 15, 2002, at 04:09  PM, Paulo Jorge O. C. Matos 
> wrote:
> > (1)  Choose a random number, a, such that a is less than p.
> > (2)  Set j = 0 and set z = am mod p.
> > (3)  If z = 1, or if z = p - 1, then p passes the test and may be 
> > prime. (4)  If j > 0 and z = 1, then p is not prime.
> > (5)  Set j = j + 1. If j < b and z ? p - 1, set z = z2 mod p and go 
> > back to step (4). If z = p - 1, then p passes the test and may be 
> > prime.
> > (6)  If j = b and z ? p - 1, then p is not prime.
> >
> This looks like a terrible specification of an algorithm. Rewrite it
> like this:
> [...]
> Due to a dreadful spec, I may be off in the boundary condition for
> j.  Frankly, it might be easier to read in scheme:

I disagree with that "might" in the last sentence -- I think that it
is very definitely easier.  This is the same story over and over
again: I keep finding people who didn't learn to be proper programmers
and then describe algorithms using some semi-imperative, mostly vague
descriptions.  This is just like so many situations where a simple
algorithm is turned inside-out, statements shuffled around, just so
the whole thing can be implemented with "dynamic programming" -- when
the original plain algorithm is so much clearer with a simple
memoization slapped on.  I see this continuously in my wife's work:
she just has to describe the simple *memoized* algorithm using
*dynamic programming*, the latter gets the "Oooh!" effect while the
former is mostly unknown at best (usually disregarded as a typo).
There are also the theory guys -- people who will teach you the
insides of the concepts of computations using Turing Machines -- all
with diagrams that get more and more exotic with little arrows for
"yes" and "no" results, and crappy descriptions of connecting N
machines in parallel with "and" and "or" switches.  When they get
someone who shows them that the whole thing can be explained much
better (in almost every metric -- short, precise, simple), then they
might get impressed for a microsecond but eventually file the incident
under a "software engineering issue".

For the sake of being on-topic, just so it doesn't look like good
programmers try to avoid gotos: it is possible.  For example, the
piece of syntax below makes this work --

  > (let ((x #f))
        (set! x 0)
        (goto start:)
        (set! x 99)
          (goto (if (even? x) even: odd:))
          (printf "even: ")
          (printf ">>> ~s\n" x)
          (set! x (add1 x))
          (when (> x 10) (goto end:))
          (goto start:)
  even: >>> 0
  >>> 1
  even: >>> 2
  >>> 3
  even: >>> 4
  >>> 5
  even: >>> 6
  >>> 7
  even: >>> 8
  >>> 9
  even: >>> 10

The code looks complex but it's quite simple.  The only value I
personally see in it is to study how it manages the labels and gotos.
Otherwise, it is a bad idea.  Anyway, here it is:

(define-syntax (with-gotos stx)
  (syntax-case stx ()
    ((_ body ...)
     (let loop ((code (syntax->list #'(body ...))) (blocks '()) (current #f))
        ((null? code)
         (let* ((goto (datum->syntax-object stx 'goto stx))
                 (let loop ((bs   (if current (cons current blocks) blocks))
                            (next #f)
                            (r    '()))
                   (if (null? bs)
                     (let ((b (reverse
                               (if next
                                 (cons #`(#,goto #,next) (car bs)) (car bs)))))
                       (loop (cdr bs) (car b)
                             (cons (if (null? (cdr b)) (list (car b) #'#f) b)
           #`((let/cc #,goto
                (letrec #,(map (lambda (block)
                                 #`(#,(car block) (lambda () #,@(cdr block))))
                  #,(caar blocks))))))
        ((identifier? (car code))
         (loop (cdr code)
               (if current (cons current blocks))
               (list (car code))))
         (loop (cdr code)
               (if current
                 (cons (car code) current)
                 (list (car code) (car (generate-temporaries

          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                  http://www.barzilay.org/                 Maze is Life!

Posted on the users mailing list.