Expositional clarity before efficiency. As it is, a factor of 2.5 is barely worth it.
----- Original Message ----- From: John Randall <[EMAIL PROTECTED]> Date: Wednesday, November 5, 2008 9:16 Subject: [Jprogramming] Primality testing To: 'Programming forum' <[email protected]> > The methods in > > http://www.jsoftware.com/jwiki/Essays/Primality_Tests > > seem mainly scalar. Is it possible to do better with > vector versions? My > initial attempt to do this for trial division suggests that it is. > > > time=:6!:2 > > TrialDiv=: 3 : 0 " 0 > for_p. i.&.(p:^:_1) (%:+2&<) y<.2^31 do. > if. 0=p|y do. 0 return. end. > end. > (1<y)*_1^y>2^31 > ) > > tda1=:-.@:(+./)@:((0=|)"0/) &.>/ > > tda=:3 : 0"1 > perm=./: y > q=./:~ y > np=._1&p: (%:+2&<) q > r=.(p:@i. &.> ~.np),. np </. q > (/: perm) { (q>1) *. ; tda1"1 r > ) > > Here tda does trial division on a vector by sorting its argument > and then > grouping it by primes to be checked. The results are > assembled in the > original order using the remembered permutation perm. > > n=:10000 [EMAIL PROTECTED] 10000 > time 'TrialDiv n' > 0.263127 > time 'tda n' > 0.105279 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
