Actually, I "cheated". Before applying DMR, I do trial division for 2 3 5 7 (I must do trial division by 2 anyway), thereby removing 77% of random candidates from further consideration. On further thought, 2 3 5 may be better as those already get it up to 73%.
BTW, the 9.49e7 magic number is not accidental. (consider *:9.49e7). ----- Original Message ----- From: John Randall <[EMAIL PROTECTED]> Date: Tuesday, November 11, 2008 11:34 Subject: Re: [Jprogramming] Miller-Rabin primality test To: Programming forum <[email protected]> > Roger Hui wrote: > > 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 > > Interesting result. I would have guessed v1, but not v0. > > Given that most random numbers are composite with small factors > (about 75% > are divisible by 2, 3 or 5), one might have thought trial > division would > do better in this case. Presumably if the smallest prime > factor of a > number is large, trial division will do much worse than I would have > imagined. > > Best wishes, > > John > > > ----------------------------------------------------------------- > ----- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
