Chinese remainder theorem: Difference between revisions

Content added Content deleted
m (→‎{{header|Phix}}: added syntax colouring the hard wa, made runnable)
(Added solution for Action!)
Line 130: Line 130:
<pre>
<pre>
x= 23
x= 23
</pre>

=={{header|Action!}}==
<lang Action!>INT FUNC MulInv(INT a,b)
INT b0,x0,x1,q,tmp

IF b=1 THEN RETURN (1) FI

b0=b x0=0 x1=1
WHILE a>1
DO
q=a/b

tmp=b
b=a MOD b
a=tmp
tmp=x0
x0=x1-q*x0
x1=tmp
OD
IF x1<0 THEN
x1==+b0
FI
RETURN (x1)

INT FUNC ChineseRemainder(BYTE ARRAY n,a BYTE len)
INT prod,sum,p,m
BYTE i

prod=1 sum=0
FOR i=0 TO len-1
DO
prod==*n(i)
OD
FOR i=0 TO len-1
DO
p=prod/n(i)
m=MulInv(p,n(i))
sum==+a(i)*m*p
OD
RETURN (sum MOD prod)

PROC Main()
BYTE ARRAY n=[3 5 7],a=[2 3 2]
INT res

res=ChineseRemainder(n,a,3)
PrintI(res)
RETURN</lang>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Chinese_remainder_theorem.png Screenshot from Atari 8-bit computer]
<pre>
23
</pre>
</pre>