[REBOL] Re: Speed testing prime functions..
From: joel:neely:fedex at: 28-Nov-2001 18:38
Hi, Ladislav,
Ladislav Mecir wrote:
> 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.
>
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] [
> 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
> ]
> ]
>
> <</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]
Nice!
However, the following is not so nice!
> 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
> ]
> ]
>
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" ;
