[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" ;
