(48G) GCD: Greatest Common Divisor

(48G) GCD: Greatest Common Divisor - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (48G) GCD: Greatest Common Divisor (/thread-11296.html)

Pages: 1 2

(48G) GCD: Greatest Common Divisor - Thomas Klemm - 08-30-2018 03:21 PM

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

RE: (48G) GCD: Greatest Common Divisor - Werner - 08-31-2018 08:34 AM

Ow that's an old one. This is still quite a bit shorter:

Code:

\<<

  WHILE

    SWAP DUP2

  REPEAT

    MOD

  END

  DROP2

\>>

Cheers, Werner

RE: (48G) GCD: Greatest Common Divisor - Albert Chan - 08-31-2018 12:12 PM

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)

RE: (48G) GCD: Greatest Common Divisor - Werner - 08-31-2018 01:18 PM

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

RE: (48G) GCD: Greatest Common Divisor - Albert Chan - 08-31-2018 02:06 PM

(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 ...

RE: (48G) GCD: Greatest Common Divisor - rprosperi - 08-31-2018 02:29 PM

(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.)

RE: (48G) GCD: Greatest Common Divisor - Albert Chan - 08-31-2018 03:46 PM

(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

RE: (48G) GCD: Greatest Common Divisor - rprosperi - 08-31-2018 10:08 PM

(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...

RE: (48G) GCD: Greatest Common Divisor - Albert Chan - 08-31-2018 11:40 PM

(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

RE: (48G) GCD: Greatest Common Divisor - rprosperi - 09-01-2018 02:52 AM

(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).

RE: (48G) GCD: Greatest Common Divisor - Werner - 09-01-2018 04:14 PM

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

RE: (48G) GCD: Greatest Common Divisor - Thomas Klemm - 09-01-2018 05:05 PM

(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

RE: (48G) GCD: Greatest Common Divisor - Albert Chan - 09-01-2018 05:57 PM

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 ...

RE: (48G) GCD: Greatest Common Divisor - Thomas Klemm - 09-01-2018 06:22 PM

(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.

RE: (48G) GCD: Greatest Common Divisor - DavidM - 09-01-2018 06:46 PM

(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>>

;

RE: (48G) GCD: Greatest Common Divisor - Thomas Klemm - 09-01-2018 07:12 PM

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

RE: (48G) GCD: Greatest Common Divisor - DavidM - 09-01-2018 07:31 PM

(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>>

;

RE: (48G) GCD: Greatest Common Divisor - Thomas Klemm - 09-01-2018 07:40 PM

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

RE: (48G) GCD: Greatest Common Divisor - DavidM - 09-01-2018 08:41 PM

(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.

RE: (48G) GCD: Greatest Common Divisor - rprosperi - 09-01-2018 09:57 PM

(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