[REBOL] Re: Speed testing prime functions..
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
]
]
