Hi Joel
Pollard Rho is great heuristic but neither a running time of O(N^.25) nor
success is in finding factors is guarenteed. but I use it.
On Wed, 16 Jan 2002, Joel Neely wrote:
> 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.
>
--
To unsubscribe from this list, please send an email to
[EMAIL PROTECTED] with "unsubscribe" in the
subject, without the quotes.
