[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Change by Mark Dickinson : -- resolution: -> fixed stage: patch review -> resolved status: open -> closed ___ Python tracker ___

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Mark Dickinson added the comment: New changeset f2ee21d858bc03dd801b97afe60ee2ea289e2fe9 by ananthan-123 in branch 'master': bpo-39479:Add math.lcm() function: Least Common Multiple (#18547) https://github.com/python/cpython/commit/f2ee21d858bc03dd801b97afe60ee2ea289e2fe9 --

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Change by Ananthakrishnan : -- pull_requests: +17925 pull_request: https://github.com/python/cpython/pull/18547 ___ Python tracker ___

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Change by Ananthakrishnan : -- keywords: +patch pull_requests: +17719 stage: -> patch review pull_request: https://github.com/python/cpython/pull/18328 ___ Python tracker ___

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

STINNER Victor added the comment: If someone wants to continue the discussion on is_prime(), I suggest to open a separated issue. -- ___ Python tracker ___

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Tim Peters added the comment: [Tim] >> The pure-Python Miller-Rabin code i posted in the >> aforementioned thread is typically at least 100 >> times faster than that. [Steven] > This is exactly the sort of argument about quality of > implementation which isn't, or shouldn't be, part of > the

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Steven D'Aprano added the comment: > [Steven] > > ... Try it on numbers like this: > > ... > > Q = P*(313*(P-1)+1)*(353*(P-1)+1) > > > > Q is a 397 digit Carmichael Number. Its smallest factor is P, > > which has 131 digits. [Tim] > The pure-Python Miller-Rabin code i posted in the

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Tim Peters added the comment: [Steven] > ... Try it on numbers like this: > ... > Q = P*(313*(P-1)+1)*(353*(P-1)+1) > > Q is a 397 digit Carmichael Number. Its smallest factor is P, > which has 131 digits. > ... > My old and slow PC can prove that Q is a composite number, > using pure Python,

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Vedran Čačić added the comment: Tim: Considering that congruence is _defined_ as x=y(mod m) :<=> m|y-x, it's really not so surprising. :-) Steven: It seems that we completely agree about inclusion of is_probabilistic_prime in stdlib. And we agree that it should be called isprime (or

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Steven D'Aprano added the comment: On Fri, Jan 31, 2020 at 12:15:37PM +, Vedran Čačić wrote: > > Vedran Čačić added the comment: > > is_prime that's always correct is probably not the right thing to go into > math. Besides, now we have isqrt, it's just > > n>1 and n&1 and all(n%d

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Tim Peters added the comment: I'd have to hear back from Raymond more on what he had in mind - I may well have been reading far too much in the specific name he suggested. Don't much care about API, etc - pick something reasonable and go with it. I'm not overly ;-) concerned with being

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Vedran Čačić added the comment: And yeah, I managed to leave out 2. Speaking about "often implemented wrong"... :-)) -- ___ Python tracker ___

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Vedran Čačić added the comment: is_prime that's always correct is probably not the right thing to go into math. Besides, now we have isqrt, it's just n>1 and n&1 and all(n%d for d in range(3,isqrt(n)+1,2)) -- yes, it's damn slow, but so is everything else you want to be absolutely

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

STINNER Victor added the comment: I dislike the idea of adding a is_prime() function in Python since users will likely stress Python with huge numbers and then complain that Python is too slow. Correct is_prime() is very slow for large numbers, and statistically approach is not 100%

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Tim Peters added the comment: Raymond, there was a thread a while back about adding an `imath` module, to package the number-theoretic functions that frequently come up. _All_ these things should really go into that instead, IMO. `math` started as a thin wrapper around C's libm, and has

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Raymond Hettinger added the comment: Perhaps add, is_prime() as well. Conceptually, it is in the same family of functions. Unlike lcm(), it is one that I would use and would improve Python's value as a teaching tool. -- ___ Python tracker

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Tim Peters added the comment: And I in turn agree with everything Mark said ;-) But I'll add that while the analogy to comb/perm is a good one, I think the case for lcm is stronger than for perm. Not only is lcm more common in real life (although, no, not at all common overall!), perm was

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Mark Dickinson added the comment: I'd guess a // gcd(a, b) * b would be faster, on the basis that division is slower than multiplication. But I doubt it's worth worrying about for this implementation, given that the gcd call is likely to be the bottleneck as a and b get large. --

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Serhiy Storchaka added the comment: If a < b, what is better, a // gcd(a, b) * b or b // gcd(a, b) * a ? Or there is no difference? -- ___ Python tracker ___

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Mark Dickinson added the comment: Great. For clarity, here's a Python function giving the behaviour I'd expect from a 2-arg lcm: from math import gcd def lcm(a, b): if a == 0: return 0 return abs(a // gcd(a, b) * b) --

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Ananthakrishnan A S added the comment: Yes,I want to put together a PR. -- ___ Python tracker ___ ___ Python-bugs-list mailing

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Mark Dickinson added the comment: +0 from me as well; agreed with everything that Tim said (except that I've never had a need for the Carmichael function; my RSA implementations do the inefficient thing based on (p-1)(q-1)). This is somewhat reminiscent of comb and perm: lcm is often taught

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Tim Peters added the comment: +0 from me. Another use is computing the Carmichael function for composite numbers (like an RSA encryption modulus, in which context the Carmichael function is routinely used). But only +0 instead of +1 because it's so easy to build from gcd(). I don't agree

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Ananthakrishnan A S added the comment: I agree with Vedran Čačić.As the modules are not made for one person but it is for the ease of coding.There are so many functions which i don't use but used by other people.We are using functions to make coding easy and if lcm function is added many

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Vedran Čačić added the comment: I agree with Raymond that it's really seldom needed. However, I'd like to point out that the "trivial" implementation might not be so trivial after all: as Steven said, it mishandles (0,0) case. And even Tim fell into that trap, so it can't be said it's easily

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Raymond Hettinger added the comment: -1 Given that we had gcd(), I don't see any value to adding *lcm()* as well. Once you have gcd(), getting the least common multiple is trivial. Also, it is rare to ever need a lcm() function. I don't think I've ever seen it in real code. --

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Ananthakrishnan A S added the comment: some problems that needs lcm function: 1:find the least number which when divided by 'a','b','c','d' leaves remainder 'e' in each case. 2:person A exercises every 'n' days and person B every 'm' days. A and B both exercised today. How many days will

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Vedran Čačić added the comment: I must say that the problem (with two classes divided into teams) seems to me to be exactly one that can be solved with gcd, and lcm itself is mostly useless for it. -- nosy: +veky ___ Python tracker

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Ananthakrishnan A S added the comment: Should i proceed with adding a pull request for adding a 'lcm' function in python's math module. -- ___ Python tracker ___

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Ananthakrishnan A S added the comment: I created this issue as i came across the following question: There are n students in class A,and m students in class B.each class divides into teams for a competition.What is the biggest possible team size that can be divided,such that each team has

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Serhiy Storchaka added the comment: reduce(gcd, [a, b, c, d, e]) -- ___ Python tracker ___ ___ Python-bugs-list mailing list

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Change by STINNER Victor : -- nosy: +serhiy.storchaka ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

Steven D'Aprano added the comment: Uses for lcm are common enough that it is provided by Excel and the C++ boost. You can use it for working out problems like: - if event A happens every 14 days, and event B happens every 6 days, then A and B will occur together even lcm(14, 6) days. By

[issue39479] [RFE] Add math.lcm() function: Least Common Multiple

STINNER Victor added the comment: There is math.gcd(): https://docs.python.org/dev/library/math.html#math.gcd You can use numpy.lcm(): https://docs.scipy.org/doc/numpy-1.15.0/reference/generated/numpy.lcm.html Is it common to need lcm()? Do you have examples of applications which need