Anonymous user
Chinese remainder theorem: Difference between revisions
added Crystal implementation (translation of Ruby implementation)
m (→congruences sets: added comments and changed whitespace.) |
(added Crystal implementation (translation of Ruby implementation)) |
||
Line 512:
(INVMOD 418 11)
0]
</pre>
=={{Header|Crystal}}==
{{trans|Ruby}}
<lang crystal>def extended_gcd(a, b)
last_remainder, remainder = a.abs, b.abs
x, last_x, y, last_y = 0, 1, 1, 0
until remainder == 0
tmp = remainder
quotient, remainder = last_remainder.divmod(remainder)
last_remainder = tmp
x, last_x = last_x - quotient * x, x
y, last_y = last_y - quotient * y, y
end
return last_remainder, last_x * (a < 0 ? -1 : 1)
end
def invmod(e, et)
g, x = extended_gcd(e, et)
unless g == 1
raise "Multiplicative inverse modulo does not exist"
end
return x % et
end
def chinese_remainder(mods, remainders)
max = mods.reduce { |acc, i| acc * i }
series = remainders.zip(mods).map { |r, m| r * max * invmod(max // m, m) // m }
return series.sum % max
end
puts chinese_remainder([3, 5, 7], [2, 3, 2])
puts chinese_remainder([5, 7, 9, 11], [1, 2, 3, 4])
</lang>
'''Output:'''
<pre>
23
1731
</pre>
|