qfall_math/integer/z/
properties.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 includes functionality about properties of [`Z`] instances.
10
11use super::Z;
12use crate::rational::Q;
13use flint_sys::{
14    fmpq::{fmpq, fmpq_inv},
15    fmpz::{
16        fmpz, fmpz_abs, fmpz_bits, fmpz_is_one, fmpz_is_perfect_power, fmpz_is_prime, fmpz_is_zero,
17        fmpz_tstbit,
18    },
19};
20
21impl Z {
22    /// Checks if a [`Z`] is `0`.
23    ///
24    /// Returns `true` if the value is `0`.
25    ///
26    /// # Examples
27    /// ```
28    /// use qfall_math::integer::Z;
29    ///
30    /// let value = Z::ZERO;
31    /// assert!(value.is_zero());
32    /// ```
33    pub fn is_zero(&self) -> bool {
34        1 == unsafe { fmpz_is_zero(&self.value) }
35    }
36
37    /// Checks if a [`Z`] is `1`.
38    ///
39    /// Returns `true` if the value is `1`.
40    ///
41    /// # Examples
42    /// ```
43    /// use qfall_math::integer::Z;
44    ///
45    /// let value = Z::ONE;
46    /// assert!(value.is_one());
47    /// ```
48    pub fn is_one(&self) -> bool {
49        1 == unsafe { fmpz_is_one(&self.value) }
50    }
51
52    /// Checks if a [`Z`] is prime.
53    ///
54    /// Returns `true` if the value is prime.
55    ///
56    /// # Examples
57    /// ```
58    /// use qfall_math::integer::Z;
59    ///
60    /// let value = Z::from(17);
61    /// assert!(value.is_prime());
62    /// ```
63    pub fn is_prime(&self) -> bool {
64        1 == unsafe { fmpz_is_prime(&self.value) }
65    }
66
67    /// Returns the given [`Z`] instance with its absolute value.
68    ///
69    /// # Examples
70    /// ```
71    /// use qfall_math::integer::Z;
72    /// let mut value = Z::from(-1);
73    ///
74    /// let value = value.abs();
75    ///
76    /// assert_eq!(Z::ONE, value);
77    /// ```
78    pub fn abs(mut self) -> Self {
79        unsafe {
80            fmpz_abs(&mut self.value, &self.value);
81        }
82        self
83    }
84
85    /// Returns the inverse of `self` as a fresh [`Q`] instance.
86    ///
87    /// As the inverse of `0` is undefined, it returns `None` in case `self == 0`.
88    ///
89    /// # Examples
90    /// ```
91    /// use qfall_math::{integer::Z, rational::Q};
92    /// let value = Z::from(4);
93    ///
94    /// let inverse = value.inverse().unwrap();
95    ///
96    /// assert_eq!(Q::from((1, 4)), inverse);
97    /// ```
98    pub fn inverse(&self) -> Option<Q> {
99        if self == &Z::ZERO {
100            return None;
101        }
102
103        let mut out = Q::ZERO;
104        // the manual construction of fmpq removes the need to clone self's value/
105        // the numerator. the new fmpz value does not need to be cleared manually
106        // as it's small the fmpq instance does neither as the fmpq value is
107        // dropped automatically, but the numerator/ self's value is kept alive
108        let self_fmpq = fmpq {
109            num: self.value,
110            den: fmpz(1),
111        };
112        unsafe { fmpq_inv(&mut out.value, &self_fmpq) };
113        Some(out)
114    }
115
116    /// Computes the number of bits needed to store the absolute value of `self`.
117    ///
118    /// The number of bits needs to fit into an [`u64`],
119    /// i.e. the size should not exceed `2^(2^64)`.
120    /// Otherwise, the result is undefined.
121    ///
122    /// # Examples
123    /// ```
124    /// use qfall_math::integer::Z;
125    /// let value = Z::from(4);
126    ///
127    /// let nr_bits = value.bits();
128    ///
129    /// assert_eq!(3, nr_bits);
130    /// ```
131    pub fn bits(&self) -> u64 {
132        unsafe { fmpz_bits(&self.value) }
133    }
134
135    /// Computes the [`Vec`] of [`bool`] bits corresponding
136    /// to the bits of the absolute value of `self`.
137    ///
138    /// The first bit is the least significant bit.
139    ///
140    /// # Examples
141    /// ```
142    /// use qfall_math::integer::Z;
143    /// let value = Z::from(4);
144    ///
145    /// let vec_bits = value.to_bits();
146    ///
147    /// assert_eq!(vec![false, false, true], vec_bits);
148    /// ```
149    pub fn to_bits(&self) -> Vec<bool> {
150        // compute absolute value
151        let value = self.clone().abs();
152        // resulting bit-vector
153        let mut bits = Vec::with_capacity(value.bits() as usize);
154        for i in 0..value.bits() {
155            // get i-th bit of value
156            let bit_i = unsafe { fmpz_tstbit(&value.value, i) };
157            // appends i-th bit to vector
158            if bit_i == 0 {
159                bits.push(false);
160            } else {
161                bits.push(true);
162            }
163        }
164
165        bits
166    }
167
168    /// Computes a pair `(root, exp)` s.t. `root^exp = self`
169    /// if `self` is a perfect power and can be represented via `root.pow(exp)`.
170    ///
171    /// This algorithm tries to find the smallest perfect root,
172    /// but there is no formal guarantee to find it.
173    ///
174    /// Returns a pair `(root, exp)` if `root.pow(exp) = self` exists. Otherwise,
175    /// `None` is returned.
176    ///
177    /// # Examples
178    /// ```
179    /// use qfall_math::integer::Z;
180    /// let value = Z::from(16);
181    ///
182    /// let (root, exp) = value.is_perfect_power().unwrap();
183    ///
184    /// assert_eq!(root, Z::from(2));
185    /// assert_eq!(exp, 4);
186    /// ```
187    pub fn is_perfect_power(&self) -> Option<(Self, i32)> {
188        let mut root = Z::default();
189        let exp = unsafe { fmpz_is_perfect_power(&mut root.value, &self.value) };
190        if root.is_zero() && exp == 0 {
191            return None;
192        }
193        Some((root, exp))
194    }
195}
196
197#[cfg(test)]
198mod test_is_perfect_power {
199    use super::Z;
200    use crate::traits::Pow;
201
202    /// Ensures that positive small values for root 2 are correctly dissembled.
203    #[test]
204    fn positive_small_2() {
205        let x = Z::from(32);
206
207        let (root, exp) = x.is_perfect_power().unwrap();
208
209        assert_eq!(root, Z::from(2));
210        assert_eq!(exp, 5);
211    }
212
213    /// Ensures that positive small values for root 5 are correctly dissembled.
214    #[test]
215    fn positive_small_5() {
216        let x = Z::from(25);
217
218        let (root, exp) = x.is_perfect_power().unwrap();
219
220        assert_eq!(root, Z::from(5));
221        assert_eq!(exp, 2);
222    }
223
224    /// Ensures that positive small values non perfect powers return None.
225    #[test]
226    fn positive_small_non_perfect_power() {
227        let x = Z::from(26);
228
229        let result = x.is_perfect_power();
230
231        assert!(result.is_none());
232    }
233
234    /// Ensures that positive large values for root 2 are correctly dissembled.
235    #[test]
236    fn positive_large_2() {
237        let x = Z::from(i64::MAX as u64 + 1);
238
239        let (root, exp) = x.is_perfect_power().unwrap();
240
241        assert_eq!(root, Z::from(2));
242        assert_eq!(exp, 63);
243    }
244
245    /// Ensures that positive large values for root 5 are correctly dissembled.
246    #[test]
247    fn positive_large_5() {
248        let x = Z::from(5).pow(67).unwrap();
249
250        let (root, exp) = x.is_perfect_power().unwrap();
251
252        assert_eq!(root, Z::from(5));
253        assert_eq!(exp, 67);
254    }
255
256    /// Ensures that positive large values for 25^50 are correctly dissembled.
257    #[test]
258    fn positive_large_25() {
259        let x = Z::from(25).pow(50).unwrap();
260
261        let (root, exp) = x.is_perfect_power().unwrap();
262
263        assert_eq!(root, Z::from(5));
264        assert_eq!(exp, 100);
265    }
266
267    /// Ensures that positive large values non perfect powers return None.
268    #[test]
269    fn positive_large_non_perfect_power() {
270        let x = Z::from(i64::MAX);
271
272        let result = x.is_perfect_power();
273
274        assert!(result.is_none());
275    }
276
277    /// Ensures that zero is correctly dissembled.
278    #[test]
279    fn zero() {
280        let x = Z::ZERO;
281
282        let (root, exp) = x.is_perfect_power().unwrap();
283
284        assert!(root.is_zero());
285        assert!(exp > 0);
286    }
287
288    /// Ensures that negative small values for root -2 are correctly dissembled.
289    #[test]
290    fn negative_small_2() {
291        let x = Z::from(-32);
292
293        let (root, exp) = x.is_perfect_power().unwrap();
294
295        assert_eq!(root, Z::from(-2));
296        assert_eq!(exp, 5);
297    }
298
299    /// Ensures that negative small values for root -5 are correctly dissembled.
300    #[test]
301    fn negative_small_5() {
302        let x = Z::from(-125);
303
304        let (root, exp) = x.is_perfect_power().unwrap();
305
306        assert_eq!(root, Z::from(-5));
307        assert_eq!(exp, 3);
308    }
309
310    /// Ensures that negative small values non perfect powers return None.
311    #[test]
312    fn negative_small_non_perfect_power() {
313        let x = Z::from(-26);
314
315        let result = x.is_perfect_power();
316
317        assert!(result.is_none());
318    }
319
320    /// Ensures that negative large values for root -2 are correctly dissembled.
321    #[test]
322    fn negative_large_2() {
323        let x = Z::from(i64::MIN);
324
325        let (root, exp) = x.is_perfect_power().unwrap();
326
327        assert_eq!(root, Z::from(-2));
328        assert_eq!(exp, 63);
329    }
330
331    /// Ensures that negative large values for root -5 are correctly dissembled.
332    #[test]
333    fn negative_large_5() {
334        let x = Z::from(-5).pow(67).unwrap();
335
336        let (root, exp) = x.is_perfect_power().unwrap();
337
338        assert_eq!(root, Z::from(-5));
339        assert_eq!(exp, 67);
340    }
341
342    /// Ensures that negative large values for root -25 are correctly dissembled.
343    #[test]
344    fn negative_large_25() {
345        let x = Z::from(-25).pow(67).unwrap();
346
347        let (root, exp) = x.is_perfect_power().unwrap();
348
349        assert_eq!(root, Z::from(-25));
350        assert_eq!(exp, 67);
351    }
352
353    /// Ensures that negative large values non perfect powers return None.
354    #[test]
355    fn negative_large_non_perfect_power() {
356        let x = Z::from(i64::MIN + 1);
357
358        let result = x.is_perfect_power();
359
360        assert!(result.is_none());
361    }
362}
363
364#[cfg(test)]
365mod test_to_bits {
366    use super::Z;
367
368    /// Ensures that `to_bits` works properly for small and large positive integer values.
369    #[test]
370    fn positive() {
371        let value_0 = Z::from(16);
372        let value_1 = Z::from(u64::MAX);
373
374        let res_0 = value_0.to_bits();
375        let res_1 = value_1.to_bits();
376
377        assert_eq!(vec![false, false, false, false, true], res_0);
378        assert_eq!(vec![true; 64], res_1);
379    }
380
381    /// Ensures that `to_bits` works properly for zero.
382    #[test]
383    fn zero() {
384        let value = Z::ZERO;
385        let cmp: Vec<bool> = vec![];
386
387        let res = value.to_bits();
388
389        assert_eq!(cmp, res);
390    }
391
392    /// Ensures that `to_bits` works properly for small and large negative integer values.
393    #[test]
394    fn negative() {
395        let value_0 = Z::from(-13);
396        let value_1 = Z::from(i64::MIN);
397        let mut cmp = vec![false; 63];
398        cmp.push(true);
399
400        let res_0 = value_0.to_bits();
401        let res_1 = value_1.to_bits();
402
403        assert_eq!(vec![true, false, true, true], res_0);
404        assert_eq!(cmp, res_1);
405    }
406}
407
408#[cfg(test)]
409mod test_bits {
410    use super::Z;
411
412    /// Checks whether the number of bits needed to store the absolute value
413    /// is output correctly for small values.
414    #[test]
415    fn small_values() {
416        assert_eq!(0, Z::ZERO.bits());
417        assert_eq!(1, Z::ONE.bits());
418        assert_eq!(1, Z::MINUS_ONE.bits());
419        assert_eq!(3, Z::from(4).bits());
420        assert_eq!(31, Z::from(i32::MAX).bits());
421        assert_eq!(32, Z::from(i32::MIN).bits());
422        assert_eq!(32, Z::from(u32::MAX).bits());
423    }
424
425    /// Checks whether the number of bits needed to store the absolute value
426    /// is output correctly for large values.
427    #[test]
428    fn large_values() {
429        let vector = vec![255; 16];
430        let large = Z::from_bytes(&vector);
431
432        assert_eq!(128, large.bits());
433        assert_eq!(63, Z::from(i64::MAX).bits());
434        assert_eq!(64, Z::from(i64::MIN).bits());
435        assert_eq!(64, Z::from(u64::MAX).bits());
436    }
437}
438
439#[cfg(test)]
440mod test_abs {
441    use super::Z;
442
443    /// Checks whether `abs` returns the positive value for small values correctly.
444    #[test]
445    fn small_values() {
446        let pos = Z::ONE;
447        let zero = Z::ZERO;
448        let neg = Z::from(-15);
449
450        assert_eq!(Z::ONE, pos.abs());
451        assert_eq!(Z::ZERO, zero.abs());
452        assert_eq!(Z::from(15), neg.abs());
453    }
454
455    /// Checks whether `abs` returns the positive value for large values correctly.
456    #[test]
457    fn large_values() {
458        let pos = Z::from(i64::MAX);
459        let neg = Z::from(i64::MIN);
460
461        assert_eq!(Z::from(i64::MAX), pos.abs());
462        assert_eq!(Z::from(i64::MIN) * Z::from(-1), neg.abs());
463    }
464}
465
466#[cfg(test)]
467mod test_is_prime {
468    use super::Z;
469
470    /// Ensure that primes are correctly detected
471    #[test]
472    fn prime_detection() {
473        let small = Z::from(2_i32.pow(16) + 1);
474        let large = Z::from(u64::MAX - 58);
475        assert!(small.is_prime());
476        assert!(large.is_prime());
477    }
478
479    /// Ensure that non-primes are correctly detected
480    #[test]
481    fn non_prime_detection() {
482        let small = Z::from(2_i32.pow(16));
483        let large = Z::from(i64::MAX);
484        assert!(!small.is_prime());
485        assert!(!large.is_prime());
486    }
487}
488
489#[cfg(test)]
490mod test_inv {
491    use super::{Q, Z};
492
493    /// Checks whether the inverse is correctly computed for small values.
494    #[test]
495    fn small_values() {
496        let val_0 = Z::from(4);
497        let val_1 = Z::from(-7);
498
499        let inv_0 = val_0.inverse().unwrap();
500        let inv_1 = val_1.inverse().unwrap();
501
502        assert_eq!(Q::from((1, 4)), inv_0);
503        assert_eq!(Q::from((-1, 7)), inv_1);
504    }
505
506    /// Checks whether the inverse is correctly computed for large values.
507    #[test]
508    fn large_values() {
509        let val_0 = Z::from(i64::MAX);
510        let val_1 = Z::from(i64::MIN);
511
512        let inv_0 = val_0.inverse().unwrap();
513        let inv_1 = val_1.inverse().unwrap();
514
515        assert_eq!(Q::from((1, i64::MAX)), inv_0);
516        assert_eq!(Q::from((1, i64::MIN)), inv_1);
517    }
518
519    /// Checks whether the inverse of `0` returns `None`.
520    #[test]
521    fn inv_zero_none() {
522        let zero = Z::ZERO;
523
524        let inv_zero = zero.inverse();
525
526        assert!(inv_zero.is_none());
527    }
528}
529
530#[cfg(test)]
531mod test_is_zero {
532    use super::Z;
533    use std::str::FromStr;
534
535    /// Ensure that is_zero returns `true` for `0`.
536    #[test]
537    fn zero_detection() {
538        let zero = Z::ZERO;
539
540        assert!(zero.is_zero());
541    }
542
543    /// Ensure that is_zero returns `false` for non-zero values.
544    #[test]
545    fn zero_rejection() {
546        let small = Z::from(2);
547        let large = Z::from_str(&format!("{}", (u128::MAX - 1) / 2 + 1)).unwrap();
548
549        assert!(!small.is_zero());
550        assert!(!large.is_zero());
551    }
552}
553
554#[cfg(test)]
555mod test_is_one {
556    use super::Z;
557    use std::str::FromStr;
558
559    /// Ensure that is_one returns `true` for `1`.
560    #[test]
561    fn one_detection() {
562        let zero = Z::ONE;
563
564        assert!(zero.is_one());
565    }
566
567    /// Ensure that is_one returns `false` for other values.
568    #[test]
569    fn one_rejection() {
570        let small = Z::from(2);
571        let large = Z::from_str(&format!("{}", (u128::MAX - 1) / 2 + 2)).unwrap();
572
573        assert!(!small.is_one());
574        assert!(!large.is_one());
575    }
576}
qfall_math/integer/z/properties.rs

qfall_math/integer/z/
properties.rs
