Chinese Remainder Theorem  Sun Tzu (3rd to 5th century AD, China)
This program solves for X for the set of three linear congruence equations:
X = A mod B
X = C mod D
X = E mod F
B, D, and F are pairwise coprime. B and D have a GCD of 1, B and F have a GCD of 1, and D and F have a GCD of 1.
A general solution takes the form
X = x1 * D * F * A + x2 * B * F * C + x3 * B * D * E
where (one method of solution)
D * F * x1 = 1 mod B
B * F * x2 = 1 mod D
B * D * x3 = 1 mod F
The program returns the solution X ± n*(B*D*F), X is the smallest positive integer and n is an integer.
Sources:
Chinese Remainder Theorem  General Information:
http://en.wikipedia.org/wiki/Chinese_remainder_theorem
Chinese Remainder Theorem  One method of solution:
http://youtu.be/3PkxN_r9up8
Solving a Linear Congruence Equation:
http://youtu.be/U9Eo6Bsvm4M
Examples:
X = 3 mod 8
X = 1 mod 9
X = 4 mod 11
X = 235 ± 792*n
{...557, 235, 1027, 1819...}
X = 4 mod 5
X = 1 mod 7
X = 11 mod 16
X = 379 ± 560*n
{... 181, 379, 939, 1499...}
HP Prime Program CHINESE3
Output: [ X, B*D*F ]
// Declare subroutine
SUB1( );
// Main routine
EXPORT CHINESE3( )
BEGIN
LOCAL A,B,C,D,E,F,I,T:=0;
INPUT({A,B,C,D,E,F}, "X=A mod B=C mod D
=E mod F");
T := SUB1(D*F, B) * D * F * A + SUB1(B*F, D) * B * F * C
+ SUB1(B*D, F) * B * D * E;
T := T MOD (B*D*F);
RETURN [T, B*D*F];
END;
SUB1(X,Y)
BEGIN
FOR I FROM 1 TO X1 DO
IF FP((X1)/Y)==0 THEN
RETURN I;
END;
END;
RETURN "NO SOLUTION";
END;
TI84+:
Main Routine: CHINESE3
Subroutine: CHIN3SUB
Output:
X
+/ N*
B*D*F
PROGRAM:CHINESE3
: ClrHome
: Disp "X=A MOD B"
: Disp "X=C MOD D"
: Disp "X=E MOD F"
: Prompt A,B,C,D,E,F
: 0 → T
: D * F → X : B → Y :prgmCHIN3SUB
: I * D * F * A → T
: B * F → X : D → Y : prgmCHIN3SUB
: T + I * B * F * C → T
: B * D → X : F → Y : prgmCHIN3SUB
: T +I * B * D * E → T
: remainder(T, B * D * F) → T
: Disp T
: Disp "+/ N*"
: Disp B * D * F
PROGRAM:CHIN3SUB (Subroutine)
: For(I, 1, X1)
: fPart((X*I1)/Y) → Z
: If Z=0
: Then
: Return
: End
: End
: Disp "NO SOLUTION"
: Stop
A blog is that is all about mathematics and calculators, two of my passions in life.
Friday, January 17, 2014
HP Prime and TI84+: Chinese Remainder Theorem  Solving Three Congruence Equations
Subscribe to:
Post Comments (Atom)
Review: Canon F605 Scientific Calculator
Review: Canon F605 Scientific Calculator Company: Canon Type: Scientific Memory: 7 registers Battery: LR54 x 1 Yea...

Casio fx991EX Classwiz Review Casio FX991EX The next incarnation of the fx991 line of Casio calculators is the fx991 EX. ...

One of the missing features of the TI82/83/84 family is the ability to convert between bases. Here are two programs in TIBasic to help...

HP Prime: Basic CAS Commands for Polynomials and Rational Expressions Define the following variables: poly: a polynomial o...
No comments:
Post a Comment