I did an implementation of deterministic Miller-Rabin
on limited range integers (<9.49e7) and obtained the
following timings compared to trial division:
v0=: 87654321 + 2e5 [EMAIL PROTECTED] 4e6 NB. random integers
v1=: p: 5e6+2e5 [EMAIL PROTECTED] 3e5 NB. random primes
v0 v1
trial div. 0.228147 3.16518
DMR 0.102935 0.68829
----- Original Message -----
From: Roger Hui <[EMAIL PROTECTED]>
Date: Monday, November 3, 2008 21:32
Subject: Re: [Jprogramming] Miller-Rabin primality test
To: Programming forum <[email protected]>
> huo=: <[EMAIL PROTECTED]:^:(0=2&|)^:a: NB. halve until odd
>
> NB. magic numbers from http://primes.utm.edu/prove/prove2_3.html
> witnesses=: 4 : 0
> r=. 9080191 4759123141 2152302898747 3474749600383
> 341550071728321x if. y>:{:r do.
> 1+x [EMAIL PROTECTED] y-1
> else.
> ((r-1) I. y){:: 31 73 ; 2 7 61 ; 2 3 5 7 11 ; 2 3 5 7 11
> 13 ; 2 3 5 7 11 13 17
> end.
> )
>
> NB. Miller-Rabin primality test
> NB. deterministic for y< {:r (3.4e14) in witnesses;
> probabilistic for y>:{:r (0 answer is always correct;
> NB. 1 answer is wrong with error probability at most 0.25^x)
>
> MillerRabin=: 100&$: : (4 : 0) " 0
> if. 0=2|y do. 2=y return. end.
> if. 74>y do. y e. i.&.(p:^:_1) 74 return. end.
> e=. huo y-1
> for_a. x witnesses y do. if. (+./c=y-1) +: 1={:c=. a y&|@^
> e do. 0 return. end. end.
> 1
> )
>
> -----------------------------------------------------------------
> -----
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
