(12C) LCM <> GCD - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Software Libraries (/forum-10.html) +--- Forum: General Software Library (/forum-13.html) +--- Thread: (12C) LCM <> GCD (/thread-9865.html) |
(12C) LCM <> GCD - Gamo - 01-06-2018 10:14 AM Program to find LCM and GCD with two integers. Code:
Example: LCM(256, 562) is 71936 --> 256 ENTER 562 R/S GCD(256, 562) is 2 -------> X<>Y LCM(12345, 67890) is 55873470 ---> 12345 ENTER 67890 R/S GCD(12345, 67890) is 15 -----------> X<>Y Gamo RE: (12C) Least Common Multiple <> GCD - Dieter - 01-06-2018 12:27 PM (01-06-2018 10:14 AM)Gamo Wrote: Program to find LCM and GCD with two integers. You chose the algorithm with successive subtraction. I don't know how fast this runs on a real original 12C. But anyway, you can improve your code: First you should never ever use "2 y^x" for squaring. "ENTER x" is much faster and also more precise. It even sets LastX correctly. Your program uses a square and squareroot sequence to emulate an ABS command. There are other ways to do so, but the ABS is not required if you make sure that y is greater than x: x<=y? x<>y x<>y At the end you should also first divide R0 by the GCD and then multiply with R1. This avoid inaccuracies for large arguments. These suggestions lead to the following version: Code: 01 STO 0 This returns the LCM in X (and R1) and the GCD in Y (and R0). However, I prefer a different algorithm: repeat c = a mod b a = b b = c until c = 0 GCD = a It runs quite fast and can be very elegantly implemented on calculators with mod function and direct stack access. For instance on the HP41: Code: 01 LBL"GCDLCM" No registers, just the stack, returns GCD in X and LCM in Y. This method can also be coded on the 12C: Code: 01 x<=y? This returns the GCD in X (and R2) and the LCM in Y (and R1). Dieter RE: (12C) Least Common Multiple <> GCD - Gamo - 01-07-2018 12:49 AM Thank You Dieter Very helpful to know that [ENTER] [x] is better than [2] [Y^X] and [X<=Y] [X<>Y] [X<>Y] to make Y greater than X Your program version is much better. Gamo |