Post Reply 
(48G) GCD: Greatest Common Divisor
08-30-2018, 03:21 PM
Post: #1
(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
Find all posts by this user
Quote this message in a reply
08-31-2018, 08:34 AM
Post: #2
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
Find all posts by this user
Quote this message in a reply
08-31-2018, 12:12 PM (This post was last modified: 08-31-2018 11:45 PM by Albert Chan.)
Post: #3
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)
Find all posts by this user
Quote this message in a reply
08-31-2018, 01:18 PM
Post: #4
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
Find all posts by this user
Quote this message in a reply
08-31-2018, 02:06 PM
Post: #5
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 ...
Find all posts by this user
Quote this message in a reply
08-31-2018, 02:29 PM
Post: #6
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
Find all posts by this user
Quote this message in a reply
08-31-2018, 03:46 PM
Post: #7
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
Find all posts by this user
Quote this message in a reply
08-31-2018, 10:08 PM
Post: #8
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
Find all posts by this user
Quote this message in a reply
08-31-2018, 11:40 PM
Post: #9
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 Smile
Find all posts by this user
Quote this message in a reply
09-01-2018, 02:52 AM
Post: #10
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 Smile

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
Find all posts by this user
Quote this message in a reply
09-01-2018, 04:14 PM
Post: #11
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
Find all posts by this user
Quote this message in a reply
09-01-2018, 05:05 PM
Post: #12
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 »

Thanks in advance
Thomas
Find all posts by this user
Quote this message in a reply
09-01-2018, 05:57 PM
Post: #13
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 ...
Find all posts by this user
Quote this message in a reply
09-01-2018, 06:22 PM
Post: #14
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.
Find all posts by this user
Quote this message in a reply
09-01-2018, 06:46 PM (This post was last modified: 09-01-2018 06:51 PM by DavidM.)
Post: #15
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>>
;
Find all posts by this user
Quote this message in a reply
09-01-2018, 07:12 PM
Post: #16
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
Find all posts by this user
Quote this message in a reply
09-01-2018, 07:31 PM
Post: #17
RE: (48G) GCD: Greatest Common Divisor
(09-01-2018 07:12 PM)Thomas Klemm Wrote:  Is there another :: ; included somewhere?

Short answer:
Yes. Smile

Longer answer:
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>>
;
Find all posts by this user
Quote this message in a reply
09-01-2018, 07:40 PM
Post: #18
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
Find all posts by this user
Quote this message in a reply
09-01-2018, 08:41 PM
Post: #19
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.
Find all posts by this user
Quote this message in a reply
09-01-2018, 09:57 PM (This post was last modified: 09-01-2018 09:58 PM by rprosperi.)
Post: #20
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
Find all posts by this user
Quote this message in a reply
Post Reply 




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