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)
Fun with the Radio Shack EC4026
Fun with the Radio Shack EC4026 (Equivalent of the Casio fx4500P) Programming Notes The syntax for prompting ...

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