12345678910111213141516171819202122232425262728 |
- #!/usr/bin/ruby
- # Remainder tree algorithm.
- # Algorithm from:
- # https://facthacks.cr.yp.to/remainder.html
- func product_tree(X) {
- gather {
- take(X)
- while (X.len > 1) {
- X = range((X.len+1)>>1).map{|i| X.slice(i<<1, 2).prod }
- take(X)
- }
- }
- }
- func remainders(n,X) {
- var result = [n]
- product_tree(X).flip.each {|t|
- result = t.map_kv {|k,v| result[k>>1] % v }
- }
- return result
- }
- say var r = remainders(8675309, [11,13,17,19,23]) #=> [5, 6, 5, 4, 8]
- assert_eq(r, [5, 6, 5, 4, 8])
|