Mailing List Archive: 49091 messages

## [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
]
]
```