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> |
||