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
Best wishes,
John
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
