## Re: 2 questions

Expand Messages
• ... Well, its certainly a lot more calculation than simply recording a 1 or 2 as each prime candidate in a long chain appears. PARI can check primality of
Message 1 of 27 , Apr 22, 2011
• 0 Attachment
--- In primenumbers@yahoogroups.com, "Phil" <philiplouisbewig@...> wrote:
>
> I discussed the Baillie-Wagstaff primality checker at my blog
> <http://programmingpraxis.com/2010/01/26/primality-checking-revisited/>
> . Here's the latest version of source code, in Scheme, which differs
> slightly from the original entry; it's more than "a few lines" of code,
> but not too long:
> (define (prime? n) (letrec ( (expm (lambda (b e m) (let ((times
> (lambda (x y) (modulo (* x y) m)))) (cond ((zero? e) 1) ((even?
> e) (expm (times b b) (/ e 2) m)) (else (times b (expm (times b b)
> (/ (- e 1) 2) m))))))) (digits (lambda (n) (let loop ((n n) (ds
> '())) (if (zero? n) ds (loop (quotient n 2) (cons (modulo n 2)
> ds)))))) (isqrt (lambda (n) (let loop ((x n) (y (quotient (+ n
> 1) 2))) (if (<= 0 (- y x) 1) x (loop y (quotient (+ y (quotient n
> y)) 2)))))) (square? (lambda (n) (let ((n2 (isqrt n))) (= n (* n2
> n2))))) (jacobi (lambda (a n) (let loop ((a a) (n n))
> (cond ((= a 0) 0) ((= a 1) 1) ((= a 2) (case (modulo n 8)
> ((1 7) 1) ((3 5) -1))) ((even? a) (* (loop 2 n) (loop (/ a
> 2) n))) ((< n a) (loop (modulo a n) n)) ((and
> (= (modulo a 4) 3) (= (modulo n 4) 3)) (- (loop n a)))
> (else (loop n a)))))) (inverse (lambda (x m) (let loop ((a 1) (b
> 0) (g x) (u 0) (v 1) (w m)) (if (zero? w) (modulo a m)
> (let ((q (quotient g w))) (loop u v w (- a (* q u)) (- b (* q
> v)) (- g (* q w)))))))) (strong-pseudo-prime? (lambda (n a) (let
> loop ((r 0) (s (- n 1))) (if (even? s) (loop (+ r 1) (/ s 2))
> (if (= (expm a s n) 1) #t (let loop ((r r) (s s))
> (cond ((zero? r) #f) ((= (expm a s n) (- n 1)) #t) (else
> (loop (- r 1) (* s 2)))))))))) (chain (lambda (m f g u v) (let
> loop ((ms (digits m)) (u u) (v v)) (cond ((null? ms) (values u
> v)) ((zero? (car ms)) (loop (cdr ms) (f u) (g u v)))
> (else (loop (cdr ms) (g u v) (f v))))))) (lucas-pseudo-prime? (lambda
> (n) (let loop ((a 11) (b 7)) (let ((d (- (* a a) (* 4 b))))
> (cond ((square? d) (loop (+ a 2) (+ b 1))) ((not (= (gcd
> n (* 2 a b d)) 1)) (loop (+ a 2) (+ b 2))) (else (let*
> ((x1 (modulo (- (* a a (inverse b n)) 2) n))
> (m (quotient (- n (jacobi d n)) 2)) (f
> (lambda (u) (modulo (- (* u u) 2) n))) (g
> (lambda (u v) (modulo (- (* u v) x1) n))))
> (let-values (((xm xm1) (chain m f g 2 x1)))
> (zero? (modulo (- (* x1 xm) (* 2 xm1)) n))))))))))) (if (not
> (integer? n)) (error 'prime? "must be integer") (if (< n 2) #f (if
> (even? n) (= n 2) (if (zero? (modulo n 3)) (= n 3) (and
> (strong-pseudo-prime? n 2) (strong-pseudo-prime? n 3)
> (lucas-pseudo-prime? n))))))))
>
>

Well, its certainly a lot more calculation than simply recording
a '1' or '2' as each prime candidate in a long chain appears.
PARI can check primality of 19-20 digit integers at a rate of
about 8000/sec, according to Maximillian, so I would expect
Praxis to be a bit slower. My primitive pm2 hit 11500/sec when
I put it into a Lazarus FreePascal compiler on a Pentium4, so I
feel it has potential. I would have to seriously upgrade my
programming skills to see how far the idea can really go
however. Somebody please shoot it down - my brain hurts!
Its pretty easy to check out even if Pascal is not your bag.