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)
Retro Review: Radio Shack EC2024
Retro Review: Radio Shack EC2024 Quick Facts Company: Radio Shack Years in Production: Around 1994 Original Price: $24.99 Bat...

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

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

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