Chinese remainder theorem: Difference between revisions
m
syntax highlighting fixup automation
(add bqn) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 53:
=={{header|11l}}==
{{trans|Python}}
<
V b0 = b
V x0 = 0
Line 77:
V n = [3, 5, 7]
V a = [2, 3, 2]
print(chinese_remainder(n, a))</
{{out}}
<pre>23</pre>
Line 83:
=={{header|360 Assembly}}==
{{trans|REXX}}
<
CHINESE CSECT
USING CHINESE,R12 base addr
Line 126:
NOSOL DC CL17'no solution found'
YREGS
END CHINESE</
{{out}}
<pre>
Line 133:
=={{header|Action!}}==
<
INT b0,x0,x1,q,tmp
Line 179:
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 190:
Using the package Mod_Inv from [[http://rosettacode.org/wiki/Modular_inverse#Ada]].
<
procedure Chin_Rema is
Line 209:
end loop;
Ada.Text_IO.Put_Line(Integer'Image(Sum mod Prod));
end Chin_Rema;</
=={{header|Arturo}}==
<
[a b x0]: @[a0 b0 0]
result: 1
Line 245:
]
print chineseRemainder [3 5 7] [2 3 2]</
{{out}}
Line 254:
{{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:
x1 += b0
return x1
}</
{{out}}
<pre>23</pre>
Line 298:
Multiplicative Modular inverse function taken from BQNcrate.
<
ChRem←{
num 𝕊 rem:
Line 306:
•Show 3‿5‿7 ChRem 2‿3‿2
•Show 10‿4‿9 ChRem 11‿22‿19</
172</
=={{header|Bracmat}}==
{{trans|C}}
<
= a b b0 q x0 x1
. !arg:(?a.?b:?b0)
Line 348:
& 2 3 2:?a
& put$(str$(chinese-remainder$(!n.!a) \n))
);</
Output:
<pre>23</pre>
Line 354:
=={{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 392:
printf("%d\n", chinese_remainder(n, a, sizeof(n)/sizeof(n[0])));
return 0;
}</
=={{header|C sharp|C#}}==
<
using System.Linq;
Line 447:
}
}
}</
=={{header|C++}}==
<
#include <iostream>
#include <numeric>
Line 502:
return 0;
}</
{{out}}
<pre>23</pre>
Line 508:
=={{header|Clojure}}==
Modeled after the Python version http://rosettacode.org/wiki/Category:Python
<
(:require [clojure.math.numeric-tower :as math]))
Line 549:
(println (chinese_remainder n a))
</syntaxhighlight>
'''Output:'''
Line 557:
=={{header|Coffeescript}}==
<
sum = 0
prod = n.reduce (a,c) -> a*c
Line 576:
x1
print crt [3,5,7], [2,3,2]</
'''Output:'''
<pre>
Line 584:
=={{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 594:
:do
(incf sum (* a (invmod (/ mtot m) m) (/ mtot m)))))
</syntaxhighlight>
'''Output:'''
Line 625:
{{trans|Ruby}}
<
last_remainder, remainder = a.abs, b.abs
x, last_x = 0, 1
Line 658:
puts chinese_remainder([3, 5, 7], [2, 3, 2])
puts chinese_remainder([5, 7, 9, 11], [1, 2, 3, 4])
</syntaxhighlight>
'''Output:'''
Line 668:
=={{header|D}}==
{{trans|Python}}
<
T chineseRemainder(T)(in T[] n, in T[] a) pure nothrow @safe @nogc
Line 707:
a = [2, 3, 2];
chineseRemainder(n, a).writeln;
}</
{{out}}
<pre>23</pre>
Line 714:
{{libheader| Velthuis.BigIntegers}}
{{Trans|Java}}
<
program ChineseRemainderTheorem;
Line 778:
Writeln(chineseRemainder(n, a).ToString);
end.</
{{out}}
<pre>23</pre>
Line 785:
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight lang=text>func mul_inv a b . x1 .
b0 = b
x1 = 1
Line 819:
a[] = [ 2 3 2 ]
call remainder n[] a[] h
print h</
{{out}}
<pre>23</pre>
Line 825:
=={{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 834:
(crt-solve '(2 3 2) '(7 1005 15))
💥 error: mod[i] must be co-primes : assertion failed : 1005
</syntaxhighlight>
=={{header|Elixir}}==
Line 840:
{{works with|Elixir|1.2}}
Brute-force:
<
def remainder(mods, remainders) do
max = Enum.reduce(mods, fn x,acc -> x*acc end)
Line 852:
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 863:
=={{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 903:
[A*B || {A,B} <- zip(Residues, Inverses)])]),
mod(Solution, ModPI)
end.</
{{out}}
<pre>
Line 916:
=={{header|F_Sharp|F#}}==
===[https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Search_by_sieving sieving]===
<
match cs with
| [] -> Some(x)
Line 938:
| None -> printfn "no solution"
| Some(x) -> printfn "result = %i" x
)</
{{out}}
<pre>result = 23
Line 947:
<br>
This uses [[Modular_inverse#F.23]]
<
//Chinese Division Theorem: Nigel Galloway: April 3rd., 2017
let CD n g =
Line 953:
|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 962:
=={{header|Factor}}==
<
{ 2 3 2 } { 3 5 7 } chinese-remainder .</
{{out}}
<pre>
Line 971:
=={{header|Forth}}==
Tested with GNU FORTH
<
dup 0= IF
2drop 1 0
Line 1,009:
LOOP
crt-residues[] crt-moduli[] n crt-from-array ;
</syntaxhighlight>
{{out}}
<pre>
Line 1,023:
=={{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,056:
dim as integer a(0 to 2) = { 2, 3, 2 }
print chinese_remainder(n(), a())</
{{out}}<pre>23</pre>
Line 1,065:
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,106:
}
println[ChineseRemainder[[2,3,2],[3,5,7]] ]</
{{out}}
<pre>
Line 1,113:
=={{header|FunL}}==
<
def crt( congruences ) =
Line 1,119:
sum( a*modinv(N/n, n)*N/n | (a, n) <- congruences ) mod N
println( crt([(2, 3), (3, 5), (2, 7)]) )</
{{out}}
Line 1,129:
=={{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,167:
}
fmt.Println(crt(a, n))
}</
{{out}}
Two values, the solution x and an error value.
Line 1,176:
=={{header|Groovy}}==
{{trans|Java}}
<
static int chineseRemainder(int[] n, int[] a) {
int prod = 1
Line 1,222:
println(chineseRemainder(n, a))
}
}</
{{out}}
<pre>23</pre>
Line 1,228:
=={{header|Haskell}}==
{{trans|Erlang}}
<
egcd :: Int -> Int -> (Int, Int)
Line 1,260:
, ([10, 4, 9], [11, 22, 19])
, ([2, 3, 2], [3, 5, 7])
]</
{{Out}}
<pre>1000
Line 1,270:
{{trans|Python}} with error check added.
Works in both languages:
<
procedure main()
Line 1,293:
}
return if x1 < 0 then x1+b0 else x1
end</
Output:
Line 1,305:
=={{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]].
Line 1,315:
Translation of [[Chinese_remainder_theorem#Python|Python]] via [[Chinese_remainder_theorem#D|D]]
{{works with|Java|8}}
<
public class ChineseRemainderTheorem {
Line 1,360:
System.out.println(chineseRemainder(n, a));
}
}</
<pre>23</pre>
=={{header|JavaScript}}==
<
function crt(num, rem) {
let sum = 0;
Line 1,396:
}
console.log(crt([3,5,7], [2,3,2]))</
'''Output:'''
<pre>
Line 1,404:
=={{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,434:
else . + (remainders[$i] * $mi * $p)
end )
| . % $prod ;</
'''Examples''':
chinese_remainder([3,5,7]; [2,3,2])
Line 1,446:
{{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}}
Line 1,458:
=={{header|Kotlin}}==
{{trans|C}}
<
/* returns x where (a * x) % b == 1 */
Line 1,494:
val a = intArrayOf(2, 3, 2)
println(chineseRemainder(n, a))
}</
{{out}}
Line 1,502:
=={{header|Lobster}}==
<
def extended_gcd(a, b):
Line 1,543:
print_crt([11,22,19],[10,4,9])
print_crt([100,23],[19,0])
</syntaxhighlight>
{{out}}
<pre>ok 23
Line 1,552:
=={{header|Lua}}==
<
function prodf(a, ...) return a and a * prodf(...) or 1 end
function prodt(t) return prodf(unpack(t)) end
Line 1,597:
n = {3, 5, 7}
a = {2, 3, 2}
io.write(chineseRemainder(n, a))</
{{out}}
<pre>23</pre>
=={{header|M2000 Interpreter}}==
{{trans|C}}
<
Function ChineseRemainder(n(), a()) {
Function mul_inv(a, b) {
Line 1,625:
}
Print ChineseRemainder((3,5,7), (2,3,2))
</syntaxhighlight>
{{out}}
<pre>23
Line 1,633:
=={{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|Modula-2}}==
<
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 1,720:
ReadChar
END CRT.</
{{out}}
<pre>23</pre>
Line 1,726:
=={{header|Nim}}==
{{trans|C}}
<
var (a, b, x0) = (a0, b0, 0)
result = 1
Line 1,749:
sum mod prod
echo chineseRemainder([3,5,7], [2,3,2])</
Output:
<pre>23</pre>
Line 1,755:
=={{header|OCaml}}==
This is without the Jane Street Ocaml Core Library.
<
exception Modular_inverse
let inverse_mod a = function
Line 1,779:
with modular_inverse -> None
</syntaxhighlight>
This is using the Jane Street Ocaml Core library.
<
open Option.Monad_infix
Line 1,821:
|> 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,832:
=={{header|PARI/GP}}==
<
my(m=Mod(0,1));
for(i=1,#residues,
Line 1,839:
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}}==
Line 1,854:
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.
<
// Rosetta Code task "Chinese remainder theorem".
program ChineseRemThm;
Line 1,981:
ShowSolution([19, 0], [100, 23]);
end.
</syntaxhighlight>
{{out}}
<pre>
Line 1,996:
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 2,011:
=== 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>
Line 2,019:
{{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 2,051:
<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 2,061:
=={{header|PicoLisp}}==
<
(let (B0 B X0 0 X1 1 Q 0 T1 0)
(while (< 1 A)
Line 2,089:
(chinrem (11 12 13) (10 4 12)) )
(bye)</
=={{header|Prolog}}==
Created with SWI Prolog.
<
product(A, B, C) :- C is A*B.
Line 2,118:
foldl(crt_fold, As, Ms, Ps, 0, N0),
N is N0 mod M.
</syntaxhighlight>
{{out}}
<pre>
Line 2,135:
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,200:
S3 is S1-(Q*S2),
a_b_p_s_(B,B1,P,S,P2-P3,S2-S3,GCD).
</syntaxhighlight>
{{out}}
Line 2,213:
=={{header|PureBasic}}==
<
DisableDebugger
DataSection
Line 2,289:
PrintData(?LBL_n3,?LBL_a3)
PrintN(Str(ChineseRem(?LBL_n3,?LBL_a3)))
Input()</
{{out}}
<pre>[( 2 . 3 )( 3 . 5 )( 2 . 7 )]
Line 2,301:
===Procedural===
====Python 2.7====
<
def chinese_remainder(n, a):
sum = 0
Line 2,326:
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,359:
n = [3, 5, 7]
a = [2, 3, 2]
print(chinese_remainder(n, a))</
{{out}}
<pre>23</pre>
Line 2,370:
{{Trans|Haskell}}
{{Works with|Python|3.7}}
<
from operator import (add, mul)
Line 2,574:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>Chinese remainder theorem:
Line 2,588:
=={{header|R}}==
{{trans|C}}
<
{
b0 <- b
Line 2,631:
a <- c(2L, 3L, 2L)
chinese_remainder(n, a)</
{{out}}
<pre>23</pre>
Line 2,641:
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>
Line 2,653:
{{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,677:
}
say chinese-remainder(3, 5, 7)(2, 3, 2);</
{{out}}
<pre>23</pre>
Line 2,683:
=={{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,708:
end /*x*/
say 'no solution found.' /*oops, announce that solution ¬ found.*/</
{{out|output|text= when using the default inputs:}}
<pre>
Line 2,718:
===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,747:
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|Ruby}}==
Brute-force.
<
def chinese_remainder(mods, remainders)
max = mods.inject( :* )
Line 2,761:
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,792:
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,835:
}
}</
=={{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,879:
println(chineseRemainder(List(11, 22, 19), List(10, 4, 9)))
}</
=={{header|Seed7}}==
<
include "bigint.s7i";
Line 2,905:
end for;
writeln(sum mod prod);
end func;</
{{out}}
Line 2,914:
=={{header|Sidef}}==
{{trans|Raku}}
<
var N = n.prod
func (*a) {
Line 2,924:
}
say chinese_remainder(3, 5, 7)(2, 3, 2)</
{{out}}
<pre>
Line 2,934:
{{works with|SQLite|3.34.0}}
<
insert into inputs values (2, 3), (3, 5), (2, 7);
Line 2,993:
where
a=1 and multiplicative_inverse.id = inputs.modulus;
</syntaxhighlight>
{{out}}
Line 2,999:
=={{header|Swift}}==
<
/*
Line 3,104:
let x = crt(a,n)
print(x)</
{{out}}
Line 3,111:
=={{header|Tcl}}==
{{trans|C}}
<
if {$b == 1} {return 1}
set b0 $b; set x0 0; set x1 1
Line 3,128:
expr {$sum % $prod}
}
puts [chineseRemainder {3 5 7} {2 3 2}]</
{{out}}
<pre>23</pre>
Line 3,134:
=={{header|uBasic/4tH}}==
{{trans|C}}
<syntaxhighlight lang=text>@(000) = 3 : @(001) = 5 : @(002) = 7
@(100) = 2 : @(101) = 3 : @(102) = 2
Line 3,187:
Return (c@ % b@)
</syntaxhighlight>
{{out}}
<pre>
Line 3,198:
=={{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,221:
Debug.Print chinese_remainder([{11,22,19}], [{10,4,9}])
Debug.Print chinese_remainder([{100,23}], [{19,0}])
End Sub</
<pre> 23
1000
Line 3,229:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Function ModularMultiplicativeInverse(a As Integer, m As Integer) As Integer
Line 3,266:
End Sub
End Module</
{{out}}
<pre>23 = 2 (mod 3)
Line 3,274:
=={{header|Wren}}==
{{trans|C}}
<
var mulInv = Fn.new { |a, b|
if (b == 1) return 1
Line 3,305:
var n = [3, 5, 7]
var a = [2, 3, 2]
System.print(chineseRemainder.call(n, a))</
{{out}}
Line 3,315:
{{trans|Go}}
Using the GMP library, gcdExt is the Extended Euclidean algorithm.
<
fcn crt(xs,ys){
Line 3,327:
}
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,357:
1060 GO TO 1020
1100 IF x1<0 THEN LET x1=x1+b0
1110 RETURN </
<pre>23</pre>
|