Chinese remainder theorem: Difference between revisions
Added XPL0 example.
VincentARM (talk | contribs) (add task to aarch64 assembly for rasperry pi) |
(Added XPL0 example.) |
||
Line 3,581:
23 = 3 (mod 5)
23 = 2 (mod 7)</pre>
=={{header|Wren}}==
{{trans|C}}
Line 3,620 ⟶ 3,621:
23
</pre>
=={{header|XPL0}}==
{{trans|C}}
When N are not pairwise coprime, the program aborts due to division by zero, which is one way to convey error.
<syntaxhighlight lang "XPL0">func MulInv(A, B); \Returns X where rem((A*X) / B) = 1
int A, B;
int B0, T, Q;
int X0, X1;
[B0:= B; X0:= 0; X1:= 1;
if B = 1 then return 1;
while A > 1 do
[Q:= A / B;
T:= B; B:= rem(A/B); A:= T;
T:= X0; X0:= X1 - Q*X0; X1:= T;
];
if X1 < 0 then X1:= X1 + B0;
return X1;
];
func ChineseRem(N, A, Len);
int N, A, Len;
int P, I, Prod, Sum;
[Prod:= 1; Sum:= 0;
for I:= 0 to Len-1 do Prod:= Prod*N(I);
for I:= 0 to Len-1 do
[P:= Prod / N(I);
Sum:= Sum + A(I) * MulInv(P,N(I)) * P;
];
return rem(Sum/Prod);
];
int N, A;
[N:= [ 3, 5, 7 ];
A:= [ 2, 3, 2 ];
IntOut(0, ChineseRem(N, A, 3)); CrLf(0);
]</syntaxhighlight>
{{out}}
<pre>
23
</pre>
=={{header|zkl}}==
{{trans|Go}}
| |||