malachite_base/num/arithmetic/
lcm.rs

1// Copyright © 2026 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)$
64            ///
65            /// $M(n) = O(1)$
66            ///
67            /// where $T$ is time, $M$ is additional memory, and $n$ is
68            /// `max(self.significant_bits(), other.significant_bits())`: the cost is dominated by
69            /// the binary GCD, which performs $O(n)$ constant-cost word operations, with no
70            /// allocation.
71            ///
72            /// # Panics
73            /// Panics if the result is too large to be represented.
74            ///
75            /// # Examples
76            /// See [here](super::lcm#lcm_assign).
77            #[inline]
78            fn lcm_assign(&mut self, other: $t) {
79                *self = lcm(*self, other);
80            }
81        }
82
83        impl CheckedLcm<$t> for $t {
84            type Output = $t;
85
86            /// Computes the LCM (least common multiple) of two numbers, returning `None` if the
87            /// result is too large to represent.
88            ///
89            /// $$
90            /// f(x, y) = \\begin{cases}
91            ///     \operatorname{Some}(\operatorname{lcm}(x, y)) &
92            ///         \text{if} \\quad \operatorname{lcm}(x, y) < 2^W, \\\\
93            ///     \operatorname{None} & \text{if} \\quad \operatorname{lcm}(x, y) \geq 2^W,
94            /// \\end{cases}
95            /// $$
96            /// where $W$ is `Self::WIDTH`.
97            ///
98            /// # Worst-case complexity
99            /// $T(n) = O(n)$
100            ///
101            /// $M(n) = O(1)$
102            ///
103            /// where $T$ is time, $M$ is additional memory, and $n$ is
104            /// `max(self.significant_bits(), other.significant_bits())`: the cost is dominated by
105            /// the binary GCD, which performs $O(n)$ constant-cost word operations, with no
106            /// allocation.
107            ///
108            /// # Examples
109            /// See [here](super::lcm#checked_lcm).
110            #[inline]
111            fn checked_lcm(self, other: $t) -> Option<$t> {
112                checked_lcm(self, other)
113            }
114        }
115    };
116}
117apply_to_unsigneds!(impl_lcm);
malachite_base/num/arithmetic/lcm.rs

malachite_base/num/arithmetic/
lcm.rs
