REBOL [
Title: "Prime number checker"
Date: 21-Jul-1999
Version: 0.0.2
File: %prime.r
Home: http://www.cs.uoregon.edu/~tomc
Author: "Tom Conlin"
Owner: "Intuitec"
Rights: "yes"
Tabs: 4
Purpose: {
Address the question, could this integer be a prime number?
results of false are not prime,
results of true are very probably prime
and with the /strong refinement, ( I still have to verify this )
true ( should ) guarantee prime.
if the argument is outside the domain of the function,
none is returned
}
Comment: {
Able to handle integers up to one bit less than the machine (or rebol)
is using for a ( signed? ) integer, this may vary -- but 30 bits probabaly.
If you use the xxx-modulus functions elsewhere (they were kept general),
be sure to keep "m" non-zero
The /strong refinement is yet to be formaly proven (by me) to garantee primes.
}
History: [
0.0.1 [19-Jul-1999 {typed (2 ** (n - 1 )) // n at the prompt, for n > 1024 }]
0.0.2 [21-Jul-1999 "dug out old homework"]
]
Language: 'English
Email: tomc@cs.uoregon.edu
Need: 0.2.1
Charset: 'ANSI
Example: "is-prime? 1073741789"
library: [
level: 'intermediate
platform: none
type: none
domain: 'math
tested-under: none
support: none
license: none
see-also: none
]
]
is-prime?: func ["return false if argument is composite, and none if can't tell"
n [integer!]
/strong
/local b e p z
][
if n < 2 [return false] ; no negatives
if any [error? try [z: n + n] z < n][return none]
e: n - 1
p: power-modulus 2 e n
if strong [
b: 3
z: to-integer (log-2 n + 1 )
while [ (p == 1) and (b < z) ][
p: power-modulus b e n
b: b + 1
]
]
p == 1
]
comment {
an efficent recursive power function, will recurse only the number
of (significant) bits in the exponent, squareing the base at each
level but only accumulating the base if the least significant bit
of the exponent at that level is set. note: just forwards the
modulus to the multiply function.
}
power-modulus: func [ "b to the e power, mod m"
b [integer!] "base"
e [integer!] "exponent"
m [integer!] "modulus"
/local t
][
if e == 0 [return 1]
t: power-modulus (multiply-modulus b b m ) to-integer(e / 2) m
if odd? e [ t: multiply-modulus t b m ]
t
]
comment {
a multiply which if need be,
guarantees the product is never more than
one bit longer than the modulus
}
multiply-modulus: func[ "j times k, mod m"
j [integer!]
k [integer!]
m [integer!] "modulus"
/local product
][
if error? try [ product: j * k // m ] [
product: 0
while[ k > 0 ][
if(odd? k )
[ product: to-integer( product + j ) // m ]
j: j + j // m
k: to-integer k / 2
]
]
to-integer product
]