123456789101112131415161718192021222324252627282930313233343536373839404142 |
- #!/usr/bin/ruby
- # Batch greatest common divisor algorithm.
- # Algorithm from:
- # https://web.archive.org/web/20220116042107/http://cr.yp.to/talks/2012.12.28/slides.pdf
- func batch_gcd(X) {
- var prods = gather {
- take(X)
- while (X.len > 1) {
- X = range((X.len+1)>>1).map{|i| X.slice(i<<1, 2).prod }
- take(X)
- }
- }
- var R = prods.pop
- while (prods) {
- X = prods.pop
- R = X.map_kv {|k,v| R[k>>1] % v.sqr }
- }
- R ~Z X -> map_2d {|r,n| gcd(r/n, n) }
- }
- func batch_gcd_naive(X) { # a simpler approach (much slower)
- X.map_reduce {|a,b| a*b } ~Z X -> map_2d {|r,n| gcd(r/n, n) }
- }
- var arr = [43*97, 41*29, 43*503, 503*863]
- say var a = batch_gcd(arr) #=> [43, 1, 21629, 503]
- say var b = batch_gcd_naive(arr) #=> [1, 1, 43, 503]
- assert_eq(a, %n[43, 1, 21629, 503])
- assert_eq(b, %n[1, 1, 43, 503])
- assert(batch_gcd(1000.of { irand(2**1024) }).len, 1000)
- assert(batch_gcd(1001.of { irand(2**1024) }).len, 1001)
|