(48G) GCD: Greatest Common Divisor
08-30-2018, 03:21 PM
Post: #1
 Thomas Klemm Senior Member Posts: 2,082 Joined: Dec 2013
(48G) GCD: Greatest Common Divisor
This solution is from: HP 48 Insights Programs
Contains all the example programs from the book HP 48 Insights Part 1, by Bill Wickes.

INSIGHTS/PROGRAMS/GCD:
Code:
%%HP: T(3)A(D)F(.); \<<   WHILE DUP2 MOD DUP 0 \=/   REPEAT ROT DROP   END ROT DROP2 \>>

However we can make it a bit shorter:
Code:
«   WHILE DUP   REPEAT SWAP OVER MOD   END DROP »

Example:

54 24
GCD

6
08-31-2018, 08:34 AM
Post: #2
 Werner Senior Member Posts: 887 Joined: Dec 2013
RE: (48G) GCD: Greatest Common Divisor
Ow that's an old one. This is still quite a bit shorter:
Code:
\<<   WHILE     SWAP DUP2   REPEAT     MOD   END   DROP2 \>>

Cheers, Werner

41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE
08-31-2018, 12:12 PM (This post was last modified: 08-31-2018 11:45 PM by Albert Chan.)
Post: #3
 Albert Chan Senior Member Posts: 2,647 Joined: Jul 2018
RE: (48G) GCD: Greatest Common Divisor
Hi, Werner:

I like your shorter version !
But, it is slightly different than Thomas Klemm code.

Instead of confirming nonzero x before y % x, it test for y instead.
(Bill Wickes version also assumed start with nonzero x)
08-31-2018, 01:18 PM
Post: #4
 Werner Senior Member Posts: 887 Joined: Dec 2013
RE: (48G) GCD: Greatest Common Divisor
Since GCD(x,y) = GCD(y,x) that makes no difference.
And when does it throw an error?
GCD(x,0) = GCD(0,x) = x, even for x=0

Cheers, Werner

41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE
08-31-2018, 02:06 PM
Post: #5
 Albert Chan Senior Member Posts: 2,647 Joined: Jul 2018
RE: (48G) GCD: Greatest Common Divisor
(08-31-2018 01:18 PM)Werner Wrote:  Since GCD(x,y) = GCD(y,x) that makes no difference.
And when does it throw an error?

If entered: 0 54 GCD, the code returned gcd of 54, as expected.

If entered: 54 0 GCD, stack = {0 54}

SWAP DUP2, stack = {54 0 54 0}

Inside REPEAT, stack = {0 54 0}

MOD, will do an illegal operation 54 % 0, thus ERROR

BTW, I don't know what MOD will do for 54 % 0, ERROR was my guess.
If the calculator returned x % 0 as x, then ignore my post. All is well ...
08-31-2018, 02:29 PM
Post: #6
 rprosperi Super Moderator Posts: 6,319 Joined: Dec 2013
RE: (48G) GCD: Greatest Common Divisor
(08-31-2018 02:06 PM)Albert Chan Wrote:  BTW, I don't know what MOD will do for 54 % 0, ERROR was my guess.
If the calculator returned x % 0 as x, then ignore my post. All is well ...

The program works fine for both 0 54 GCD or 54 0 GCD, returning 54 in both cases.

Friendly suggestion: Get an actual calculator (or install an emulator) and play along with the rest of us. It's the best way to learn RPL (or RPN, etc.)

--Bob Prosperi
08-31-2018, 03:46 PM
Post: #7
 Albert Chan Senior Member Posts: 2,647 Joined: Jul 2018
RE: (48G) GCD: Greatest Common Divisor
(08-31-2018 02:29 PM)rprosperi Wrote:
(08-31-2018 02:06 PM)Albert Chan Wrote:  BTW, I don't know what MOD will do for 54 % 0, ERROR was my guess.
If the calculator returned x % 0 as x, then ignore my post. All is well ...

The program works fine for both 0 54 GCD or 54 0 GCD, returning 54 in both cases.

You mean it work for *all* 3 programs ?
Klemm version work. I was referring to the other two ...

I just downloaded Hp50g emulator: 54 0 MOD return ?, not 54
08-31-2018, 10:08 PM
Post: #8
 rprosperi Super Moderator Posts: 6,319 Joined: Dec 2013
RE: (48G) GCD: Greatest Common Divisor
(08-31-2018 03:46 PM)Albert Chan Wrote:  You mean it work for *all* 3 programs ?
Klemm version work. I was referring to the other two ...

I just downloaded Hp50g emulator: 54 0 MOD return ?, not 54

No, sorry I was not clear, I was referring to Werner's program; I thought that was the one you were referencing.

Great, glad you're jumping-in with 50g Emulator! Soon you'll want a real 50g, then maybe a 48GX, etc. Careful, it can be addictive...

--Bob Prosperi
08-31-2018, 11:40 PM
Post: #9
 Albert Chan Senior Member Posts: 2,647 Joined: Jul 2018
RE: (48G) GCD: Greatest Common Divisor
(08-31-2018 10:08 PM)rprosperi Wrote:
(08-31-2018 03:46 PM)Albert Chan Wrote:  You mean it work for *all* 3 programs ?
Klemm version work. I was referring to the other two ...

I just downloaded Hp50g emulator: 54 0 MOD return ?, not 54

No, sorry I was not clear, I was referring to Werner's program; I thought that was the one you were referencing.

Turns out, we are both right (with Werner's program):

With approx mode: 54 0 GCD returns 54 (calculator assumed 54 % 0 = 54)
Under exact mode: 54 0 GCD returns '?' (technically, 54 % 0 is undefined)

In fact, Werner's code will not work in exact mode at all, except for initial Y = 0.
It always return '?', because X always reduced to zero, causing undefined Y % X.

Hp50g emulator is fun
09-01-2018, 02:52 AM
Post: #10
 rprosperi Super Moderator Posts: 6,319 Joined: Dec 2013
RE: (48G) GCD: Greatest Common Divisor
(08-31-2018 11:40 PM)Albert Chan Wrote:  Turns out, we are both right (with Werner's program):

With approx mode: 54 0 GCD returns 54 (calculator assumed 54 % 0 = 54)
Under exact mode: 54 0 GCD returns '?' (technically, 54 % 0 is undefined)

In fact, Werner's code will not work in exact mode at all, except for initial Y = 0.
It always return '?', because X always reduced to zero, causing undefined Y % X.

Hp50g emulator is fun

Regardless of the mode the 50g is set to (Exact or Approximate), it interprets numbers as approximate or exact based on the format of the number provided. Approximate numbers always must include a decimal point, and Exact numbers never include a decimal point.

So even in Exact Mode, entering 54. 0. GCD will treat the parameters as approximate.

In my case I was actually testing with a 48GX; there is no distinction of type here, all numbers are approximate, even if entered as "54 0 GCD".

I agree the 50g emulator is great, but an actual device is even more satisfying (although not as fast for extended computations).

--Bob Prosperi
09-01-2018, 04:14 PM
Post: #11
 Werner Senior Member Posts: 887 Joined: Dec 2013
RE: (48G) GCD: Greatest Common Divisor
Hello Albert,
you're absolutely right.
I wrote this when the most advanced HP was the 48GX, and so I never realized it didn't work for decimal integers.

Still, I can get it shorter:

Code:
\<<   WHILE SWAP OVER DUP   REPEAT MOD   END    ROT DROP2 \>>

CHeers, Werner

41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE
09-01-2018, 05:05 PM
Post: #12
 Thomas Klemm Senior Member Posts: 2,082 Joined: Dec 2013
RE: (48G) GCD: Greatest Common Divisor
(09-01-2018 04:14 PM)Werner Wrote:  Still, I can get it shorter:

Can somebody explain how the size of these programs are determined?

It puzzles me a bit that this program uses 22.5 bytes:
Code:
« WHILE REPEAT END »

Whereas this longer program uses only 20 bytes:
Code:
« WHILE REPEAT SWAP END »

Thomas
09-01-2018, 05:57 PM
Post: #13
 Albert Chan Senior Member Posts: 2,647 Joined: Jul 2018
RE: (48G) GCD: Greatest Common Divisor
Hi, Thomas Klemm

My guess is « WHILE REPEAT END » cannot compile, and had to store internally as « WHILE REPEAT *PASS* END ».
*PASS* is just a placeholder. Above thus similar to Python code, while 1: pass

To minimize program byte count, common keywords use less storage.
*PASS* probably is pretty rare for a (internal) keyword, which does nothing ...
09-01-2018, 06:22 PM
Post: #14
 Thomas Klemm Senior Member Posts: 2,082 Joined: Dec 2013
RE: (48G) GCD: Greatest Common Divisor
(09-01-2018 05:57 PM)Albert Chan Wrote:  My guess is « WHILE REPEAT END » cannot compile

Nah, that's a valid program. You can even run it. It just pops the elements of the stack until it reaches 0.
09-01-2018, 06:46 PM (This post was last modified: 09-01-2018 06:51 PM by DavidM.)
Post: #15
 DavidM Senior Member Posts: 986 Joined: Dec 2013
RE: (48G) GCD: Greatest Common Divisor
(09-01-2018 05:05 PM)Thomas Klemm Wrote:  Can somebody explain how the size of these programs are determined?

It puzzles me a bit that this program uses 22.5 bytes:
Code:
« WHILE REPEAT END »

The reason this is larger is due to the way that the internal UserRPL compiler adds an empty "secondary" in between the REPEAT and the END. The empty secondary is comprised of the two SysRPL primitives :: and ;. Each one uses 2.5 bytes, for a total of 5 bytes which are "invisible" in the text form of the source code.

Something has to exist after the REPEAT and before the END for the RPL stream to be processed correctly.

(09-01-2018 05:05 PM)Thomas Klemm Wrote:  Whereas this longer program uses only 20 bytes:
Code:
« WHILE REPEAT SWAP END »

This one is compiled as you would probably expect, with the SWAP command between the REPEAT and END. SWAP only takes 2.5 bytes (compared to the 5 above), hence the smaller size of the total program.

For completeness, here's the SysRPL representations of both programs after the RPL compiler is done with them:
Code:
 « WHILE REPEAT END » ::   x<<   xWHILE   xREPEAT   ::   ;   xWHILEEND   x>> ; « WHILE REPEAT SWAP END » ::   x<<   xWHILE   xREPEAT   xSWAP   xWHILEEND   x>> ;
09-01-2018, 07:12 PM
Post: #16
 Thomas Klemm Senior Member Posts: 2,082 Joined: Dec 2013
RE: (48G) GCD: Greatest Common Divisor
Interesting. But still I don't understand why my program in post #1 uses 35 bytes while Werner's program in post #11 uses only uses 32.5 bytes.
My program is shorter if we count the commands. Is there another :: ; included somewhere?

Cheers
Thomas
09-01-2018, 07:31 PM
Post: #17
 DavidM Senior Member Posts: 986 Joined: Dec 2013
RE: (48G) GCD: Greatest Common Divisor
(09-01-2018 07:12 PM)Thomas Klemm Wrote:  Is there another :: ; included somewhere?

Yes.

The savings in Werner's version comes because, in this case, there's only one command in between the REPEAT and END steps. In the RPL stream, the next item after the REPEAT has to be skippable, so if there's more than one command they all have to be encapsulated in a secondary so as to be a single entity. Here's the compiled versions of both programs:
Code:
::   x<<   xWHILE   xDUP   xREPEAT   ::     xSWAP     xOVER     xMOD   ;   xWHILEEND   xDROP   x>> ; ::   x<<   xWHILE   xSWAP   xOVER   xDUP   xREPEAT   xMOD   xWHILEEND   xROT   xDROP2   x>> ;
09-01-2018, 07:40 PM
Post: #18
 Thomas Klemm Senior Member Posts: 2,082 Joined: Dec 2013
RE: (48G) GCD: Greatest Common Divisor
Thanks again for taking the time for this analysis!
Just out of curiosity: what would be the shortest SysRPL program to calculate the GCD of two numbers?

Cheers
Thomas
09-01-2018, 08:41 PM
Post: #19
 DavidM Senior Member Posts: 986 Joined: Dec 2013
RE: (48G) GCD: Greatest Common Divisor
(09-01-2018 07:40 PM)Thomas Klemm Wrote:  Thanks again for taking the time for this analysis!
Just out of curiosity: what would be the shortest SysRPL program to calculate the GCD of two numbers?

Everyone's least favorite answer:

"It depends..."

If the program is intended to behave in a "normal" fashion (accepting varying argument types, preserving stack for UNDO/LAST, etc.), I'm not sure you could save any space at all by going the SysRPL route.

If you don't care about error trapping or argument type checking (which leaves you exposed for a nasty crash if you forget which types of arguments to use), you could go with a "throw caution to the wind" approach and do something like this:
Code:
::    BEGIN       SWAPOVER       DUP %0<>    WHILE       %MOD    REPEAT    ROT2DROP ;

This only works with approximate numbers, and weighs in at 25 bytes. Not much savings for the risk and hassle, IMHO. Then of course you'd need something else entirely if exact integers were involved, which makes going the SysRPL route even less attractive. I'd stick with a UserRPL version for something like this.
09-01-2018, 09:57 PM (This post was last modified: 09-01-2018 09:58 PM by rprosperi.)
Post: #20
 rprosperi Super Moderator Posts: 6,319 Joined: Dec 2013
RE: (48G) GCD: Greatest Common Divisor
(09-01-2018 07:40 PM)Thomas Klemm Wrote:  Just out of curiosity: what would be the shortest SysRPL program to calculate the GCD of two numbers?

Isn't this shorter?
Code:
::   xGCD ;

SCNR

--Bob Prosperi
 « Next Oldest | Next Newest »

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