Chinese remainder theorem: Difference between revisions

=={{header|11l}}==

{{trans|Python}}

V b0 = b

V x0 = 0

V n = [3, 5, 7]

V a = [2, 3, 2]

{{out}}

<pre>23</pre>

=={{header|360 Assembly}}==

{{trans|REXX}}

CHINESE CSECT

USING CHINESE,R12 base addr

NOSOL DC CL17'no solution found'

YREGS

{{out}}

<pre>

=={{header|Action!}}==

INT b0,x0,x1,q,tmp

res=ChineseRemainder(n,a,3)

PrintI(res)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Chinese_remainder_theorem.png Screenshot from Atari 8-bit computer]

Using the package Mod_Inv from [[http://rosettacode.org/wiki/Modular_inverse#Ada]].

procedure Chin_Rema is

end loop;

Ada.Text_IO.Put_Line(Integer'Image(Sum mod Prod));

=={{header|Arturo}}==

[a b x0]: @[a0 b0 0]

result: 1

]

{{out}}

{{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)

x1 += b0

return x1

{{out}}

<pre>23</pre>

Multiplicative Modular inverse function taken from BQNcrate.

ChRem←{

num 𝕊 rem:

•Show 3‿5‿7 ChRem 2‿3‿2

=={{header|Bracmat}}==

{{trans|C}}

= a b b0 q x0 x1

. !arg:(?a.?b:?b0)

& 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

printf("%d\n", chinese_remainder(n, a, sizeof(n)/sizeof(n[0])));

return 0;

=={{header|C sharp|C#}}==

using System.Linq;

}

}

=={{header|C++}}==

#include <iostream>

#include <numeric>

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]))

(println (chinese_remainder n a))

'''Output:'''

=={{header|Coffeescript}}==

sum = 0

prod = n.reduce (a,c) -> a*c

x1

'''Output:'''

<pre>

=={{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.

:do

(incf sum (* a (invmod (/ mtot m) m) (/ mtot m)))))

'''Output:'''

{{trans|Ruby}}

last_remainder, remainder = a.abs, b.abs

x, last_x = 0, 1

puts chinese_remainder([3, 5, 7], [2, 3, 2])

puts chinese_remainder([5, 7, 9, 11], [1, 2, 3, 4])

'''Output:'''

=={{header|D}}==

{{trans|Python}}

T chineseRemainder(T)(in T[] n, in T[] a) pure nothrow @safe @nogc

a = [2, 3, 2];

chineseRemainder(n, a).writeln;

{{out}}

<pre>23</pre>

{{libheader| Velthuis.BigIntegers}}

{{Trans|Java}}

program ChineseRemainderTheorem;

Writeln(chineseRemainder(n, a).ToString);

{{out}}

<pre>23</pre>

=={{header|EasyLang}}==

{{trans|C}}

b0 = b

x1 = 1

a[] = [ 2 3 2 ]

call remainder n[] a[] h

{{out}}

<pre>23</pre>

=={{header|EchoLisp}}==

'''egcd''' - extended gcd - and '''crt-solve''' - chinese remainder theorem solve - are included in math.lib.

(lib 'math)

math.lib v1.10 ® EchoLisp

(crt-solve '(2 3 2) '(7 1005 15))

💥 error: mod[i] must be co-primes : assertion failed : 1005

=={{header|Elixir}}==

{{works with|Elixir|1.2}}

Brute-force:

def remainder(mods, remainders) do

max = Enum.reduce(mods, fn x,acc -> x*acc end)

IO.inspect Chinese.remainder([3,5,7], [2,3,2])

IO.inspect Chinese.remainder([10,4,9], [11,22,19])

{{out}}

=={{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]).

[A*B || {A,B} <- zip(Residues, Inverses)])]),

mod(Solution, ModPI)

{{out}}

<pre>

=={{header|F_Sharp|F#}}==

===[https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Search_by_sieving sieving]===

match cs with

| [] -> Some(x)

| None -> printfn "no solution"

| Some(x) -> printfn "result = %i" x

{{out}}

<pre>result = 23

<br>

This uses [[Modular_inverse#F.23]]

//Chinese Division Theorem: Nigel Galloway: April 3rd., 2017

let CD n g =

|0 -> None

|fN-> Some ((Seq.fold2(fun n i g -> n+i*(fN/g)*(MI g ((fN/g)%g))) 0 n g)%fN)

{{out}}

<pre>

=={{header|Factor}}==

{{out}}

<pre>

=={{header|Forth}}==

Tested with GNU FORTH

dup 0= IF

2drop 1 0

LOOP

crt-residues[] crt-moduli[] n crt-from-array ;

{{out}}

<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

dim as integer a(0 to 2) = { 2, 3, 2 }

{{out}}<pre>23</pre>

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.

}

{{out}}

<pre>

=={{header|FunL}}==

def crt( congruences ) =

sum( a*modinv(N/n, n)*N/n | (a, n) <- congruences ) mod N

{{out}}

=={{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 (

}

fmt.Println(crt(a, n))

{{out}}

Two values, the solution x and an error value.

=={{header|Groovy}}==

{{trans|Java}}

static int chineseRemainder(int[] n, int[] a) {

int prod = 1

println(chineseRemainder(n, a))

}

{{out}}

<pre>23</pre>

=={{header|Haskell}}==

{{trans|Erlang}}

egcd :: Int -> Int -> (Int, Int)

, ([10, 4, 9], [11, 22, 19])

, ([2, 3, 2], [3, 5, 7])

{{Out}}

<pre>1000

{{trans|Python}} with error check added.

Works in both languages:

procedure main()

}

return if x1 < 0 then x1+b0 else x1

Output:

=={{header|J}}==

23

11 12 13 crt 10 4 12

'''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]].

Translation of [[Chinese_remainder_theorem#Python|Python]] via [[Chinese_remainder_theorem#D|D]]

{{works with|Java|8}}

public class ChineseRemainderTheorem {

System.out.println(chineseRemainder(n, a));

}

<pre>23</pre>

=={{header|JavaScript}}==

function crt(num, rem) {

let sum = 0;

}

'''Output:'''

<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):

else . + (remainders[$i] * $mi * $p)

end )

'''Examples''':

chinese_remainder([3,5,7]; [2,3,2])

{{works with|Julia|1.2}}

Π = prod(n)

mod(sum(ai * invmod(Π ÷ ni, ni) * (Π ÷ ni) for (ni, ai) in zip(n, a)), Π)

end

{{out}}

=={{header|Kotlin}}==

{{trans|C}}

/* returns x where (a * x) % b == 1 */

val a = intArrayOf(2, 3, 2)

println(chineseRemainder(n, a))

{{out}}

=={{header|Lobster}}==

def extended_gcd(a, b):

print_crt([11,22,19],[10,4,9])

print_crt([100,23],[19,0])

{{out}}

<pre>ok 23

=={{header|Lua}}==

function prodf(a, ...) return a and a * prodf(...) or 1 end

function prodt(t) return prodf(unpack(t)) end

n = {3, 5, 7}

a = {2, 3, 2}

{{out}}

<pre>23</pre>

=={{header|M2000 Interpreter}}==

{{trans|C}}

Function ChineseRemainder(n(), a()) {

Function mul_inv(a, b) {

}

Print ChineseRemainder((3,5,7), (2,3,2))

{{out}}

<pre>23

=={{header|Maple}}==

This is a Maple built-in procedure, so it is trivial:

23

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Very easy, because it is a built-in function:

=={{header|MATLAB}} / {{header|Octave}}==

s = prod(m) ./ m;

[~, t] = gcd(s, m);

{{out}}

=={{header|Modula-2}}==

FROM FormatString IMPORT FormatString;

FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

ReadChar

{{out}}

<pre>23</pre>

=={{header|Nim}}==

{{trans|C}}

var (a, b, x0) = (a0, b0, 0)

result = 1

sum mod prod

Output:

<pre>23</pre>

=={{header|OCaml}}==

This is without the Jane Street Ocaml Core Library.

exception Modular_inverse

let inverse_mod a = function

with modular_inverse -> None

This is using the Jane Street Ocaml Core library.

open Option.Monad_infix

|> List.reduce_exn ~f:(+)

|> fun n -> let n' = n mod mod_pi in if n' < 0 then n' + mod_pi else n')

{{out}}

<pre>

=={{header|PARI/GP}}==

my(m=Mod(0,1));

for(i=1,#residues,

lift(m)

};

{{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}}==

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;

ShowSolution([19, 0], [100, 23]);

end.

{{out}}

<pre>

There are at least three CPAN modules for this: ntheory (Math::Prime::Util), Math::ModInt, and Math::Pari. All three handle bigints.

{{libheader|ntheory}}

{{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);

{{out}}

<pre>mod(23, 105)</pre>

=== Non-pairwise-coprime ===

All three modules will also handle cases where the moduli are not pairwise co-prime but a solution exists, e.g.:

{{out}}

<pre>28450328 mod 44037504</pre>

{{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>

<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>

=={{header|PicoLisp}}==

(let (B0 B X0 0 X1 1 Q 0 T1 0)

(while (< 1 A)

(chinrem (11 12 13) (10 4 12)) )

=={{header|Prolog}}==

Created with SWI Prolog.

product(A, B, C) :- C is A*B.

foldl(crt_fold, As, Ms, Ps, 0, N0),

N is N0 mod M.

{{out}}

<pre>

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

S3 is S1-(Q*S2),

a_b_p_s_(B,B1,P,S,P2-P3,S2-S3,GCD).

{{out}}

=={{header|PureBasic}}==

DisableDebugger

DataSection

PrintData(?LBL_n3,?LBL_a3)

PrintN(Str(ChineseRem(?LBL_n3,?LBL_a3)))

{{out}}

<pre>[( 2 . 3 )( 3 . 5 )( 2 . 7 )]

===Procedural===

====Python 2.7====

def chinese_remainder(n, a):

sum = 0

n = [3, 5, 7]

a = [2, 3, 2]

{{out}}

<pre>23</pre>

====Python 3.6====

from functools import reduce

def chinese_remainder(n, a):

n = [3, 5, 7]

a = [2, 3, 2]

{{out}}

<pre>23</pre>

{{Trans|Haskell}}

{{Works with|Python|3.7}}

from operator import (add, mul)

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>Chinese remainder theorem:

=={{header|R}}==

{{trans|C}}

{

b0 <- b

a <- c(2L, 3L, 2L)

{{out}}

<pre>23</pre>

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))

{{out}}

<pre>23</pre>

{{trans|C}}

{{works with|Rakudo|2015.12}}

sub mul-inv($a is copy, $b is copy) {

return 1 if $b == 1;

}

{{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.*/

end /*x*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

===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.*/

end /*x*/

{{out|output|text=&nbsp; is identical to the 1^st REXX version.}} <br><br>

=={{header|Ruby}}==

Brute-force.

def chinese_remainder(mods, remainders)

max = mods.inject( :* )

p chinese_remainder([3,5,7], [2,3,2]) #=> 23

p chinese_remainder([10,4,9], [11,22,19]) #=> nil

Similar to above, but working with large(r) numbers.

def extended_gcd(a, b)

last_remainder, remainder = a.abs, b.abs

p chinese_remainder([17353461355013928499, 3882485124428619605195281, 13563122655762143587], [7631415079307304117, 1248561880341424820456626, 2756437267211517231]) #=> 937307771161836294247413550632295202816

p chinese_remainder([10,4,9], [11,22,19]) #=> nil

=={{header|Rust}}==

if a == 0 {

(b, 0, 1)

}

=={{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 {

println(chineseRemainder(List(11, 22, 19), List(10, 4, 9)))

=={{header|Seed7}}==

include "bigint.s7i";

end for;

writeln(sum mod prod);

{{out}}

=={{header|Sidef}}==

{{trans|Raku}}

var N = n.prod

func (*a) {

}

{{out}}

<pre>

{{works with|SQLite|3.34.0}}

insert into inputs values (2, 3), (3, 5), (2, 7);

where

a=1 and multiplicative_inverse.id = inputs.modulus;

{{out}}

=={{header|Swift}}==

/*

let x = crt(a,n)

{{out}}

=={{header|Tcl}}==

{{trans|C}}

if {$b == 1} {return 1}

set b0 $b; set x0 0; set x1 1

expr {$sum % $prod}

}

{{out}}

<pre>23</pre>

=={{header|uBasic/4tH}}==

{{trans|C}}

@(100) = 2 : @(101) = 3 : @(102) = 2

Return (c@ % b@)

{{out}}

<pre>

=={{header|VBA}}==

Uses the function mul_inv() from [[Modular_inverse#VBA]]

Dim p As Long, prod As Long, tot As Long

prod = 1: tot = 0

Debug.Print chinese_remainder([{11,22,19}], [{10,4,9}])

Debug.Print chinese_remainder([{100,23}], [{19,0}])

<pre> 23

1000

=={{header|Visual Basic .NET}}==

{{trans|C#}}

Function ModularMultiplicativeInverse(a As Integer, m As Integer) As Integer

End Sub

{{out}}

<pre>23 = 2 (mod 3)

=={{header|Wren}}==

{{trans|C}}

var mulInv = Fn.new { |a, b|

if (b == 1) return 1

var n = [3, 5, 7]

var a = [2, 3, 2]

{{out}}

{{trans|Go}}

Using the GMP library, gcdExt is the Extended Euclidean algorithm.

fcn crt(xs,ys){

}

return(X % p);

println(crt(T(11,12,13),T(10,4,12))); //-->1000

=={{header|ZX Spectrum Basic}}==

{{trans|C}}

20 FOR i=1 TO 3

30 READ n(i),a(i)

1060 GO TO 1020

1100 IF x1<0 THEN LET x1=x1+b0

<pre>23</pre>