Chinese remainder theorem: Difference between revisions
Added Algol 68
imported>Maxima enthusiast |
(Added Algol 68) |
||
| (4 intermediate revisions by 4 users not shown) | |||
Line 401:
Ada.Text_IO.Put_Line(Integer'Image(Sum mod Prod));
end Chin_Rema;</syntaxhighlight>
=={{header|ALGOL 68}}==
{{Trans|C|with some error messages}}
<syntaxhighlight lang="algol68">
BEGIN # Chinese remainder theorewm - translated from the C sample #
PROC mul inv = ( INT a in, b in )INT:
IF b in = 1
THEN 1
ELSE
INT b0 = b in;
INT a := a in, b := b in, x0 := 0, x1 := 1;
WHILE a > 1 DO
IF b = 0 THEN
print( ( "Numbers not pairwise coprime", newline ) ); stop
FI;
INT q = a OVER b;
INT t;
t := b; b := a MOD b; a := t;
t := x0; x0 := x1 - q * x0; x1 := t
OD;
IF x1 < 0 THEN x1 + b0 ELSE x1 FI
FI # mul inv # ;
PROC chinese remainder = ( []INT n, a )INT:
IF LWB n /= LWB a OR UPB n /= UPB a OR ( UPB a - LWB a ) + 1 < 1
THEN print( ( "Array bounds mismatch or empty arrays", newline ) ); stop
ELSE
INT prod := 1, sum := 0;
FOR i FROM LWB n TO UPB n DO prod *:= n[ i ] OD;
IF prod = 0 THEN
print( ( "Numbers not pairwise coprime", newline ) ); stop
FI;
FOR i FROM LWB n TO UPB n DO
INT p = prod OVER n[ i ];
sum +:= a[ i ] * mul inv( p, n[ i ] ) * p
OD;
FI # chinese remainder # ;
print( ( whole( chinese remainder( ( 3, 5, 7 ), ( 2, 3, 2 ) ), 0 ), newline ) )
END
</syntaxhighlight>
{{out}}
<pre>
23
</pre>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}}
Line 918 ⟶ 967:
23
</pre>
=={{header|
<syntaxhighlight lang="coffeescript">crt = (n,a) ->
sum = 0
Line 943 ⟶ 992:
23
</pre>
=={{header|Common Lisp}}==
Using function ''invmod'' from [[http://rosettacode.org/wiki/Modular_inverse#Common_Lisp]].
Line 1,144 ⟶ 1,194:
{{trans|C}}
<syntaxhighlight lang="text">
b0 = b
x1 = 1
if b <> 1
while a > 1
q = a div b
t = b
b = a mod b
a = t
t = x0
x0 = x1 - q * x0
x1 = t
.
if x1 < 0
x1 += b0
.
.
return x1
.
proc remainder . n[] a[] r .
prod = 1
sum = 0
for i = 1 to len n[]
prod *= n[i]
.
for i = 1 to len n[]
p = prod / n[i]
.▼
▲ r = sum mod prod
▲ .
.
n[] = [ 3 5 7 ]
a[] = [ 2 3 2 ]
print h
</syntaxhighlight>
Line 2,061 ⟶ 2,111:
makelist([lst[%%[i][1]],lst[%%[i][2]]],i,length(%%)),
makelist(apply('gcd,%%[i]),i,length(%%)),
if length(unique(%%))
/* Chinese remainder function */
Line 3,742 ⟶ 3,792:
=={{header|Wren}}==
{{trans|C}}
<syntaxhighlight lang="
var mulInv = Fn.new { |a, b|
if (b == 1) return 1
| |||