(35S) Bézout or EGCD
|
12-20-2014, 05:05 PM
(This post was last modified: 06-15-2017 01:26 PM by Gene.)
Post: #1
|
|||
|
|||
(35S) Bézout or EGCD
Bézout (or extended Euclidean algorithm) finds integer solutions for C, E & GCD( X , Y ) in the equation
C * X + E * Y = GCD( X , Y ). For example, for stack Y: 666,777 X: 777,666 The programme returns Z: 111 (our GCD) Y: -3,233 (E) X: 2,772 (C) & indeed 2,772 * 777,666 + -3,233 * 666,777 = 111 1 LBL B 2 1►E►F-1►C►D 3 R↓ 4 REGY 5 REGY 6 INT/ 7 +/- 8 ENTER 9 RCL* D 10 RCL+ E 11 x<> D 12 STO E 13 R↓ 14 ENTER 15 RCL* F 16 RCL+ C 17 x<> F 18 STO C 19 R↓ 20 REGY 21 * 22 REGZ 23 + 24 x≠0? 25 GTO B004 26 R↓ 27 RCL E 28 RCL C 29 RTN Should the GCD be 1, then E is the multiplicative inverse of Y modulo X & C the multiplicative inverse of X modulo Y. |
|||
12-21-2014, 02:37 AM
(This post was last modified: 02-17-2015 10:07 AM by Thomas Klemm.)
Post: #2
|
|||
|
|||
RE: HP 35S: Bézout or EGCD
(12-20-2014 05:05 PM)Gerald H Wrote: Should the GCD be 1, then E is the multiplicative inverse of Y modulo X & C the multiplicative inverse of X modulo Y. You might be interested in: Solving a Single Congruence Equation (04-18-2014 05:24 PM)Thomas Klemm Wrote: Remark: Kind regards Thomas |
|||
12-22-2014, 04:32 PM
Post: #3
|
|||
|
|||
RE: HP 35S: Bézout or EGCD
Here an alternative programme to the above, same input & output. I expected the time taken for calculations to be less than with the first progamme & don't really understand why that's not the case.
1 LBL E 2 STO H 3 x<>y 4 STO G 5 [H,1] 6 [G,0] 7 REGX*[1,0] 8 x=0? 9 GTO E022 10 REGZ 11 x<>y 12 / 13 [1,0] 14 * 15 IP 16 REGY 17 * 18 REGZ 19 - 20 +/- 21 GTO E007 22 REGZ*[1,0] 23 REGT*[0,1] 24 (REGY-REGX*H)/G 25 x<>y 26 RTN |
|||
02-17-2015, 08:49 AM
Post: #4
|
|||
|
|||
RE: HP 35S: Bézout or EGCD
(12-22-2014 04:32 PM)Gerald H Wrote: Here an alternative programme to the above, same input & output. I expected the time taken for calculations to be less than with the first progamme & don't really understand why that's not the case. Q: How do you evaluate the speed of the execution? My 2 cents GCD program, nothing special here, I just like the simplicity Code: A001 LBLA |
|||
02-17-2015, 09:42 AM
Post: #5
|
|||
|
|||
RE: HP 35S: Bézout or EGCD
(02-17-2015 08:49 AM)Tugdual Wrote:(12-22-2014 04:32 PM)Gerald H Wrote: Here an alternative programme to the above, same input & output. I expected the time taken for calculations to be less than with the first progamme & don't really understand why that's not the case. I store the begin time, run the programme, & subtract present time from the stored value. |
|||
02-17-2015, 10:04 AM
Post: #6
|
|||
|
|||
RE: HP 35S: Bézout or EGCD | |||
02-17-2015, 07:29 PM
Post: #7
|
|||
|
|||
RE: HP 35S: Bézout or EGCD
(02-17-2015 08:49 AM)Tugdual Wrote: My 2 cents GCD program, nothing special here, I just like the simplicity Whoa... 10 (ten!) steps. Obviously you never used a calculator with limited memory. ;-) Code: A001 LBLA Yes, it's the same method. Dieter |
|||
02-17-2015, 07:57 PM
Post: #8
|
|||
|
|||
RE: HP 35S: Bézout or EGCD
(02-17-2015 07:29 PM)Dieter Wrote:Oh wow I would have sworn RMDR was requiring a specific sort order...(02-17-2015 08:49 AM)Tugdual Wrote: My 2 cents GCD program, nothing special here, I just like the simplicity I like the final "A007 +" |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 3 Guest(s)