Chinese remainder theorem: Difference between revisions
Added Algol 68
(Added XPL0 example.) |
(Added Algol 68) |
||
| (10 intermediate revisions by 6 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;
sum MOD prod
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">
func mul_inv a b
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
.
prod = 1
sum = 0
for i = 1 to len n[]
prod *= n[i]
.
for i = 1 to len n[]
p = prod / n[i]
.
.
n[] = [ 3 5 7 ]
a[] = [ 2 3 2 ]
print h
</syntaxhighlight>
Line 1,375 ⟶ 1,425:
10 11 4 22 9 19 3 >>>crt<<< .
</pre>
=={{header|Fortran}}==
Written in Fortran-77 style (fixed form, GO TO), directly translated from the problem description.
<syntaxhighlight lang="Fortran">
* RC task: use the Chinese Remainder Theorem to solve a system of congruences.
FUNCTION crt(n, residues, moduli)
IMPLICIT INTEGER (A-Z)
DIMENSION residues(n), moduli(n)
p = product(moduli)
crt = 0
DO 10 i = 1, n
m = p/moduli(i)
CALL egcd(moduli(i), m, r, s, gcd)
IF (gcd .ne. 1) GO TO 20 ! error exit
10 crt = crt + residues(i)*s*m
crt = modulo(crt, p)
RETURN
20 crt = -1 ! will never be negative, so flag an error
END
* Compute egcd(a, b), returning x, y, g s.t.
* g = gcd(a, b) and a*x + b*y = g
*
SUBROUTINE egcd(a, b, x, y, g)
IMPLICIT INTEGER (A-Z)
g = a
u = 0
v = 1
w = b
x = 1
y = 0
1 IF (w .eq. 0) RETURN
q = g/w
u next = x - q*u
v next = y - q*v
w next = g - q*w
x = u
y = v
g = w
u = u next
v = v next
w = w next
GO TO 1
END
PROGRAM Chinese Remainder
IMPLICIT INTEGER (A-Z)
PRINT *, crt(3, [2, 3, 2], [3, 5, 7])
PRINT *, crt(3, [2, 3, 2], [3, 6, 7]) ! no solution
END
</syntaxhighlight>
{{Out}}
<pre>
23
-1
</pre>
=={{header|FreeBASIC}}==
Partial {{trans|C}}. Uses the code from [[Greatest_common_divisor#Recursive_solution]] as an include.
Line 1,412 ⟶ 1,528:
print chinese_remainder(n(), a())</syntaxhighlight>
{{out}}<pre>23</pre>
=={{header|Frink}}==
This example solves an extended version of the Chinese Remainder theorem by allowing an optional third parameter <CODE>d</CODE> which defaults to 0 and is an integer. The solution returned is the smallest solution >= d. (This optional parameter is common in many/most real-world applications of the Chinese Remainder Theorem.)
Line 1,986 ⟶ 2,103:
<syntaxhighlight lang="matlab">>> chineseRemainder([2 3 2], [3 5 7])
ans = 23</syntaxhighlight>
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">
/* Function that checks pairwise coprimality */
check_pwc(lst):=block(
sublist(cartesian_product_list(makelist(i,i,length(lst)),makelist(i,i,length(lst))),lambda([x],x[1]#x[2])),
makelist([lst[%%[i][1]],lst[%%[i][2]]],i,length(%%)),
makelist(apply('gcd,%%[i]),i,length(%%)),
if length(unique(%%))=1 and first(unique(%%))=1 then true)$
/* Chinese remainder function */
c_remainder(A,N):=if check_pwc(N)=false then "chinese remainder theorem not applicable" else block(
cn:apply("*",N),
makelist(gcdex(cn/N[i],N[i]),i,1,length(N)),
makelist(A[i]*%%[i][1]*cn/N[i],i,1,length(N)),
apply("+",%%),
mod(%%,cn));
Alis:[2,3,2]$
Nlis:[3,5,7]$
c_remainder(Alis,Nlis);
</syntaxhighlight>
{{out}}
<pre>
23
</pre>
=={{header|Modula-2}}==
<syntaxhighlight lang="modula2">MODULE CRT;
Line 3,070 ⟶ 3,213:
say 'no solution found.' /*oops, announce that solution ¬ found.*/</syntaxhighlight>
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}} <br><br>
=={{header|RPL}}==
{{trans|Python}}
{{works with|Halcyon Calc|4.2.9}}
{| class="wikitable" ≪
! RPL code
! Comment
|-
|
≪
DUP ROT 1 R→C ROT 0 R→C
'''WHILE''' DUP RE '''REPEAT'''
OVER RE OVER RE / FLOOR
OVER * NEG ROT +
'''END'''
DROP C→R ROT MOD
SWAP 1 == SWAP 0 IFTE
≫ ‘<span style="color:blue">MODINV</span>’ STO
≪ → n a
≪ 0
1 1 n SIZE '''FOR''' j n j GET * '''NEXT'''
1 n SIZE '''FOR''' j
DUP n j GET / FLOOR
ROT OVER n j GET <span style="color:blue">MODINV</span> a j GET * ROT * +
SWAP '''NEXT'''
MOD
≫ ≫ ‘<span style="color:blue">NCHREM</span>’ STO
|
<span style="color:blue">MODINV</span> ''( a b → x ) with ax = 1 mod b''
3:b 2:(r,u) ← (a,1) 1:(r',u') ← (b,0)
While r' ≠ 0
q ← r // r'
(r - q*r', u - q*u')
Forget (r',u') and calculate u mod b
Test r and return zero if a and b are not co-prime
<span style="color:blue">NCHREM</span> ''( n a → remainder )''
sum = 0
prod = reduce(lambda a, b: a*b, n)
for n_i, a_i in zip(n, a):
p = prod / n_i
sum += a_i * mul_inv(p, n_i) * p
// reorder stack for next iteration
return sum % prod
|}
'''RPL 2003 version'''
{{works with|HP|49}}
≪ → a n
≪ a 1 GET n 1 GET →V2
2 a SIZE '''FOR''' j
a j GET n j GET →V2 ICHINREM
'''NEXT'''
V→ MOD
≫ ≫ '<span style="color:blue">NCHREM</span>' STO
{ 2 3 2 } { 3 5 7 } <span style="color:blue">NCHREM</span>
{{out}}
<pre>
1: 23.
</pre>
=={{header|Ruby}}==
Brute-force.
Line 3,113 ⟶ 3,320:
p chinese_remainder([10,4,9], [11,22,19]) #=> nil
</syntaxhighlight>
=={{header|Rust}}==
<syntaxhighlight lang="rust">fn egcd(a: i64, b: i64) -> (i64, i64, i64) {
Line 3,584 ⟶ 3,792:
=={{header|Wren}}==
{{trans|C}}
<syntaxhighlight lang="
var mulInv = Fn.new { |a, b|
if (b == 1) return 1
| |||