qfall_math/integer/z/
gcd.rs

1// Copyright © 2023 Niklas Siemer
2//
3// This file is part of qFALL-math.
4//
5// qFALL-math is free software: you can redistribute it and/or modify it under
6// the terms of the Mozilla Public License Version 2.0 as published by the
7// Mozilla Foundation. See <https://mozilla.org/en-US/MPL/2.0/>.
8
9//! This module contains the implementation of the [`Gcd`]
10//! and [`Xgcd`] trait for [`Z`].
11
12use super::Z;
13use crate::traits::{Gcd, Xgcd};
14use flint_sys::fmpz::{fmpz_gcd, fmpz_xgcd};
15
16impl<Integer: Into<Z>> Gcd<Integer> for Z {
17    type Output = Z;
18
19    /// Outputs the greatest common divisor (gcd) of the two given values
20    /// with `gcd(a, 0) = |a|`.
21    ///
22    /// Parameters:
23    /// - `other`: specifies one of the values of which the gcd is computed
24    ///
25    /// Returns the greatest common divisor of `self` and `other` as
26    /// a [`Z`] instance.
27    ///
28    /// # Examples
29    /// ```
30    /// use qfall_math::integer::Z;
31    /// use qfall_math::traits::*;
32    ///
33    /// let val_1 = Z::from(10);
34    /// let val_2 = Z::from(15);
35    ///
36    /// let gcd = val_1.gcd(&val_2);
37    ///
38    /// assert_eq!(Z::from(5), gcd);
39    /// ```
40    fn gcd(&self, other: Integer) -> Self::Output {
41        let other = other.into();
42        let mut out = Z::default();
43        unsafe { fmpz_gcd(&mut out.value, &self.value, &other.value) };
44        out
45    }
46}
47
48impl<Integer: Into<Z>> Xgcd<Integer> for Z {
49    type Output = (Z, Z, Z);
50
51    /// Outputs the extended greatest common divisor (xgcd) of the two given values,
52    /// i.e. a triple `(gcd(a, b), x, y)`, where `a*x + b*y = gcd(a, b)*`.
53    ///
54    /// Parameters:
55    /// - `other`: specifies one of the values of which the gcd is computed
56    ///
57    /// Returns a triple `(gcd(a, b), x, y)` containing the greatest common divisor,
58    /// `x`, and `y` s.t. `gcd(a, b) = a*x + b*y`.
59    ///
60    /// # Examples
61    /// ```
62    /// use qfall_math::integer::Z;
63    /// use qfall_math::traits::*;
64    ///
65    /// let val_1 = Z::from(10);
66    /// let val_2 = Z::from(15);
67    ///
68    /// let (gcd, x, y) = val_1.xgcd(&val_2);
69    /// let cmp_gcd = &val_1 * &x + &val_2 * &y;
70    ///
71    /// assert_eq!(Z::from(5), gcd);
72    /// assert_eq!(gcd, cmp_gcd);
73    /// ```
74    fn xgcd(&self, other: Integer) -> Self::Output {
75        let other = other.into();
76        let mut gcd = Z::ZERO;
77        let mut x = Z::ZERO;
78        let mut y = Z::ZERO;
79        unsafe {
80            fmpz_xgcd(
81                &mut gcd.value,
82                &mut x.value,
83                &mut y.value,
84                &self.value,
85                &other.value,
86            )
87        };
88        (gcd, x, y)
89    }
90}
91
92#[cfg(test)]
93mod test_gcd {
94    use super::{Gcd, Z};
95
96    /// Ensures that the gcd is correctly computed for small [`Z`] instances
97    /// and ensures properties: `gcd(a, b) == gcd(b, a)` and `gcd(a, a) == a`
98    #[test]
99    fn small() {
100        let pos_1 = Z::from(10);
101        let pos_2 = Z::from(15);
102        let neg_1 = Z::from(-10);
103        let neg_2 = Z::from(-15);
104
105        let gcd_pos_1 = pos_1.gcd(&pos_2);
106        let gcd_pos_2 = pos_2.gcd(&pos_1);
107        let gcd_pos_eq = pos_1.gcd(&pos_1);
108        let gcd_mix_1 = pos_1.gcd(&neg_1);
109        let gcd_mix_2 = neg_2.gcd(&pos_1);
110        let gcd_neg_1 = neg_1.gcd(&neg_2);
111        let gcd_neg_2 = neg_2.gcd(&neg_1);
112        let gcd_neg_eq = neg_2.gcd(&neg_2);
113
114        assert_eq!(Z::from(5), gcd_pos_1);
115        assert_eq!(Z::from(5), gcd_pos_2);
116        assert_eq!(Z::from(10), gcd_pos_eq);
117        assert_eq!(Z::from(10), gcd_mix_1);
118        assert_eq!(Z::from(5), gcd_mix_2);
119        assert_eq!(Z::from(5), gcd_neg_1);
120        assert_eq!(Z::from(5), gcd_neg_2);
121        assert_eq!(Z::from(15), gcd_neg_eq);
122    }
123
124    /// Ensures that the gcd is correctly computed for small [`Z`] instances
125    /// and ensures properties: `gcd(a, b) == gcd(b, a)`, `gcd(a, a) == a`, and
126    /// `gcd(a, 0) == a`
127    #[test]
128    fn large() {
129        let pos = Z::from(i64::MAX);
130        let zero = Z::ZERO;
131        let neg = Z::from(i64::MIN);
132        let abs_neg = Z::MINUS_ONE * &neg;
133
134        let gcd_1 = pos.gcd(&zero);
135        let gcd_2 = pos.gcd(&pos);
136        let gcd_3 = neg.gcd(&zero);
137        let gcd_4 = neg.gcd(&neg);
138        let gcd_5 = pos.gcd(&neg);
139
140        assert_eq!(pos, gcd_1);
141        assert_eq!(pos, gcd_2);
142        assert_eq!(abs_neg, gcd_3);
143        assert_eq!(abs_neg, gcd_4);
144        assert_eq!(Z::ONE, gcd_5);
145    }
146
147    /// Ensure that gcd trait/ implementation is available for other types
148    #[test]
149    fn availability() {
150        let z = Z::ONE;
151
152        let _ = z.gcd(z.clone());
153        let _ = z.gcd(4_u8);
154        let _ = z.gcd(4_u16);
155        let _ = z.gcd(4_u32);
156        let _ = z.gcd(4_u64);
157        let _ = z.gcd(4_i8);
158        let _ = z.gcd(4_i16);
159        let _ = z.gcd(4_i32);
160        let _ = z.gcd(4_i64);
161    }
162}
163
164#[cfg(test)]
165mod test_xgcd {
166    use super::{Xgcd, Z};
167
168    /// Ensures that the gcd is correctly computed for small [`Z`] instances
169    /// and ensures properties: `gcd(a, b) == gcd(b, a)` and `gcd(a, a) == a`
170    #[test]
171    fn gcd_small() {
172        let pos_1 = Z::from(10);
173        let pos_2 = Z::from(15);
174        let neg_1 = Z::from(-10);
175        let neg_2 = Z::from(-15);
176
177        let xgcd_pos_1 = pos_1.xgcd(&pos_2);
178        let xgcd_pos_2 = pos_2.xgcd(&pos_1);
179        let xgcd_pos_eq = pos_1.xgcd(&pos_1);
180        let xgcd_mix_1 = pos_1.xgcd(&neg_1);
181        let xgcd_mix_2 = neg_2.xgcd(&pos_1);
182        let xgcd_neg_1 = neg_1.xgcd(&neg_2);
183        let xgcd_neg_2 = neg_2.xgcd(&neg_1);
184        let xgcd_neg_eq = neg_2.xgcd(&neg_2);
185
186        assert_eq!(Z::from(5), xgcd_pos_1.0);
187        assert_eq!(Z::from(5), xgcd_pos_2.0);
188        assert_eq!(Z::from(10), xgcd_pos_eq.0);
189        assert_eq!(Z::from(10), xgcd_mix_1.0);
190        assert_eq!(Z::from(5), xgcd_mix_2.0);
191        assert_eq!(Z::from(5), xgcd_neg_1.0);
192        assert_eq!(Z::from(5), xgcd_neg_2.0);
193        assert_eq!(Z::from(15), xgcd_neg_eq.0);
194    }
195
196    /// Ensures that the gcd is correctly computed for small [`Z`] instances
197    /// and ensures properties: `gcd(a, b) == gcd(b, a)`, `gcd(a, a) == a`, and
198    /// `gcd(a, 0) == a`
199    #[test]
200    fn gcd_large() {
201        let pos = Z::from(i64::MAX);
202        let zero = Z::ZERO;
203        let neg = Z::from(i64::MIN);
204        let abs_neg = Z::MINUS_ONE * &neg;
205
206        let xgcd_1 = pos.xgcd(&zero);
207        let xgcd_2 = pos.xgcd(&pos);
208        let xgcd_3 = neg.xgcd(&zero);
209        let xgcd_4 = neg.xgcd(&neg);
210        let xgcd_5 = pos.xgcd(&neg);
211
212        assert_eq!(pos, xgcd_1.0);
213        assert_eq!(pos, xgcd_2.0);
214        assert_eq!(abs_neg, xgcd_3.0);
215        assert_eq!(abs_neg, xgcd_4.0);
216        assert_eq!(Z::ONE, xgcd_5.0);
217    }
218
219    /// Ensures that the computation of `x` and `y` works correctly
220    /// s.t. `a*x + b*y = gcd(a, b)` for small values
221    #[test]
222    fn xy_small() {
223        let pos_1 = Z::from(10);
224        let pos_2 = Z::from(15);
225        let neg_1 = Z::from(-10);
226        let neg_2 = Z::from(-15);
227
228        let xgcd_pos_1 = pos_1.xgcd(&pos_2);
229        let xgcd_pos_2 = pos_2.xgcd(&pos_1);
230        let xgcd_pos_eq = pos_1.xgcd(&pos_1);
231        let xgcd_mix_1 = pos_1.xgcd(&neg_1);
232        let xgcd_mix_2 = neg_2.xgcd(&pos_1);
233        let xgcd_neg_1 = neg_1.xgcd(&neg_2);
234        let xgcd_neg_2 = neg_2.xgcd(&neg_1);
235        let xgcd_neg_eq = neg_2.xgcd(&neg_2);
236
237        // check that `gcd(a, b) == a * x + b * y`
238        assert_eq!(
239            xgcd_pos_1.0,
240            &pos_1 * &xgcd_pos_1.1 + &pos_2 * &xgcd_pos_1.2
241        );
242        assert_eq!(
243            xgcd_pos_2.0,
244            &pos_2 * &xgcd_pos_2.1 + &pos_1 * &xgcd_pos_2.2
245        );
246        assert_eq!(
247            xgcd_pos_eq.0,
248            &pos_1 * &xgcd_pos_eq.1 + &pos_1 * &xgcd_pos_eq.2
249        );
250        assert_eq!(
251            xgcd_mix_1.0,
252            &pos_1 * &xgcd_mix_1.1 + &neg_1 * &xgcd_mix_1.2
253        );
254        assert_eq!(
255            xgcd_mix_2.0,
256            &neg_2 * &xgcd_mix_2.1 + &pos_1 * &xgcd_mix_2.2
257        );
258        assert_eq!(
259            xgcd_neg_1.0,
260            &neg_1 * &xgcd_neg_1.1 + &neg_2 * &xgcd_neg_1.2
261        );
262        assert_eq!(
263            xgcd_neg_2.0,
264            &neg_2 * &xgcd_neg_2.1 + &neg_1 * &xgcd_neg_2.2
265        );
266        assert_eq!(
267            xgcd_neg_eq.0,
268            &neg_2 * &xgcd_neg_eq.1 + &neg_2 * &xgcd_neg_eq.2
269        );
270    }
271
272    /// Ensures that the computation of `x` and `y` works correctly
273    /// s.t. `a*x + b*y = gcd(a, b)` for large values
274    #[test]
275    fn xy_large() {
276        let pos = Z::from(i64::MAX);
277        let zero = Z::ZERO;
278        let neg = Z::from(i64::MIN);
279
280        let xgcd_1 = pos.xgcd(&zero);
281        let xgcd_2 = pos.xgcd(&pos);
282        let xgcd_3 = neg.xgcd(&zero);
283        let xgcd_4 = neg.xgcd(&neg);
284        let xgcd_5 = pos.xgcd(&neg);
285
286        // check that `gcd(a, b) == a * x + b * y`
287        assert_eq!(xgcd_1.0, &pos * &xgcd_1.1 + &zero * &xgcd_1.2);
288        assert_eq!(xgcd_2.0, &pos * &xgcd_2.1 + &pos * &xgcd_2.2);
289        assert_eq!(xgcd_3.0, &neg * &xgcd_3.1 + &zero * &xgcd_3.2);
290        assert_eq!(xgcd_4.0, &neg * &xgcd_4.1 + &neg * &xgcd_4.2);
291        assert_eq!(xgcd_5.0, &pos * &xgcd_5.1 + &neg * &xgcd_5.2);
292    }
293
294    /// Ensure that xgcd trait/ implementation is available for other types
295    #[test]
296    fn availability() {
297        let z = Z::ONE;
298
299        let _ = z.xgcd(z.clone());
300        let _ = z.xgcd(4_u8);
301        let _ = z.xgcd(4_u16);
302        let _ = z.xgcd(4_u32);
303        let _ = z.xgcd(4_u64);
304        let _ = z.xgcd(4_i8);
305        let _ = z.xgcd(4_i16);
306        let _ = z.xgcd(4_i32);
307        let _ = z.xgcd(4_i64);
308    }
309}
qfall_math/integer/z/gcd.rs

qfall_math/integer/z/
gcd.rs
