Mailing List Archive: 49091 messages

## [REBOL] Just for fun

### From: joel::neely::fedex::com at: 16-Jan-2002 20:31

```
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" ;
```