(42S) GCF

[Gerald H]

Prompted by Eddie W Shore's

http://www.hpmuseum.org/forum/thread-6528.html

here's my short GCD programme.

The prog takes X & Y values from stack & returns GCD , or GCF if you wish, to stack level X.

Code:


0.    { 16-Byte Prgm }
1.    LBL “GCF”
2.    LBL 00
3.    MOD
4.    LASTX
5.    X<>Y
6.    X≠0?
7.    GTO 00
8.    R↓
9.    ABS
10.    END

[Werner]

Same as mine, except I have a "+" in step 8 (since you know X contains zero).
I also add Smallest Common Multiple:

*LBL "SCM"
RCL ST Y
RCL ST Y
XEQ 00
/
x
RTN

Cheers, Werner

[Guenter Schink]

Is this ABS necessary?

Günter

[Gerald H]

Yes, ABS is needed for some negative inputs, otherwise the GCD is returned as a negative which is surely not the GREATEST common factor.

[Gerald H]

(07-10-2016 07:21 AM)Werner Wrote:  Same as mine, except I have a "+" in step 8 (since you know X contains zero).
I also add Smallest Common Multiple:

*LBL "SCM"
RCL ST Y
RCL ST Y
XEQ 00
/
x
RTN

Cheers, Werner

What does XEQ 00 do?

[Werner]

Look at your own code ;-)
it does GCF, I keep them both in 1 program.

Werner

[Dieter]

(07-10-2016 04:41 AM)Gerald H Wrote:  here's my short GCD programme.

Fine – my fractions programs used virtually the same code, but with a final + instead of R↓ which works as a DROP here. ;-)

FTR, here is an alternate GCD routine with a slightly shorter and thus faster loop. It can be used if Z does not have to be preserved:

Code:

01 LBL 00
02 STO Z
03 MOD
04 X≠0?
05 GTO 00
06 +
07 END

And finally a solution that returns both LCM and GCD (in Y resp. X):

Code:

01 LBL"LCMGCD"
02 STO T
03 X<>Y
04 ST* T
05 LBL 00
06 STO Z
07 MOD
08 X≠0?
09 GTO 00
10 +
11 ST/ Y
12 END

This is HP41 code. HP42s users may imagine an additional "ST" in the stack related commands. ;-)

Dieter

[Gerald H]

(07-11-2016 06:58 PM)Dieter Wrote:  

(07-10-2016 04:41 AM)Gerald H Wrote:  here's my short GCD programme.

Fine – my fractions programs used virtually the same code, but with a final + instead of R↓ which works as a DROP here. ;-)

FTR, here is an alternate GCD routine with a slightly shorter and thus faster loop. It can be used if Z does not have to be preserved:

Code:

01 LBL 00
02 STO Z
03 MOD
04 X≠0?
05 GTO 00
06 +
07 END

And finally a solution that returns both LCM and GCD (in Y resp. X):

Code:

01 LBL"LCMGCD"
02 STO T
03 X<>Y
04 ST* T
05 LBL 00
06 STO Z
07 MOD
08 X≠0?
09 GTO 00
10 +
11 ST/ Y
12 END

This is HP41 code. HP42s users may imagine an additional "ST" in the stack related commands. ;-)

Dieter

I tried the first programme but for various inputs it returned 1.

[Gerald H]

Sorry, my error, I entered STO "Z" for STO ST Z.

Now functions correctly.