Hi, all,
There was some discussion about factoring and primes a while back
(don't remember exactly when). Perusing my number theory books
reminded me of Pollard's "rho" method, which typically finds
factors *WAY* faster than the easier to understand and implement
brute-force trial-divisors-in-order-up-to-the-square-root method
we've probably all played around with.
A quick bit of REBOL hacking produced...
rho: make object! [
; "randomizing" function across prime residue classes
f: func [x [number!] n [number!]] [1.0 * x * x + 1 // n]
; greatest common divisor (helper first)
_gcd: func [a [number!] b [number!] /local c] [
while [b > 0] [c: a // b a: b b: c]
a
]
gcd: func [a [number!] b [number!]] [
a: abs a b: abs b
_gcd max a b min a b
]
; returns 1 or n for primes, some factor for composites
test: func [n [number!] /local x y d g] [
n: abs n
either n > 3 [
d: n + (x: 2) - (y: f x n) // n
while [d > 0] [
if 1 < g: gcd n d [return g]
d: n + (x: f x n) - (y: f f y n n) // n
]
1
][
n
]
]
; returns block with some factors or input number (if prime)
factors: func [n [number!] /local d r] [
r: copy []
while [even? n] [append r 2 n: n / 2]
while [1 < d: test n] [append r d n: n / d]
if 1 < n [append r n]
r
]
]
Which does things like:
>> rho/test 11 == 1
>> rho/test 111 == 3
>> rho/test 1111 == 11
>> rho/test 11111 == 41
>> rho/test 111111 == 3
and
>> rho/factors 11 == [11]
>> rho/factors 111 == [3 37]
>> rho/factors 1111 == [11 101]
>> rho/factors 11111 == [41 271]
>> rho/factors 111111 == [3 7 5291]
>> rho/factors 101010101 == [41 271 9091]
>> rho/factors 10010101001 == [109 15187 6047]
>> rho/factors 1001001001001 == [31 41 271 2906161]
Note that the factors are not necessarily produced in order; I
also haven't verified that they will always be prime. However
they should show that the number is composite.
No guarantees, but have fun!
-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" ;
--
To unsubscribe from this list, please send an email to
[EMAIL PROTECTED] with "unsubscribe" in the
subject, without the quotes.
