This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

classification
Title: Proposal : LCM function to complement GCD
Type: enhancement Stage:
Components: Extension Modules Versions: Python 3.4
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: Nosy List: CliffM, mark.dickinson, terry.reedy, tim.peters
Priority: normal Keywords: patch

Created on 2013-10-12 21:39 by CliffM, last changed 2022-04-11 14:57 by admin. This issue is now closed.

Files
File name Uploaded Description Edit
lcm.patch CliffM, 2013-10-12 21:39 review
lcm2.patch CliffM, 2013-10-13 10:40 review
Messages (6)
msg199624 - (view) Author: CliffM (CliffM) Date: 2013-10-12 21:39
While implementing a Least-Common-Multiple function (LCM), I noticed that although python has a Greatest-Common-Divisor (GCD) function in the fractions module, the LCM, its counterpart is not there.

I've attached a patch which implements and tests LCM in the fractions module. 

It would really need documentation, but maybe GCD and LCD should be moved to the math module first ?
msg199678 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2013-10-13 09:12
To get the boundary cases correct, you need a special case for lcm(0, 0), which should be 0.

Did you have any particular use-cases in mind for this?  It may make sense to allow multiple arguments:  e.g., lcm(4, 5, 6) -> 60.

Overall, I'm -0 on this addition: I don't think it comes up often enough to make it worth adding, and when it does come up it's easy to create the lcm from the gcd (just as your patch does).
msg199687 - (view) Author: CliffM (CliffM) Date: 2013-10-13 10:40
I've handled a patch, and extended both lcm and gcd to take an arbitrary number of arguments -- via functools.reduce, as they are both multiplicative (in the first argument).

Also handled the zero case , so lcm(0,0) = 0 = gcd(0,0)

Use-case-wise, I do a reasonable amount of number-theoretic work and lcm and gcd are always popping up.  If gcd is defined, it's nice to find lcm too.  

For those less well versed in number-theory, the implementation of lcm is not so obvious, and many end up going down a tedious prime factorisation route -- if they get that far.

But is it all worth it in the fractions module ?  They should really be in the math module.
msg200326 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2013-10-18 23:06
I am -0 (or more negative) for the same reason. The need for lcm is very rare. I think the gcd doc should give the lcm formula, with perhaps an index entry. The gcd doc might also mention that gcd is associative: gcd(a,b,c) = gcd(gcd(a,b),c).

The math module is nearly all float math. The integer only math.factorial(n) is relatively recent. Gcd in in fractions because we do not have an imath module and because the only use of gcd in the stdlib is for reducing fractions.
msg201010 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2013-10-23 09:10
I'm going to reject this for the reasons already given above.  It's easy to write your own (lightweight, inefficient) lcm and multi-argument gcd if you need them.  For more serious work, you probably want to avoid Python's gcd anyway---it's horribly inefficient, and there are 3rd party solutions for specialised number-theoretic work (e.g., SymPy, SAGE, gmpy2).
msg361283 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2020-02-03 11:39
See renewed discussion in #39479, which may lead to math.lcm being added in 3.9.
History
Date User Action Args
2022-04-11 14:57:51adminsetgithub: 63436
2020-02-03 11:39:09mark.dickinsonsetmessages: + msg361283
2013-10-23 09:10:25mark.dickinsonsetstatus: open -> closed
resolution: rejected
messages: + msg201010
2013-10-18 23:06:04terry.reedysetnosy: + terry.reedy
messages: + msg200326
2013-10-13 10:40:13CliffMsetfiles: + lcm2.patch

messages: + msg199687
2013-10-13 09:12:22mark.dickinsonsetmessages: + msg199678
2013-10-12 23:22:52pitrousetnosy: + tim.peters
2013-10-12 23:22:47pitrousetnosy: + mark.dickinson
2013-10-12 21:39:45CliffMcreate