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