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
