## [REBOL] Re: Speed testing prime functions..

### From: joel:neely:fedex at: 28-Nov-2001 13:16

Hi, James, (Telecommuting from home with sinus infection, but can't resist the good ol' primes... ;-) James Marsden wrote:> Hi to all the prime lovers out there :) > > Could someone give me some feedback on the fastest way to implement prime > checks in Rebol - > > Currently I use: > > prime?: func [p /local c v][ > v: true > for c 2 (p - 1) 1 [ > if p // c = 0 [v: false break] > ] > v > ] >A few suggestions right off (ASSUMING THAT ALL CANDIDATES ARE >= 2): 1) The local word V is superfluous, as follows: prime?: func [p /local c] [ for c 2 (p - 1) 1 [ if p // c = 0 [return false] ] true ] 2) After testing 2, there's no point in checking for any other even divisors, as follows: prime?: func [p /local c] [ if p // 2 <> 0 [ for c 3 (p - 1) 2 [ if p // c = 0 [return false] ] return true ] ] Note the trick that IF yields NONE if its condition is false. That return value counts as false for primality. 3) Consider the fact that a divisor less than the square root of a number gives a quotient that is greater than the square root. Therefore, there's no point in continuing after passing the square root of the candidate, as follows: prime?: func [p /local c] [ if p // 2 <> 0 [ c: 3 while [c * c <= p] [ if p // c = 0 [return false] c: c + 2 ] return true ] ] Hint: try a before-and-after with a larger prime, such as 1000003 to see the difference. 4) After testing 3, there's no point in checking for any other multiples of 3. This one gets a bit obscure-looking, as we don't want any superfluous division. Consider the odds: 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 ... XX XX XX XX xx where multiples of 3 are x-ed out, and notice that we can step from 5 alternately by 2 and 4 to get the ones that are left. prime?: func [p /local c s] [ if p // 2 <> 0 [ if p = 3 [return true] ;; below only works for >= 5 if p // 3 <> 0 [ c: 5 s: 4 while [c * c <= p] [ if p // c = 0 [return false] c: c + s: 6 - s ] return true ] ] ] Of course, the more we hack up the function for these kinds of optimizations, the larger our candidate has to be to provide a real payback on the bulkier code. One last hack (left as an exercise for the reader... ;-) is to save all primes previously found, and use only known primes as trial divisors. Of course the candidate list must be extended with new trial divisors whenever it is not long enough, but only saving the prime ones (hint: recursion). This *OBVIOUSLY* requires that the function be used many times within a single session to pay off the setup costs. HTH! -jn- -- ; sub REBOL {}; sub head ($) {@_[0]} REBOL [] # despam: func [e] [replace replace/all e ":" "." "#" "@"] ; sub despam {my ($e) = @_; $e =~ tr/:#/.@/; return "\n$e"} print head reverse despam "moc:xedef#yleen:leoj" ;