How to resolve the algorithm Chinese remainder theorem step by step in the Prolog programming language

Published on 12 May 2024 09:40 PM
#Prolog

How to resolve the algorithm Chinese remainder theorem step by step in the Prolog programming language

Table of Contents

Problem Statement

Suppose

n

1

{\displaystyle n_{1}}

,

n

2

{\displaystyle n_{2}}

,

…

{\displaystyle \ldots }

,

n

k

{\displaystyle n_{k}}

are positive integers that are pairwise co-prime.   Then, for any given sequence of integers

a

1

{\displaystyle a_{1}}

,

a

2

{\displaystyle a_{2}}

,

…

{\displaystyle \dots }

,

a

k

{\displaystyle a_{k}}

,   there exists an integer

x

{\displaystyle x}

solving the following system of simultaneous congruences: Furthermore, all solutions

x

{\displaystyle x}

of this system are congruent modulo the product,

N

n

1

n

2

…

n

k

{\displaystyle N=n_{1}n_{2}\ldots n_{k}}

.

Write a program to solve a system of linear congruences by applying the   Chinese Remainder Theorem. If the system of equations cannot be solved, your program must somehow indicate this. (It may throw an exception or return a special false value.) Since there are infinitely many solutions, the program should return the unique solution

s

{\displaystyle s}

where

0 ≤ s ≤

n

1

n

2

…

n

k

{\displaystyle 0\leq s\leq n_{1}n_{2}\ldots n_{k}}

.

Show the functionality of this program by printing the result such that the

n

{\displaystyle n}

's   are

[ 3 , 5 , 7 ]

{\displaystyle [3,5,7]}

and the

a

{\displaystyle a}

's   are

[ 2 , 3 , 2 ]

{\displaystyle [2,3,2]}

.

Algorithm:   The following algorithm only applies if the

n

i

{\displaystyle n_{i}}

's   are pairwise co-prime. Suppose, as above, that a solution is required for the system of congruences: Again, to begin, the product

N

n

1

n

2

…

n

k

{\displaystyle N=n_{1}n_{2}\ldots n_{k}}

is defined. Then a solution

x

{\displaystyle x}

can be found as follows: For each

i

{\displaystyle i}

,   the integers

n

i

{\displaystyle n_{i}}

and

N

/

n

i

{\displaystyle N/n_{i}}

are co-prime. Using the   Extended Euclidean algorithm,   we can find integers

r

i

{\displaystyle r_{i}}

and

s

i

{\displaystyle s_{i}}

such that

r

i

n

i

s

i

N

/

n

i

= 1

{\displaystyle r_{i}n_{i}+s_{i}N/n_{i}=1}

. Then, one solution to the system of simultaneous congruences is: and the minimal solution,

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Chinese remainder theorem step by step in the Prolog programming language

Source code in the prolog programming language

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

pair(X, Y, X-Y).

egcd(_, 0, 1, 0) :- !.
egcd(A, B, X, Y) :-
    divmod(A, B, Q, R),
    egcd(B, R, S, X),
    Y is S - Q*X.

modinv(A, B, X) :-
    egcd(A, B, X, Y),
    A*X + B*Y =:= 1.

crt_fold(A, M, P, R0, R1) :- % system of equations of (x = a) (mod m); p = M/m
    modinv(P, M, Inv),
    R1 is R0 + A*Inv*P.

crt(Pairs, N) :-
    maplist(pair, As, Ms, Pairs),
    foldl(product, Ms, 1, M),
    maplist(divmod(M), Ms, Ps, _), % p(n) <- M/m(n)
    foldl(crt_fold, As, Ms, Ps, 0, N0),
    N is N0 mod M.


/* Chinese remainder Theorem: Input chinrest([2,3,2], [3,5,7], R).  -----> R == 23
                                 or chinrest([2,3], [5,13], R). ---------> R == 42
    Written along the lines of "Introduction to Algorithms" by 
    Thomas Cormen
    Charles Leiserson
    Ronald Rivest
compiled with gprolog 1.4.5 (64 Bits)
*/

chinrest(A, N, X) :- 
    sort(N),                
    prime(N,Nn), !, lenok(A, Nn),                         /* test as to whether the ni are primes */
    product(Nn,P), !,                                     /* P is the product of the ni */
    milist(P, Nn, Mi),                                    /* The Mi List: mi = n/ni */
    cilist(Mi, Nn, Ci),                                   /* The first Ci List: mi-1 mod ni */
    mult_lists(Mi, Ci, Ac),                               /* The ci List :mi*(mi-1 mod ni) */
    mult_lists(Ac, A, Ad),                                /* The ai*ci List */
    sum_list(Ad, S),                                      /* Sum of the ai*cis */
    X is S mod P, ! .                                     /* a is (a1c1 + ... +akck) mod n */

prime([X|Ys], Zs) :- fd_not_prime(X), !, prime(Ys,Zs).    /* sift the primes of [list] */
prime([Y|Ys], [Y|Zs]) :- fd_prime(Y), !, prime(Ys,Zs).
prime([],[]).

product([], 0).                                           /* n1.n2.n3. ... .ni. ... .nk */
product([H|T], P) :- product_1(T, H, P).

product_1([], P, P).
product_1([H|T], H0, P) :- product_1(T, H, P0), P is P0 * H0.
    
lenok(A, N) :- length(A, X), length(N, Y), X=:=Y.
lenok(_, _) :- write('Please enter equal length prime numbers only'), fail.

cilist(Mi, Ni, Ci) :- maplist( (modinv), Mi, Ni, Ci).       /* generate the Cis */

mult_lists(Ai, Ci, Ac) :- maplist( (pro), Ai, Ci, Ac).      /* The mi*ci */
pro(X, Y, Z) :- Z is X * Y.

milist(_, [],[]).
milist(P, [H|T],[X|Y]) :- X is truncate(P/H), milist(P, T, Y).

modinv(A, B, N) :- eeuclid(A, B, P, _, GCD), 
        GCD =:= 1,
        N is P mod B.
        
eeuclid(A,B,P,S,GCD) :-
   A >= B,
   a_b_p_s_(A,B,P,S,1-0,0-1,GCD),
   GCD is A*P + B*S.

eeuclid(A,B,P,S,GCD) :-
   A < B,
   a_b_p_s_(B,A,S,P,1-0,0-1,GCD);
   GCD is A*P + B*S.

a_b_p_s_(A,0,P1,S1,P1-_P2,S1-_S2,A).
a_b_p_s_(A,B,P,S,P1-P2,S1-S2,GCD) :-
   B > 0,
   A > B,
   Q is truncate(A/B),
   B1 is A mod B,
   P3 is P1-(Q*P2),
   S3 is S1-(Q*S2),
   a_b_p_s_(B,B1,P,S,P2-P3,S2-S3,GCD).

You may also check:How to resolve the algorithm Calendar - for REAL programmers step by step in the J programming language
You may also check:How to resolve the algorithm Add a variable to a class instance at runtime step by step in the Python programming language
You may also check:How to resolve the algorithm Hash join step by step in the Julia programming language
You may also check:How to resolve the algorithm Array length step by step in the Lambdatalk programming language
You may also check:How to resolve the algorithm Superellipse step by step in the Delphi programming language