Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

Speed testing prime functions..

 [1/11] from: james::mustard::co::nz at: 29-Nov-2001 7:36


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 ] Is there a better way to do this? I have seen another implementation but that was about 60 or so lines and seemed slower... James.

 [2/11] 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
<<quoted lines omitted: 7>>
> 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" ;

 [3/11] from: tomc:darkwing:uoregon at: 28-Nov-2001 11:28


Hi James, seemed slower... hmmm, on what size number? how about running them both on... say 1073741789 you might want to run the other one first :) On Thu, 29 Nov 2001, James Marsden wrote:

 [4/11] from: joel:neely:fedex at: 28-Nov-2001 13:28


Oooops... (I *said* I was under the weather! ;-) Joel Neely wrote:
Since 2 is prime, an initial bailout check is needed for that case (as I *did* catch for 3 in the fourth round of optimization)...
> 2) After testing 2... > > prime?: func [p /local c] [
if p = 2 [return true]
> if p // 2 <> 0 [ > for c 3 (p - 1) 2 [
<<quoted lines omitted: 5>>
> 3) Consider the fact that a divisor less than the square root of... > prime?: func [p /local c] [
if p = 2 [return true]
> if p // 2 <> 0 [ > c: 3
<<quoted lines omitted: 7>>
> 4) After testing 3, there's no point in checking for any other... > prime?: func [p /local c s] [
if p = 2 [return true]
> if p // 2 <> 0 [ > if p = 3 [return true] ;; below only works for >= 5
<<quoted lines omitted: 8>>
> ] > ]
-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" ;

 [5/11] from: james:mustard at: 29-Nov-2001 8:45


Heh - I must admit I was testing it on relatively small primes - With what Joel sent in I'll have a bit of a redefine. The project only involves lower order primes currently but with larger primes my original equation is definitely slow :) James.

 [6/11] from: joel:neely:fedex at: 28-Nov-2001 13:51


Hi, all ...further feverish notes to self... Joel Neely wrote:
I believe that using zero? foo is the tiniest bit faster than foo = 0 but that's probably insignificant...
> 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, I should have said that the last hack is to save all prime *trial*divisors* previously found, since the memoized list of divisors must be ordered and without gaps. To atone for my poor phraseology, I'll submit the following for scrutiny (and, as always, corrections, tweaks, etc.) use [d] [ d: [2 3 5 7] prime?: func [p /local c s] [ if found? find d p [return true] foreach v d [ if zero? p // v [return false] if v * v > p [return true ] ] either zero? s: (c: 2 + last d) // 3 [ c: c + 2 s: 4 ][ s: s + s ] while [c * c <= p] [ if prime? c [ append d c if zero? p // c [return false] ] c: c + s: 6 - s ] return true ] ] -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" ;

 [7/11] from: tomc:darkwing:uoregon at: 28-Nov-2001 12:59


Hi James, how small or lower order? how often will you need to call it? my argument against seive / brute force methods is you end up gaining information about numbers along the way that you may not have any use for. if your largest prime is small enough you could try loading or generating a list of primes and do a binary search (or just use find) On Thu, 29 Nov 2001, James Marsden wrote:

 [8/11] from: lmecir:mbox:vol:cz at: 28-Nov-2001 23:10


Hi Joel, <<Joel>> I believe that using zero? foo is the tiniest bit faster than foo = 0 <</Joel>> your assumption is wrong, at least here. <<Joel>>
> 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, I should have said that the last hack is to save all prime *trial*divisors* previously found, since the memoized list of divisors must be ordered and without gaps. To atone for my poor phraseology, I'll submit the following for scrutiny (and, as always, corrections, tweaks, etc.) use [d] [ d: [2 3 5 7] prime?: func [p /local c s] [ if found? find d p [return true] foreach v d [ if zero? p // v [return false] if v * v > p [return true ] ] either zero? s: (c: 2 + last d) // 3 [ c: c + 2 s: 4 ][ s: s + s ] while [c * c <= p] [ if prime? c [ append d c if zero? p // c [return false] ] c: c + s: 6 - s ] return true ] ] -jn- <</Joel>> The following versions will be faster: prime?: function [p] [c s l] [ if p // 2 = 0 [return p = 2] if p // 3 = 0 [return p = 3] l: to integer! square-root p c: 5 s: 4 while [c <= l] [ if p // c = 0 [return false] c: c + s: 6 - s ] true ] use [d] [ d: [2 3 5 7] prime?: function [p] [c s l] [ l: to integer! square-root p foreach v d [ if p // v = 0 [return p = v] if v >= l [return true] ] c: (last d) + 6 - s: (last d) // 3 * 2 while [c <= l] [ if prime? c [ append d c if p // c = 0 [return false] ] c: c + s: 6 - s ] true ] ]

 [9/11] from: lmecir:mbox:vol:cz at: 29-Nov-2001 0:06


Hello, wrong order of sets in my formula: use [d] [ d: [2 3 5 7] prime?: function [p] [c s l] [ l: to integer! square-root p foreach v d [ if p // v = 0 [return p = v] if v >= l [return true] ] c: (last d) + s: 6 - ((last d) // 3 * 2) while [c <= l] [ if prime? c [ append d c if p // c = 0 [return false] ] c: c + s: 6 - s ] true ] ]

 [10/11] from: joel:neely:fedex at: 28-Nov-2001 18:38


Hi, Ladislav, Ladislav Mecir wrote:
> Hi Joel, > <<Joel>>
<<quoted lines omitted: 4>>
> <</Joel>> > your assumption is wrong, at least here.
The statement was based on a QAD test like the following:
>> x: now/time/precise
repeat i 5000000 [zero? i // 2] print now/time/precise - x 0:00:52.78
>> x: now/time/precise
repeat i 5000000 [i // 2 = 0] print now/time/precise - x 0:00:54.04 Further testing has shown *significant* variation in timings. (Good thing I wasn't expecting consistency! ;-)
> <<Joel>> > use [d] [
<<quoted lines omitted: 25>>
> if p // 2 = 0 [return p = 2] > if p // 3 = 0 [return p = 3]
Nice! However, the following is not so nice!
> use [d] [ > d: [2 3 5 7]
<<quoted lines omitted: 15>>
> ] > ]
Unfortunately, faster is not always better. Try the above function on prime? 29 * 29 prime? 37 * 37 prime? 53 * 53 prime? 37 * 67 prime? 59 * 71 and so on... I tested both using the following (where FACTOR is too obvious to include) and got some discrepancies... use [d] [ d: [2 3 5 7] lprime?: function [p] [c s l] [ l: to integer! square-root p foreach v d [ if p // v = 0 [return p = v] if v >= l [return true] ] c: (last d) + 6 - s: (last d) // 3 * 2 while [c <= l] [ if lprime? c [ append d c if p // c = 0 [return false] ] c: c + s: 6 - s ] true ] ] use [d] [ d: [2 3 5 7] jprime?: func [p /local c s] [ if found? find d p [return true] foreach v d [ if zero? p // v [return false] if v * v > p [return true ] ] either zero? s: (c: 2 + last d) // 3 [ c: c + 2 s: 4 ][ s: s + s ] while [c * c <= p] [ if jprime? c [ append d c if zero? p // c [return false] ] c: c + s: 6 - s ] return true ] ] use [l j] [ repeat i 5000 [ l: lprime? i j: jprime? i if l <> j [ print [i l j mold factor i] ] ] ] -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" ;

 [11/11] from: joel:neely:fedex at: 28-Nov-2001 18:47


Hi, again, Ladislav, Ladislav Mecir wrote:
> use [d] [ > d: [2 3 5 7]
<<quoted lines omitted: 15>>
> ] > ]
Niceness restored!! After I made the point earlier about testing only thru the square root of the candidate, I'm glad you caught my omission of that in the latter functions! -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" ;

Notes
  • Quoted lines have been omitted from some messages.
    View the message alone to see the lines that have been omitted