Chinese remainder theorem: Difference between revisions
Added Algol 68
MaiconSoft (talk | contribs) (Added Delphi example) |
(Added Algol 68) |
||
| (18 intermediate revisions by 11 users not shown) | |||
Line 50:
::: <math>x \pmod{N}</math>.
<br><br>
=={{header|11l}}==
{{trans|Python}}
<
V b0 = b
V x0 = 0
Line 77 ⟶ 76:
V n = [3, 5, 7]
V a = [2, 3, 2]
print(chinese_remainder(n, a))</
{{out}}
<pre>23</pre>
=={{header|360 Assembly}}==
{{trans|REXX}}
<
CHINESE CSECT
USING CHINESE,R12 base addr
Line 126 ⟶ 124:
NOSOL DC CL17'no solution found'
YREGS
END CHINESE</
{{out}}
<pre>
x= 23
</pre>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }}
<syntaxhighlight lang AArch64 Assembly>
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program chineserem64.s */
/************************************/
/* Constantes */
/************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessResult: .asciz "Result = "
szCarriageReturn: .asciz "\n"
.align 2
arrayN: .quad 3,5,7
arrayA: .quad 2,3,2
.equ ARRAYSIZE, (. - arrayA)/8
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main:
ldr x0,qAdrarrayN // N array address
ldr x1,qAdrarrayA // A array address
mov x2,#ARRAYSIZE // array size
bl chineseremainder
ldr x1,qAdrsZoneConv
bl conversion10 // call décimal conversion
mov x0,#3
ldr x1,qAdrszMessResult
ldr x2,qAdrsZoneConv // insert conversion in message
ldr x3,qAdrszCarriageReturn
bl displayStrings // display message
100: // standard end of the program
mov x0, #0 // return code
mov x8,EXIT
svc #0 // perform the system call
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrsZoneConv: .quad sZoneConv
qAdrszMessResult: .quad szMessResult
qAdrarrayA: .quad arrayA
qAdrarrayN: .quad arrayN
/******************************************************************/
/* compute chinese remainder */
/******************************************************************/
/* x0 contains n array address */
/* x1 contains a array address */
/* x2 contains array size */
chineseremainder:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
stp x6,x7,[sp,-16]! // save registers
stp x8,x9,[sp,-16]! // save registers
mov x4,#1 // product
mov x5,#0 // sum
mov x6,#0 // indice
1:
ldr x3,[x0,x6,lsl #3] // load a value
mul x4,x3,x4 // compute product
add x6,x6,#1
cmp x6,x2
blt 1b
mov x6,#0
mov x7,x0 // save entry
mov x8,x1
mov x9,x2
2:
mov x0,x4 // product
ldr x1,[x7,x6,lsl #3] // value of n
sdiv x2,x0,x1
mov x0,x2 // p
bl inverseModulo
mul x0,x2,x0 // = product / n * invmod
ldr x3,[x8,x6,lsl #3] // value a
madd x5,x0,x3,x5 // sum = sum + (result1 * a)
add x6,x6,#1
cmp x6,x9
blt 2b
sdiv x1,x5,x4 // divide sum by produc
msub x0,x1,x4,x5 // compute remainder
100:
ldp x8,x9,[sp],16 // restaur registers
ldp x6,x7,[sp],16 // restaur registers
ldp x4,x5,[sp],16 // restaur registers
ldp x2,x3,[sp],16 // restaur registers
ldp x1,lr,[sp],16 // restaur registers
ret
/***************************************************/
/* Calcul modulo inverse */
/***************************************************/
/* x0 cont.quad number, x1 modulo */
/* x0 return result */
inverseModulo:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
stp x6,x7,[sp,-16]! // save registers
mov x7,x1 // save Modulo
mov x6,x1 // A x0=B
mov x4,#1 // X
mov x5,#0 // Y
1: //
cmp x0,#0 // B = 0
beq 2f
mov x1,x0 // T = B
mov x0,x6 // A
sdiv x2,x0,x1 // A / T
msub x0,x2,x1,x0 // B and x2=Q
mov x6,x1 // A=T
mov x1,x4 // T=X
msub x4,x2,x1,x5 // X=Y-(Q*T)
mov x5,x1 // Y=T
b 1b
2:
add x7,x7,x5 // = Y + N
cmp x5,#0 // Y > 0
bge 3f
mov x0,x7
b 100f
3:
mov x0,x5
100:
ldp x6,x7,[sp],16 // restaur registers
ldp x4,x5,[sp],16 // restaur registers
ldp x2,x3,[sp],16 // restaur registers
ldp x1,lr,[sp],16 // restaur registers
ret
/***************************************************/
/* display multi strings */
/***************************************************/
/* x0 contains number strings address */
/* x1 address string1 */
/* x2 address string2 */
/* x3 address string3 */
/* other address on the stack */
/* thinck to add number other address * 4 to add to the stack */
displayStrings: // INFO: affichageStrings
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
add fp,sp,#48 // save paraméters address (6 registers saved * 8 bytes)
mov x4,x0 // save strings number
cmp x4,#0 // 0 string -> end
ble 100f
mov x0,x1 // string 1
bl affichageMess
cmp x4,#1 // number > 1
ble 100f
mov x0,x2
bl affichageMess
cmp x4,#2
ble 100f
mov x0,x3
bl affichageMess
cmp x4,#3
ble 100f
mov x3,#3
sub x2,x4,#4
1: // loop extract address string on stack
ldr x0,[fp,x2,lsl #3]
bl affichageMess
subs x2,x2,#1
bge 1b
100:
ldp x4,x5,[sp],16 // restaur registers
ldp x2,x3,[sp],16 // restaur registers
ldp x1,lr,[sp],16 // restaur registers
ret
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
{{Output}}
<pre>
Result = 23
</pre>
=={{header|Action!}}==
<
INT b0,x0,x1,q,tmp
Line 179 ⟶ 371:
res=ChineseRemainder(n,a,3)
PrintI(res)
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Chinese_remainder_theorem.png Screenshot from Atari 8-bit computer]
Line 185 ⟶ 377:
23
</pre>
=={{header|Ada}}==
Using the package Mod_Inv from [[http://rosettacode.org/wiki/Modular_inverse#Ada]].
<
procedure Chin_Rema is
Line 209 ⟶ 400:
end loop;
Ada.Text_IO.Put_Line(Integer'Image(Sum mod Prod));
end Chin_Rema;</
=={{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}}
<syntaxhighlight lang ARM Assembly>
/* ARM assembly Raspberry PI or android with termux */
/* program chineserem.s */
/* REMARK 1 : this program use routines in a include file
see task Include a file language arm assembly
for the routine affichageMess conversion10
see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes */
/************************************/
.include "../constantes.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessResult: .asciz "Result = "
szCarriageReturn: .asciz "\n"
.align 2
arrayN: .int 3,5,7
arrayA: .int 2,3,2
.equ ARRAYSIZE, (. - arrayA)/4
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main:
ldr r0,iAdrarrayN @ N array address
ldr r1,iAdrarrayA @ A array address
mov r2,#ARRAYSIZE @ array size
bl chineseremainder
ldr r1,iAdrsZoneConv
bl conversion10 @ call décimal conversion
mov r0,#3
ldr r1,iAdrszMessResult
ldr r2,iAdrsZoneConv @ insert conversion in message
ldr r3,iAdrszCarriageReturn
bl displayStrings @ display message
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
svc #0 @ perform the system call
iAdrszCarriageReturn: .int szCarriageReturn
iAdrsZoneConv: .int sZoneConv
iAdrszMessResult: .int szMessResult
iAdrarrayA: .int arrayA
iAdrarrayN: .int arrayN
/******************************************************************/
/* compute chinese remainder */
/******************************************************************/
/* r0 contains n array address */
/* r1 contains a array address */
/* r2 contains array size */
chineseremainder:
push {r1-r9,lr} @ save registers
mov r4,#1 @ product
mov r5,#0 @ sum
mov r6,#0 @ indice
1:
ldr r3,[r0,r6,lsl #2] @ load a value
mul r4,r3,r4 @ compute product
add r6,#1
cmp r6,r2
blt 1b
mov r6,#0
mov r7,r0 @ save entry
mov r8,r1
mov r9,r2
2:
mov r0,r4 @ product
ldr r1,[r7,r6,lsl #2] @ value of n
bl division
mov r0,r2 @ p
bl inverseModulo
mul r0,r2,r0 @ = product / n * invmod
ldr r3,[r8,r6,lsl #2] @ value a
mla r5,r0,r3,r5 @ sum = sum + (result1 * a)
add r6,#1
cmp r6,r9
blt 2b
mov r0,r5 @ sum
mov r1,r4 @ product
bl division
mov r0,r3
100:
pop {r1-r9,pc} @ restaur registers
/***************************************************/
/* Calcul modulo inverse */
/***************************************************/
/* r0 containt number, r1 modulo */
/* x0 return result */
inverseModulo:
push {r1-r7,lr} @ save registers
mov r7,r1 // save Modulo
mov r6,r1 // A r0=B
mov r4,#1 // X
mov r5,#0 // Y
1: //
cmp r0,#0 // B = 0
beq 2f
mov r1,r0 // T = B
mov r0,r6 // A
bl division // A / T
mov r0,r3 // B and r2=Q
mov r6,r1 // A=T
mov r1,r4 // T=X
mls r4,r2,r1,r5 // X=Y-(Q*T)
mov r5,r1 // Y=T
b 1b
2:
add r7,r7,r5 // = Y + N
cmp r5,#0 // Y > 0
bge 3f
mov r0,r7
b 100f
3:
mov r0,r5
100:
pop {r1-r7,pc}
/***************************************************/
/* display multi strings */
/***************************************************/
/* r0 contains number strings address */
/* r1 address string1 */
/* r2 address string2 */
/* r3 address string3 */
/* other address on the stack */
/* thinck to add number other address * 4 to add to the stack */
displayStrings: @ INFO: affichageStrings
push {r1-r4,fp,lr} @ save des registres
add fp,sp,#24 @ save paraméters address (6 registers saved * 4 bytes)
mov r4,r0 @ save strings number
cmp r4,#0 @ 0 string -> end
ble 100f
mov r0,r1 @ string 1
bl affichageMess
cmp r4,#1 @ number > 1
ble 100f
mov r0,r2
bl affichageMess
cmp r4,#2
ble 100f
mov r0,r3
bl affichageMess
cmp r4,#3
ble 100f
mov r3,#3
sub r2,r4,#4
1: @ loop extract address string on stack
ldr r0,[fp,r2,lsl #2]
bl affichageMess
subs r2,#1
bge 1b
100:
pop {r1-r4,fp,pc}
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
{{output}}
<pre>
Result = 23
</pre>
=={{header|Arturo}}==
<
[a b x0]: @[a0 b0 0]
result: 1
Line 245 ⟶ 664:
]
print chineseRemainder [3 5 7] [2 3 2]</
{{out}}
<pre>23</pre>
=={{header|AWK}}==
{{trans|C}}
We are using the split-function to create both arrays, thus the indices start at 1. This is the only difference to the C version.
<
BEGIN {
len = split("3 5 7", n)
Line 290 ⟶ 708:
x1 += b0
return x1
}</
{{out}}
<pre>23</pre>
=={{header|BQN}}==
Multiplicative Modular inverse function taken from BQNcrate.
<syntaxhighlight lang="bqn">MulInv←⊣|·⊑{0=𝕨?1‿0;(⌽-(0⋈𝕩⌊∘÷𝕨)⊸×)𝕨𝕊˜𝕨|𝕩}
ChRem←{
num 𝕊 rem:
prod←×´num
prod|+´rem×(⊢×num⊸(MulInv¨))prod⌊∘÷num
}
•Show 3‿5‿7 ChRem 2‿3‿2
•Show 10‿4‿9 ChRem 11‿22‿19</syntaxhighlight><syntaxhighlight lang="text">23
172</syntaxhighlight>
=={{header|Bracmat}}==
{{trans|C}}
<
= a b b0 q x0 x1
. !arg:(?a.?b:?b0)
Line 333 ⟶ 764:
& 2 3 2:?a
& put$(str$(chinese-remainder$(!n.!a) \n))
);</
Output:
<pre>23</pre>
=={{header|C}}==
When n are not pairwise coprime, the program crashes due to division by zero, which is one way to convey error.
<
// returns x where (a * x) % b == 1
Line 377 ⟶ 807:
printf("%d\n", chinese_remainder(n, a, sizeof(n)/sizeof(n[0])));
return 0;
}</
=={{header|C sharp|C#}}==
<
using System.Linq;
Line 432 ⟶ 861:
}
}
}</
=={{header|C++}}==
<
#include <iostream>
#include <numeric>
Line 487 ⟶ 915:
return 0;
}</
{{out}}
<pre>23</pre>
=={{header|Clojure}}==
Modeled after the Python version http://rosettacode.org/wiki/Category:Python
<
(:require [clojure.math.numeric-tower :as math]))
Line 534 ⟶ 961:
(println (chinese_remainder n a))
</syntaxhighlight>
'''Output:'''
Line 540 ⟶ 967:
23
</pre>
=={{header|CoffeeScript}}==
<syntaxhighlight lang="coffeescript">crt = (n,a) ->
sum = 0
prod = n.reduce (a,c) -> a*c
Line 561 ⟶ 987:
x1
print crt [3,5,7], [2,3,2]</
'''Output:'''
<pre>
Line 569 ⟶ 995:
=={{header|Common Lisp}}==
Using function ''invmod'' from [[http://rosettacode.org/wiki/Modular_inverse#Common_Lisp]].
<
(defun chinese-remainder (am)
"Calculates the Chinese Remainder for the given set of integer modulo pairs.
Line 579 ⟶ 1,005:
:do
(incf sum (* a (invmod (/ mtot m) m) (/ mtot m)))))
</syntaxhighlight>
'''Output:'''
Line 610 ⟶ 1,036:
{{trans|Ruby}}
<
last_remainder, remainder = a.abs, b.abs
x, last_x = 0, 1
Line 643 ⟶ 1,069:
puts chinese_remainder([3, 5, 7], [2, 3, 2])
puts chinese_remainder([5, 7, 9, 11], [1, 2, 3, 4])
</syntaxhighlight>
'''Output:'''
Line 650 ⟶ 1,076:
1731
</pre>
=={{header|D}}==
{{trans|Python}}
<
T chineseRemainder(T)(in T[] n, in T[] a) pure nothrow @safe @nogc
Line 692 ⟶ 1,117:
a = [2, 3, 2];
chineseRemainder(n, a).writeln;
}</
{{out}}
<pre>23</pre>
Line 699 ⟶ 1,124:
{{libheader| Velthuis.BigIntegers}}
{{Trans|Java}}
<syntaxhighlight lang="delphi">
program ChineseRemainderTheorem;
Line 763 ⟶ 1,188:
Writeln(chineseRemainder(n, a).ToString);
end.</
{{out}}
<pre>23</pre>
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight lang="text">
func mul_inv a b .
if
if x1
.
.
return x1
.
prod = 1
sum = 0
for i
prod *= n[i]
.
for i
p = prod / n[i]
.
.
n[] = [ 3 5 7 ]
a[] = [ 2 3 2 ]
print h
</syntaxhighlight>
{{out}}
<pre>23</pre>
Line 810 ⟶ 1,235:
=={{header|EchoLisp}}==
'''egcd''' - extended gcd - and '''crt-solve''' - chinese remainder theorem solve - are included in math.lib.
<
(lib 'math)
math.lib v1.10 ® EchoLisp
Line 819 ⟶ 1,244:
(crt-solve '(2 3 2) '(7 1005 15))
💥 error: mod[i] must be co-primes : assertion failed : 1005
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Ruby}}
{{works with|Elixir|1.2}}
Brute-force:
<
def remainder(mods, remainders) do
max = Enum.reduce(mods, fn x,acc -> x*acc end)
Line 837 ⟶ 1,261:
IO.inspect Chinese.remainder([3,5,7], [2,3,2])
IO.inspect Chinese.remainder([10,4,9], [11,22,19])
IO.inspect Chinese.remainder([11,12,13], [10,4,12])</
{{out}}
Line 845 ⟶ 1,269:
[1000]
</pre>
=={{header|Erlang}}==
{{trans|OCaml}}
<
-import(lists, [zip/2, unzip/1, foldl/3, sum/1]).
-export([egcd/2, mod/2, mod_inv/2, chinese_remainder/1]).
Line 888 ⟶ 1,311:
[A*B || {A,B} <- zip(Residues, Inverses)])]),
mod(Solution, ModPI)
end.</
{{out}}
<pre>
Line 898 ⟶ 1,321:
23
</pre>
=={{header|F_Sharp|F#}}==
===[https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Search_by_sieving sieving]===
<
match cs with
| [] -> Some(x)
Line 923 ⟶ 1,345:
| None -> printfn "no solution"
| Some(x) -> printfn "result = %i" x
)</
{{out}}
<pre>result = 23
Line 932 ⟶ 1,354:
<br>
This uses [[Modular_inverse#F.23]]
<
//Chinese Division Theorem: Nigel Galloway: April 3rd., 2017
let CD n g =
Line 938 ⟶ 1,360:
|0 -> None
|fN-> Some ((Seq.fold2(fun n i g -> n+i*(fN/g)*(MI g ((fN/g)%g))) 0 n g)%fN)
</syntaxhighlight>
{{out}}
<pre>
Line 945 ⟶ 1,367:
CD [2;3;2] [3;5;7] -> Some 23
</pre>
=={{header|Factor}}==
<
{ 2 3 2 } { 3 5 7 } chinese-remainder .</
{{out}}
<pre>
23
</pre>
=={{header|Forth}}==
Tested with GNU FORTH
<
dup 0= IF
2drop 1 0
Line 994 ⟶ 1,414:
LOOP
crt-residues[] crt-moduli[] n crt-from-array ;
</syntaxhighlight>
{{out}}
<pre>
Line 1,004 ⟶ 1,424:
:2: Invalid numeric argument
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.
<
#include "gcd.bas"
function mul_inv( a as integer, b as integer ) as integer
Line 1,041 ⟶ 1,526:
dim as integer a(0 to 2) = { 2, 3, 2 }
print chinese_remainder(n(), a())</
{{out}}<pre>23</pre>
Line 1,050 ⟶ 1,535:
Input is validated and useful error messages are emitted if the input data is invalid. If a solution cannot be found, this returns the special value <CODE>undef</CODE>.
<
[r, m, d=0] where r and m are arrays of the remainder terms r and the
modulus terms m respectively. These must be of the same length.
Line 1,091 ⟶ 1,576:
}
println[ChineseRemainder[[2,3,2],[3,5,7]] ]</
{{out}}
<pre>
23
</pre>
=={{header|FunL}}==
<
def crt( congruences ) =
Line 1,104 ⟶ 1,588:
sum( a*modinv(N/n, n)*N/n | (a, n) <- congruences ) mod N
println( crt([(2, 3), (3, 5), (2, 7)]) )</
{{out}}
Line 1,111 ⟶ 1,595:
23
</pre>
=={{header|Go}}==
Go has the Extended Euclidean algorithm in the GCD function for big integers in the standard library. GCD will return 1 only if numbers are coprime, so a result != 1 indicates the error condition.
<
import (
Line 1,152 ⟶ 1,635:
}
fmt.Println(crt(a, n))
}</
{{out}}
Two values, the solution x and an error value.
Line 1,158 ⟶ 1,641:
23 <nil>
</pre>
=={{header|Groovy}}==
{{trans|Java}}
<
static int chineseRemainder(int[] n, int[] a) {
int prod = 1
Line 1,207 ⟶ 1,689:
println(chineseRemainder(n, a))
}
}</
{{out}}
<pre>23</pre>
=={{header|Haskell}}==
{{trans|Erlang}}
<
egcd :: Int -> Int -> (Int, Int)
Line 1,245 ⟶ 1,726:
, ([10, 4, 9], [11, 22, 19])
, ([2, 3, 2], [3, 5, 7])
]</
{{Out}}
<pre>1000
No modular inverse for 418 and 11
23</pre>
=={{header|Icon}} and {{header|Unicon}}==
{{trans|Python}} with error check added.
Works in both languages:
<
procedure main()
Line 1,278 ⟶ 1,758:
}
return if x1 < 0 then x1+b0 else x1
end</
Output:
Line 1,287 ⟶ 1,767:
->
</pre>
=={{header|J}}==
'''Solution''' (''brute force''):<
'''Example''': <
23
11 12 13 crt 10 4 12
1000</
'''Notes''': This is a brute force approach and does not meet the requirement for explicit notification of an an unsolvable set of equations (it just spins forever). A much more thorough and educational approach can be found on the [[j:Essays/Chinese%20Remainder%20Theorem|J wiki's Essay on the Chinese Remainder Thereom]].
=={{header|Java}}==
Translation of [[Chinese_remainder_theorem#Python|Python]] via [[Chinese_remainder_theorem#D|D]]
{{works with|Java|8}}
<
public class ChineseRemainderTheorem {
Line 1,345 ⟶ 1,823:
System.out.println(chineseRemainder(n, a));
}
}</
<pre>23</pre>
=={{header|JavaScript}}==
<
function crt(num, rem) {
let sum = 0;
Line 1,381 ⟶ 1,858:
}
console.log(crt([3,5,7], [2,3,2]))</
'''Output:'''
<pre>
23
</pre>
=={{header|jq}}==
This implementation is similar to the one in C, but raises an error if there is no solution, as illustrated in the last example.
<
def mul_inv(a; b):
Line 1,419 ⟶ 1,895:
else . + (remainders[$i] * $mi * $p)
end )
| . % $prod ;</
'''Examples''':
chinese_remainder([3,5,7]; [2,3,2])
Line 1,427 ⟶ 1,903:
chinese_remainder([10,4,9]; [11,22,19])
# jq: error: nogo: p=36 mods[0]=10
=={{header|Julia}}==
{{works with|Julia|1.2}}
<
Π = prod(n)
mod(sum(ai * invmod(Π ÷ ni, ni) * (Π ÷ ni) for (ni, ai) in zip(n, a)), Π)
end
@show chineseremainder([3, 5, 7], [2, 3, 2])</
{{out}}
<pre>chineseremainder([3, 5, 7], [2, 3, 2]) = 23</pre>
=={{header|Kotlin}}==
{{trans|C}}
<
/* returns x where (a * x) % b == 1 */
Line 1,479 ⟶ 1,953:
val a = intArrayOf(2, 3, 2)
println(chineseRemainder(n, a))
}</
{{out}}
Line 1,485 ⟶ 1,959:
23
</pre>
=={{header|Lobster}}==
<
def extended_gcd(a, b):
Line 1,528 ⟶ 2,001:
print_crt([11,22,19],[10,4,9])
print_crt([100,23],[19,0])
</syntaxhighlight>
{{out}}
<pre>ok 23
Line 1,535 ⟶ 2,008:
ok 1219
</pre>
=={{header|Lua}}==
<
function prodf(a, ...) return a and a * prodf(...) or 1 end
function prodt(t) return prodf(unpack(t)) end
Line 1,582 ⟶ 2,054:
n = {3, 5, 7}
a = {2, 3, 2}
io.write(chineseRemainder(n, a))</
{{out}}
<pre>23</pre>
=={{header|M2000 Interpreter}}==
{{trans|C}}
<syntaxhighlight lang="m2000 interpreter">
Function ChineseRemainder(n(), a()) {
Function mul_inv(a, b) {
Line 1,610 ⟶ 2,082:
}
Print ChineseRemainder((3,5,7), (2,3,2))
</syntaxhighlight>
{{out}}
<pre>23
</pre>
=={{header|Maple}}==
This is a Maple built-in procedure, so it is trivial:
<
23
</syntaxhighlight>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
Very easy, because it is a built-in function:
<
23</
=={{header|MATLAB}} / {{header|Octave}}==
<
s = prod(m) ./ m;
[~, t] = gcd(s, m);
f = s .* t * r';</
{{out}}
<
ans = 23</
=={{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}}==
<
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 1,705 ⟶ 2,198:
ReadChar
END CRT.</
{{out}}
<pre>23</pre>
=={{header|Nim}}==
{{trans|C}}
<
var (a, b, x0) = (a0, b0, 0)
result = 1
Line 1,734 ⟶ 2,226:
sum mod prod
echo chineseRemainder([3,5,7], [2,3,2])</
Output:
<pre>23</pre>
=={{header|OCaml}}==
This is without the Jane Street Ocaml Core Library.
<
exception Modular_inverse
let inverse_mod a = function
Line 1,764 ⟶ 2,255:
with modular_inverse -> None
</syntaxhighlight>
This is using the Jane Street Ocaml Core library.
<
open Option.Monad_infix
Line 1,806 ⟶ 2,297:
|> List.reduce_exn ~f:(+)
|> fun n -> let n' = n mod mod_pi in if n' < 0 then n' + mod_pi else n')
</syntaxhighlight>
{{out}}
<pre>
Line 1,815 ⟶ 2,306:
- : int option = None
</pre>
=={{header|PARI/GP}}==
<
my(m=Mod(0,1));
for(i=1,#residues,
Line 1,824 ⟶ 2,314:
lift(m)
};
chivec([2,3,2], [3,5,7])</
{{out}}
<pre>23</pre>
Pari's chinese function takes a vector in the form <tt>[Mod(a1,n1), Mod(a2, n2), ...]</tt>, so we can do this directly:
<
or to take the residue/moduli array as above:
<
lift(chinese(vector(#residues,i,Mod(residues[i],moduli[i]))))
}</
=={{header|Pascal}}==
A console application in Free Pascal, created with the Lazarus IDE.
Follows the Perl examples: (1) expresses each solution as a residue class; (2) if the moduli are not pairwise coprime, still finds a solution if there is one.
<syntaxhighlight lang="pascal">
// Rosetta Code task "Chinese remainder theorem".
program ChineseRemThm;
uses SysUtils;
type TIntArray = array of integer;
// Defining EXTRA adds optional explanatory code
{$DEFINE EXTRA}
// Return (if possible) a residue res_out that satifies
// res_out = res1 modulo mod1, res_out = res2 modulo mod2.
// Return mod_out = LCM( mod1, mod2), or mod_out = 0 if there's no solution.
procedure Solve2( const res1, res2, mod1, mod2 : integer;
out res_out, mod_out : integer);
var
a, c, d, k, m, m1, m2, r, temp : integer;
p, p_prev : integer;
{$IFDEF EXTRA}
q, q_prev : integer;
{$ENDIF}
begin
if (mod1 = 0) or (mod2 = 0) then
raise SysUtils.Exception.Create( 'Solve2: Modulus cannot be 0');
m1 := Abs( mod1);
m2 := Abs( mod2);
// Extended Euclid's algorithm for HCF( m1, m2), except that only one
// of the Bezout coefficients is needed (here p, could have used q)
c := m1; d := m2;
p :=0; p_prev := 1;
{$IFDEF EXTRA}
q := 1; q_prev := 0;
{$ENDIF}
a := 0;
while (d > 0) do begin
temp := p_prev - a*p; p_prev := p; p := temp;
{$IFDEF EXTRA}
temp := q_prev - a*q; q_prev := q; q := temp;
{$ENDIF}
a := c div d;
temp := c - a*d; c := d; d := temp;
end;
// Here with c = HCF( m1, m2)
{$IFDEF EXTRA}
Assert( c = p*m2 + q*m1); // p and q are the Bezout coefficients
{$ENDIF}
// A soution exists iff c divides (res2 - res1)
k := (res2 - res1) div c;
if res2 - res1 <> k*c then begin
res_out := 0; mod_out := 0; // indicate that there's no xolution
end
else begin
m := (m1 div c) * m2; // m := LCM( m1, m2)
r:= res2 - k*p*m2; // r := a solution modulo m
{$IFDEF EXTRA}
Assert( r = res1 + k*q*m1); // alternative formula in terms of q
{$ENDIF}
// Return the solution in the range 0..(m - 1)
// Don't trust the compiler with a negative argument to mod
if (r >= 0) then r := r mod m
else begin
r := (-r) mod m;
if (r > 0) then r := m - r;
end;
res_out := r; mod_out := m;
end;
end;
// Return (if possible) a residue res_out that satifies
// res_out = res_array[j] modulo mod_array[j], for j = 0..High(res_array).
// Return mod_out = LCM of the moduli, or mod_out = 0 if there's no solution.
procedure SolveMulti( const res_array, mod_array : TIntArray;
out res_out, mod_out : integer);
var
count, k, m, r : integer;
begin
count := Length( mod_array);
if count <> Length( res_array) then
raise SysUtils.Exception.Create( 'Arrays are different sizes')
else if count = 0 then
raise SysUtils.Exception.Create( 'Arrays are empty');
k := 1;
m := mod_array[0]; r := res_array[0];
while (k < count) and (m > 0) do begin
Solve2( r, res_array[k], m, mod_array[k], r, m);
inc(k);
end;
res_out := r; mod_out := m;
end;
// Cosmetic to turn an integer array into a string for printout.
function ArrayToString( a : TIntArray) : string;
var
j : integer;
begin
result := '[';
for j := 0 to High(a) do begin
result := result + SysUtils.IntToStr(a[j]);
if j < High(a) then result := result + ', '
else result := result + ']';
end;
end;
// For the passed-in res_array and mod_array, show the solution
// found by SolveMulti (above), or state that there's no solution.
procedure ShowSolution( const res_array, mod_array : TIntArray);
var
mod_out, res_out : integer;
begin
SolveMulti( res_array, mod_array, res_out, mod_out);
Write( ArrayToString( res_array) + ' mod '
+ ArrayToString( mod_array) + ' --> ');
if mod_out = 0 then
WriteLn( 'No solution')
else
WriteLn( SysUtils.Format( '%d mod %d', [res_out, mod_out]));
end;
// Main routine. Examples for Rosetta Code task.
begin
ShowSolution([2, 3, 2], [3, 5, 7]);
ShowSolution([3, 5, 7], [2, 3, 2]);
ShowSolution([10, 4, 12], [11, 12, 13]);
ShowSolution([1, 2, 3, 4], [5, 7, 9, 11]);
ShowSolution([11, 22, 19], [10, 4, 9]);
ShowSolution([2328, 410], [16256, 5418]);
ShowSolution([19, 0], [100, 23]);
end.
</syntaxhighlight>
{{out}}
<pre>
[2, 3, 2] mod [3, 5, 7] --> 23 mod 105
[3, 5, 7] mod [2, 3, 2] --> 5 mod 6
[10, 4, 12] mod [11, 12, 13] --> 1000 mod 1716
[1, 2, 3, 4] mod [5, 7, 9, 11] --> 1731 mod 3465
[11, 22, 19] mod [10, 4, 9] --> No solution
[2328, 410] mod [16256, 5418] --> 28450328 mod 44037504
[19, 0] mod [100, 23] --> 1219 mod 2300
</pre>
=={{header|Perl}}==
There are at least three CPAN modules for this: ntheory (Math::Prime::Util), Math::ModInt, and Math::Pari. All three handle bigints.
{{libheader|ntheory}}
<
say chinese([2,3], [3,5], [2,7]);</
{{out}}
<pre>23</pre>
The function returns undef if no common residue class exists. The combined modulus can be obtained using the <code>lcm</code> function applied to the moduli (e.g. <code>lcm(3,5,7) = 105</code> in the example above).
<
use Math::ModInt::ChineseRemainder qw(cr_combine);
say cr_combine(mod(2,3),mod(3,5),mod(2,7));</
{{out}}
<pre>mod(23, 105)</pre>
Line 1,853 ⟶ 2,484:
=== Non-pairwise-coprime ===
All three modules will also handle cases where the moduli are not pairwise co-prime but a solution exists, e.g.:
<
say chinese( [2328,16256], [410,5418] ), " mod ", lcm(16256,5418);</
{{out}}
<pre>28450328 mod 44037504</pre>
=={{header|Phix}}==
{{trans|C}}
Uses the function mul_inv() from [[Modular_inverse#Phix]] (reproduced below)
<!--<
<span style="color: #008080;">function</span> <span style="color: #000000;">mul_inv</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">n</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
Line 1,893 ⟶ 2,523:
<span style="color: #0000FF;">?</span><span style="color: #000000;">chinese_remainder</span><span style="color: #0000FF;">({</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">22</span><span style="color: #0000FF;">,</span><span style="color: #000000;">19</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">})</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">chinese_remainder</span><span style="color: #0000FF;">({</span><span style="color: #000000;">100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">23</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">19</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">})</span>
<!--</
{{out}}
<pre>
Line 1,901 ⟶ 2,531:
1219
</pre>
=={{header|PicoLisp}}==
<
(let (B0 B X0 0 X1 1 Q 0 T1 0)
(while (< 1 A)
Line 1,931 ⟶ 2,560:
(chinrem (11 12 13) (10 4 12)) )
(bye)</
=={{header|Prolog}}==
Created with SWI Prolog.
<
product(A, B, C) :- C is A*B.
Line 1,960 ⟶ 2,588:
foldl(crt_fold, As, Ms, Ps, 0, N0),
N is N0 mod M.
</syntaxhighlight>
{{out}}
<pre>
Line 1,977 ⟶ 2,605:
above. Therefore, I had to write another version of the
Chinese Remainder Therorem
<
/* Chinese remainder Theorem: Input chinrest([2,3,2], [3,5,7], R). -----> R == 23
or chinrest([2,3], [5,13], R). ---------> R == 42
Line 2,042 ⟶ 2,670:
S3 is S1-(Q*S2),
a_b_p_s_(B,B1,P,S,P2-P3,S2-S3,GCD).
</syntaxhighlight>
{{out}}
Line 2,053 ⟶ 2,681:
</pre>
=={{header|PureBasic}}==
<
DisableDebugger
DataSection
Line 2,131 ⟶ 2,758:
PrintData(?LBL_n3,?LBL_a3)
PrintN(Str(ChineseRem(?LBL_n3,?LBL_a3)))
Input()</
{{out}}
<pre>[( 2 . 3 )( 3 . 5 )( 2 . 7 )]
Line 2,139 ⟶ 2,766:
[( 11 . 10 )( 22 . 4 )( 19 . 9 )]
x = Division by zero</pre>
=={{header|Python}}==
===Procedural===
====Python 2.7====
<
def chinese_remainder(n, a):
sum = 0
Line 2,168 ⟶ 2,794:
n = [3, 5, 7]
a = [2, 3, 2]
print chinese_remainder(n, a)</
{{out}}
<pre>23</pre>
====Python 3.6====
<
from functools import reduce
def chinese_remainder(n, a):
Line 2,201 ⟶ 2,827:
n = [3, 5, 7]
a = [2, 3, 2]
print(chinese_remainder(n, a))</
{{out}}
<pre>23</pre>
Line 2,212 ⟶ 2,838:
{{Trans|Haskell}}
{{Works with|Python|3.7}}
<
from operator import (add, mul)
Line 2,416 ⟶ 3,042:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>Chinese remainder theorem:
Line 2,427 ⟶ 3,053:
([3, 5, 7], [2, 3, 2]) -> 23
([2, 3, 2], [3, 5, 7]) -> 'No solution: no modular inverse for 6 and 2'</pre>
=={{header|R}}==
{{trans|C}}
<
{
b0 <- b
Line 2,473 ⟶ 3,098:
a <- c(2L, 3L, 2L)
chinese_remainder(n, a)</
{{out}}
<pre>23</pre>
=={{header|Racket}}==
This is more of a demonstration of the built-in function "solve-chinese", than
Line 2,483 ⟶ 3,107:
Take a look in the "math/number-theory" package it's full of goodies!
URL removed -- I can't be doing the Dutch recaptchas I'm getting.
<
(require (only-in math/number-theory solve-chinese))
(define as '(2 3 2))
(define ns '(3 5 7))
(solve-chinese as ns)</
{{out}}
<pre>23</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{trans|C}}
{{works with|Rakudo|2015.12}}
<syntaxhighlight lang="raku"
sub mul-inv($a is copy, $b is copy) {
return 1 if $b == 1;
Line 2,519 ⟶ 3,142:
}
say chinese-remainder(3, 5, 7)(2, 3, 2);</
{{out}}
<pre>23</pre>
=={{header|REXX}}==
===algebraic===
<
parse arg Ns As . /*get optional arguments from the C.L. */
if Ns=='' | Ns=="," then Ns= '3,5,7' /*Ns not specified? Then use default.*/
Line 2,550 ⟶ 3,172:
end /*x*/
say 'no solution found.' /*oops, announce that solution ¬ found.*/</
{{out|output|text= when using the default inputs:}}
<pre>
Line 2,560 ⟶ 3,182:
===congruences sets===
<
parse arg Ns As . /*get optional arguments from the C.L. */
if Ns=='' | Ns=="," then Ns= '3,5,7' /*Ns not specified? Then use default.*/
Line 2,589 ⟶ 3,211:
end /*x*/
say 'no solution found.' /*oops, announce that solution ¬ found.*/</
{{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.
<
def chinese_remainder(mods, remainders)
max = mods.inject( :* )
Line 2,603 ⟶ 3,288:
p chinese_remainder([3,5,7], [2,3,2]) #=> 23
p chinese_remainder([10,4,9], [11,22,19]) #=> nil
</syntaxhighlight>
Similar to above, but working with large(r) numbers.
<
def extended_gcd(a, b)
last_remainder, remainder = a.abs, b.abs
Line 2,634 ⟶ 3,319:
p chinese_remainder([17353461355013928499, 3882485124428619605195281, 13563122655762143587], [7631415079307304117, 1248561880341424820456626, 2756437267211517231]) #=> 937307771161836294247413550632295202816
p chinese_remainder([10,4,9], [11,22,19]) #=> nil
</syntaxhighlight>
=={{header|Rust}}==
<
if a == 0 {
(b, 0, 1)
Line 2,677 ⟶ 3,362:
}
}</
=={{header|Scala}}==
{{Out}}Best seen running in your browser either by [https://scalafiddle.io/sf/9QZvFht/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/njcaS3BFT6GtaWT2cHiwXg Scastie (remote JVM)].
<
object ChineseRemainderTheorem extends App {
Line 2,721 ⟶ 3,405:
println(chineseRemainder(List(11, 22, 19), List(10, 4, 9)))
}</
=={{header|Seed7}}==
<
include "bigint.s7i";
Line 2,747 ⟶ 3,430:
end for;
writeln(sum mod prod);
end func;</
{{out}}
Line 2,753 ⟶ 3,436:
23
</pre>
=={{header|Sidef}}==
{{trans|Raku}}
<
var N = n.prod
func (*a) {
Line 2,766 ⟶ 3,448:
}
say chinese_remainder(3, 5, 7)(2, 3, 2)</
{{out}}
<pre>
23
</pre>
=={{header|SQL}}==
{{works with|SQLite|3.34.0}}
<
insert into inputs values (2, 3), (3, 5), (2, 7);
Line 2,835 ⟶ 3,516:
where
a=1 and multiplicative_inverse.id = inputs.modulus;
</syntaxhighlight>
{{out}}
<pre>23</pre>
=={{header|Swift}}==
<
/*
Line 2,946 ⟶ 3,626:
let x = crt(a,n)
print(x)</
{{out}}
<pre>23</pre>
=={{header|Tcl}}==
{{trans|C}}
<
if {$b == 1} {return 1}
set b0 $b; set x0 0; set x1 1
Line 2,970 ⟶ 3,649:
expr {$sum % $prod}
}
puts [chineseRemainder {3 5 7} {2 3 2}]</
{{out}}
<pre>23</pre>
=={{header|uBasic/4tH}}==
{{trans|C}}
<syntaxhighlight lang="text">@(000) = 3 : @(001) = 5 : @(002) = 7
@(100) = 2 : @(101) = 3 : @(102) = 2
Line 3,029 ⟶ 3,707:
Return (c@ % b@)
</syntaxhighlight>
{{out}}
<pre>
Line 3,037 ⟶ 3,715:
0 OK, 0:1034
</pre>
=={{header|VBA}}==
Uses the function mul_inv() from [[Modular_inverse#VBA]]
{{trans|Phix}}<
Dim p As Long, prod As Long, tot As Long
prod = 1: tot = 0
Line 3,063 ⟶ 3,740:
Debug.Print chinese_remainder([{11,22,19}], [{10,4,9}])
Debug.Print chinese_remainder([{100,23}], [{19,0}])
End Sub</
<pre> 23
1000
fail
1219 </pre>
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Function ModularMultiplicativeInverse(a As Integer, m As Integer) As Integer
Line 3,108 ⟶ 3,784:
End Sub
End Module</
{{out}}
<pre>23 = 2 (mod 3)
Line 3,116 ⟶ 3,792:
=={{header|Wren}}==
{{trans|C}}
<
var mulInv = Fn.new { |a, b|
if (b == 1) return 1
Line 3,147 ⟶ 3,823:
var n = [3, 5, 7]
var a = [2, 3, 2]
System.print(chineseRemainder.call(n, a))</
{{out}}
<pre>
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>
Line 3,157 ⟶ 3,873:
{{trans|Go}}
Using the GMP library, gcdExt is the Extended Euclidean algorithm.
<
fcn crt(xs,ys){
Line 3,169 ⟶ 3,885:
}
return(X % p);
}</
<
println(crt(T(11,12,13),T(10,4,12))); //-->1000
println(crt(T(11,22,19), T(10,4,9))); //-->ValueError: 11 not coprime</
=={{header|ZX Spectrum Basic}}==
{{trans|C}}
<
20 FOR i=1 TO 3
30 READ n(i),a(i)
Line 3,199 ⟶ 3,914:
1060 GO TO 1020
1100 IF x1<0 THEN LET x1=x1+b0
1110 RETURN </
<pre>23</pre>
| |||