Anonymous user
Chinese remainder theorem: Difference between revisions
Added zkl
(add Haskell example) |
(Added zkl) |
||
Line 574:
{{out}}
<pre>23</pre>
=={{header|zkl}}==
{{trans|Go}}
Using the GMP library, gcdExt is the Extended Euclidean algorithm.
<lang zkl>var BN=Import("zklBigNum"), one=BN(1);
fcn crt(xs,ys){
p:=xs.reduce('*,BN(1));
X:=BN(0);
foreach x,y in (xs.zip(ys)){
q:=p/x;
z,s,_:=q.gcdExt(x);
if(z!=one) throw(Exception.ValueError("%d not coprime".fmt(x)));
X+=y*s*q;
}
return(X % p);
}</lang>
<lang zkl>println(crt(T(3,5,7), T(2,3,2))); //-->23
println(crt(T(11,12,13),T(10,4,12))); //-->1000
println(crt(T(11,22,19), T(10,4,9))); //-->ValueError: 11 not coprime</lang>
| |||