Chinese remainder theorem: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 1,366: | Line 1,366: | ||
{{out}} |
{{out}} |
||
<pre>23</pre> |
<pre>23</pre> |
||
=={{header|M2000 Interpreter}}== |
|||
{{trans|C}} |
|||
<lang M2000 Interpreter> |
|||
Function ChineseRemainder(n(), a()) { |
|||
Function mul_inv(a, b) { |
|||
if b==1 then =1 : exit |
|||
b0=b |
|||
x1=1 : x0=0 |
|||
while a>1 |
|||
q=a div b |
|||
t=b : b=a mod b: a=t |
|||
t=x0: x0=x1-q*x0:x1=t |
|||
end while |
|||
if x1<0 then x1+=b0 |
|||
=x1 |
|||
} |
|||
def p, i, prod=1, sum |
|||
for i=0 to len(n())-1 {prod*=n(i)} |
|||
for i=0 to len(a())-1 |
|||
p=prod div n(i) |
|||
sum+=a(i)*mul_inv(p, n(i))*p |
|||
next |
|||
=sum mod prod |
|||
} |
|||
Print ChineseRemainder((3,5,7), (2,3,2)) |
|||
</lang> |
|||
{{out}} |
|||
<pre>23 |
|||
</pre> |
|||
=={{header|Maple}}== |
=={{header|Maple}}== |