malachite_base/num/arithmetic/
lcm.rs

1// Copyright © 2025 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::num::arithmetic::traits::{CheckedLcm, Lcm, LcmAssign};
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11
12#[inline]
13fn lcm<T: PrimitiveUnsigned>(x: T, y: T) -> T {
14    checked_lcm(x, y).unwrap()
15}
16
17fn checked_lcm<T: PrimitiveUnsigned>(x: T, y: T) -> Option<T> {
18    if x == T::ZERO && y == T::ZERO {
19        Some(T::ZERO)
20    } else {
21        (x / x.gcd(y)).checked_mul(y)
22    }
23}
24
25macro_rules! impl_lcm {
26    ($t:ident) => {
27        impl Lcm<$t> for $t {
28            type Output = $t;
29
30            /// Computes the LCM (least common multiple) of two numbers.
31            ///
32            /// $$
33            /// f(x, y) = \operatorname{lcm}(x, y).
34            /// $$
35            ///
36            /// # Worst-case complexity
37            /// $T(n) = O(n^2)$
38            ///
39            /// $M(n) = O(1)$
40            ///
41            /// where $T$ is time, $M$ is additional memory, and $n$ is
42            /// `max(self.significant_bits(), other.significant_bits())`.
43            ///
44            /// # Panics
45            /// Panics if the result is too large to be represented.
46            ///
47            /// # Examples
48            /// See [here](super::lcm#lcm).
49            #[inline]
50            fn lcm(self, other: $t) -> $t {
51                lcm(self, other)
52            }
53        }
54
55        impl LcmAssign<$t> for $t {
56            /// Replaces a number with the LCM (least common multiple) of it and another number.
57            ///
58            /// $$
59            /// x \gets \operatorname{lcm}(x, y).
60            /// $$
61            ///
62            /// # Worst-case complexity
63            /// $T(n) = O(n^2)$
64            ///
65            /// $M(n) = O(n)$
66            ///
67            /// where $T$ is time, $M$ is additional memory, and $n$ is
68            /// `max(self.significant_bits(), other.significant_bits())`.
69            ///
70            /// # Panics
71            /// Panics if the result is too large to be represented.
72            ///
73            /// # Examples
74            /// See [here](super::lcm#lcm_assign).
75            #[inline]
76            fn lcm_assign(&mut self, other: $t) {
77                *self = lcm(*self, other);
78            }
79        }
80
81        impl CheckedLcm<$t> for $t {
82            type Output = $t;
83
84            /// Computes the LCM (least common multiple) of two numbers, returning `None` if the
85            /// result is too large to represent.
86            ///
87            /// $$
88            /// f(x, y) = \\begin{cases}
89            ///     \operatorname{Some}(\operatorname{lcm}(x, y)) &
90            ///         \text{if} \\quad \operatorname{lcm}(x, y) < 2^W, \\\\
91            ///     \operatorname{None} & \text{if} \\quad \operatorname{lcm}(x, y) \geq 2^W,
92            /// \\end{cases}
93            /// $$
94            /// where $W$ is `Self::WIDTH`.
95            ///
96            /// # Worst-case complexity
97            /// $T(n) = O(n^2)$
98            ///
99            /// $M(n) = O(n)$
100            ///
101            /// where $T$ is time, $M$ is additional memory, and $n$ is
102            /// `max(self.significant_bits(), other.significant_bits())`.
103            ///
104            /// # Examples
105            /// See [here](super::lcm#checked_lcm).
106            #[inline]
107            fn checked_lcm(self, other: $t) -> Option<$t> {
108                checked_lcm(self, other)
109            }
110        }
111    };
112}
113apply_to_unsigneds!(impl_lcm);
malachite_base/num/arithmetic/lcm.rs

malachite_base/num/arithmetic/
lcm.rs
