Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

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