(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
 Gerald H Senior Member Posts: 1,417 Joined: May 2014
(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
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
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:
Since overflow is avoided it's possible to solve:
999,999,999,989 * x = 1 mod 999,999,999,999

Solution:
899,999,999,999

Kind regards
Thomas
12-22-2014, 04:32 PM
Post: #3
 Gerald H Senior Member Posts: 1,417 Joined: May 2014
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
 Tugdual Senior Member Posts: 745 Joined: Dec 2013
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 A002 x>y? A003 x<>y A004 RMDR A005 x=0? A006 GTO A009 A007 LASTx A008 GTO A003 A009 LASTX A010 RTN
02-17-2015, 09:42 AM
Post: #5
 Gerald H Senior Member Posts: 1,417 Joined: May 2014
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.

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 A002 x>y? A003 x<>y A004 RMDR A005 x=0? A006 GTO A009 A007 LASTx A008 GTO A003 A009 LASTX A010 RTN

I store the begin time, run the programme, & subtract present time from the stored value.
02-17-2015, 10:04 AM
Post: #6
 Tugdual Senior Member Posts: 745 Joined: Dec 2013
RE: HP 35S: Bézout or EGCD
(02-17-2015 09:42 AM)Gerald H Wrote:  I store the begin time, run the programme, & subtract present time from the stored value.
You have a time function on the 35s?
02-17-2015, 07:29 PM
Post: #7
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
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 A002 RMDR A003 LASTx A004 x<>y A005 x≠0? A006 GTO A002 A007 + A008 RTN

Yes, it's the same method.

Dieter
02-17-2015, 07:57 PM
Post: #8
 Tugdual Senior Member Posts: 745 Joined: Dec 2013
RE: HP 35S: Bézout or EGCD
(02-17-2015 07:29 PM)Dieter Wrote:
(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 A002 RMDR A003 LASTx A004 x<>y A005 x≠0? A006 GTO A002 A007 + A008 RTN

Yes, it's the same method.

Dieter
Oh wow I would have sworn RMDR was requiring a specific sort order...
I like the final "A007 +"
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)