Mailing List Archive: 49091 messages

# Just for fun

### [1/2] 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 ==  >> rho/factors 111 == [3 37]
<<quoted lines omitted: 4>>
>> 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 (\$) {@_} 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" ;

### [2/2] from: tomc:darkwing:uoregon at: 16-Jan-2002 18:58

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:

Notes
• Quoted lines have been omitted from some messages.
View the message alone to see the lines that have been omitted