Proposal : LCM function to complement GCD

[CliffM]

BPO	19237
Nosy	@tim-one, @terryjreedy, @mdickinson
Files	lcm.patch lcm2.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2013-10-23.09:10:25.157>
created_at = <Date 2013-10-12.21:39:45.103>
labels = ['extension-modules', 'type-feature']
title = 'Proposal : LCM function to complement GCD'
updated_at = <Date 2020-02-03.11:39:09.848>
user = 'https://bugs.python.org/CliffM'

bugs.python.org fields:

activity = <Date 2020-02-03.11:39:09.848>
actor = 'mark.dickinson'
assignee = 'none'
closed = True
closed_date = <Date 2013-10-23.09:10:25.157>
closer = 'mark.dickinson'
components = ['Extension Modules']
creation = <Date 2013-10-12.21:39:45.103>
creator = 'CliffM'
dependencies = []
files = ['32068', '32084']
hgrepos = []
issue_num = 19237
keywords = ['patch']
message_count = 6.0
messages = ['199624', '199678', '199687', '200326', '201010', '361283']
nosy_count = 4.0
nosy_names = ['tim.peters', 'terry.reedy', 'mark.dickinson', 'CliffM']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = None
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue19237'
versions = ['Python 3.4']

[CliffM]

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 ?

[mdickinson]

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

[CliffM]

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.

[terryjreedy]

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.

[mdickinson]

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

[mdickinson]

See renewed discussion in bpo-39479, which may lead to math.lcm being added in 3.9.