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)
TI84 Plus CE and HP 17BII+: Euclidian Divison
TI84 Plus CE and HP 17BII+: Euclidian Division What is the ├ symbol on the calculator? (├ the symbol is a vertical line with a horizontal ...

The Odds of Hitting it Big The number of possible combinations is fairly easy to calculate. You multiply the number symbols each slot has ...

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

Over the next month, maybe month and a half, I plan to post programming tutorials for the HP (Hewlett Packard) Prime. If you have program...
No comments:
Post a Comment