[DM16] Least Common Multipple (LCM)) on stack
[DM16] Least Common Multipple (LCM)) on stack
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 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.
Re: [DM16] Least Common Multipple (LCM)) on stack
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
Cheers, Werner
Code: Select all
LBL C
GSB D
GSB E
/
*
RTN
41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE, DM15L
Re: [DM16] Least Common Multipple (LCM)) on stack
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
thanks again, Iain