Chinese remainder theorem: Difference between revisions
Content added Content deleted
VincentARM (talk | contribs) (add task to aarch64 assembly for rasperry pi) |
(Added XPL0 example.) |
||
Line 3,581: | Line 3,581: | ||
23 = 3 (mod 5) |
23 = 3 (mod 5) |
||
23 = 2 (mod 7)</pre> |
23 = 2 (mod 7)</pre> |
||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{trans|C}} |
{{trans|C}} |
||
Line 3,620: | Line 3,621: | ||
23 |
23 |
||
</pre> |
</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}}== |
=={{header|zkl}}== |
||
{{trans|Go}} |
{{trans|Go}} |