[DM16] Least Common Multipple (LCM)) on stack

Contributed software for the DM10, DM11, DM12, DM15 and DM16 goes here.

Please prefix the subject of your post with the model of the calculator that your program is for.
Post Reply
IainGray
Posts: 6
Joined: Sat Mar 07, 2020 10:55 am

[DM16] Least Common Multipple (LCM)) on stack

Post by IainGray »

The LCM https://en.wikipedia.org/wiki/Least_common_multiple is one of the most useful of the simpler Number Theoretic functions, and is essential when developing fractional arithmetic libraries. Defining it as LCM(a, b) = abs(a * b) / GCD(a, b) it can be evaluated entirely on the stack without using any external registers. The code
Screenshot 2020-04-26 at 17.38.54.png
Screenshot 2020-04-26 at 17.38.54.png (58.15 KiB) Viewed 4436 times
lines 1 to 9 is the GCD routine, and lines 10 to 23 the Duplication routine, both described in earlier posts. Subroutine C duplicates the stack, then calculates the numerator placing at the top of the stack, then calculates the denominator, finally after rolling and swapping produces the LCM. An example usage is 21 <ENTER> 35 <GSB> C which results in 105.
whuyse
Posts: 198
Joined: Thu Dec 21, 2017 1:23 pm

Re: [DM16] Least Common Multipple (LCM)) on stack

Post by whuyse »

It is better to calculate the LCM(a,b) as (b/GCD(a,b))*a, that way you won't lose digits if the product a*b exceeds 1e12, so

Code: Select all

LBL C
GSB D
GSB E
/
*
RTN
Cheers, Werner
41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE, DM15L
IainGray
Posts: 6
Joined: Sat Mar 07, 2020 10:55 am

Re: [DM16] Least Common Multipple (LCM)) on stack

Post by IainGray »

thanks, I agree that your implementation works better in practice in preserving high order bits. My posts were intended to show how much could be done by using the stack without having to resort to external register storage.
thanks again, Iain
Post Reply