Chinese remainder theorem: Difference between revisions
Frink
(Added solution for Action!) |
(Frink) |
||
Line 971:
print chinese_remainder(n(), a())</lang>
{{out}}<pre>23</pre>
=={{header|Frink}}==
This example solves an extended version of the Chinese Remainder theorem by allowing an optional third parameter <CODE>d</CODE> which is an integer. The solution returned is the smallest solution >= d.
<lang frink>/** arguments:
[r, m, d=0] where r and m are arrays of the remainder terms r and the
modulus terms m respectively. These must be of the same length.
returns
x, the unique solution mod N where N is the product of all the M terms where x >= d.
*/
ChineseRemainder[r, m, d=0] :=
{
if length[r] != length[m]
{
println["ChineseRemainder: r and m must be arrays of the same length."]
return undef
}
N = product[m]
y = new array
z = new array
x = 0
for i = rangeOf[m]
{
y@i = N / m@i
z@i = modInverse[y@i, m@i]
if z@i == undef
{
println["ChineseRemainder: modInverse returned undef for modInverse[" + y@i + ", " + m@i + "]"]
return undef
}
x = x + r@i y@i z@i
}
xp = x mod N
f = d div N
r = f * N + xp
if r < d
r = r + N
return r
}
println[ChineseRemainder[[2,3,2],[3,5,7]] ]</lang>
{{out}}
<pre>
23
</pre>
=={{header|FunL}}==
| |||