maths/least_common_multiple very inefficient #2268

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Closed

fhlasek opened this issue Aug 2, 2020 · 1 comment

Contributor

fhlasek commented Aug 2, 2020

The time complexity of the least common multiple implementation is O(max(A, B)) where A and B are the function parameters.

Much more efficient implementation uses the formula with the greatest common divisor which is already implemented efficiently in this repo.

Member

cclauss commented Aug 2, 2020

Without a benchmark, this seems to be a theoretical supposition with no executable proof.

cclauss closed this as completed

fhlasek mentioned this issue

More efficient least common multiple. #2281

Merged

14 tasks

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment