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: HP 95LX
Retro Review: HP 95LX Essentials Company: Hewlett Packard Years: 1991  2003 Type: Palmtop PC (a very early versi...

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

TI36X Pro Review This is a review of the TI36X Pro Calculator by Texas Instruments. History Originally, this was the TI30X Pro that w...

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...
No comments:
Post a Comment