Just for fun

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

>> rho/factors 11 == [11] >> rho/factors 111 == [3 37] >> rho/factors 10010101001 == [109 15187 6047] >> rho/factors 1001001001001 == [31 41 271 2906161]

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: