1234567891011121314151617181920212223242526272829303132333435363738394041424344454647 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 18 May 2020
- # https://github.com/trizen
- # Algorithm for performing exact division of two large integers, using the Chinese Remainder Theorem (CRT).
- func exact_division(n,k) {
- return n if (k == 1)
- return 1 if (n == k)
- var nv = n.valuation(2)
- var kv = k.valuation(2)
- n >>= nv
- k >>= kv
- return (1 << (nv-kv)) if (n == k)
- var lcm = 2
- var crt = [1, 2]
- var logk = k.ilog2
- var logn = n.ilog2-1
- for(var p = 3; true ; p.next_prime!) {
- var q = Math.chinese(crt, [invmod(k, p) * (n%p), p]) || next
- crt = [q, lcm *= p]
- if (q.ilog2 + logk >= logn) {
- break if (q*k >= n)
- }
- }
- crt[0] << (nv - kv)
- }
- say exact_division(43*97, 43)
- say exact_division(100!, 50!)
- with (10!) {|n|
- n.divisors.each {|d|
- assert_eq(exact_division(n, d), n/d)
- }
- }
|