malachite-base 0.9.2

A collection of utilities, including new arithmetic traits and iterators that generate all values of a type.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

// Copyright © 2026 Mikhail Hogrefe
//
// This file is part of Malachite.
//
// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.

use malachite_base::num::arithmetic::mod_inverse::mod_inverse_binary;
use malachite_base::num::basic::signeds::PrimitiveSigned;
use malachite_base::num::basic::unsigneds::PrimitiveUnsigned;
use malachite_base::num::conversion::traits::WrappingFrom;
use malachite_base::test_util::generators::{
    unsigned_gen, unsigned_gen_var_6, unsigned_pair_gen_var_38,
};
use malachite_base::test_util::num::arithmetic::mod_inverse::mod_inverse_euclidean;
use std::panic::catch_unwind;

fn mod_inverse_helper<
    U: PrimitiveUnsigned + WrappingFrom<S>,
    S: PrimitiveSigned + WrappingFrom<U>,
>() {
    let test = |n: U, m, out| {
        assert_eq!(n.mod_inverse(m), out);
        assert_eq!(mod_inverse_euclidean::<U, S>(n, m), out);
        assert_eq!(mod_inverse_binary::<U, S>(n, m), out);
    };

    test(U::ONE, U::exact_from(5), Some(U::ONE));
    test(U::exact_from(7), U::exact_from(10), Some(U::exact_from(3)));
    test(U::exact_from(6), U::exact_from(10), None);
    test(
        U::exact_from(100),
        U::exact_from(101),
        Some(U::exact_from(100)),
    );
    test(U::ONE, U::MAX, Some(U::ONE));
    test(U::MAX - U::ONE, U::MAX, Some(U::MAX - U::ONE));
}

#[test]
fn test_mod_inverse() {
    apply_fn_to_unsigned_signed_pairs!(mod_inverse_helper);
}

fn mod_inverse_fail_helper<T: PrimitiveUnsigned>() {
    assert_panic!(T::ZERO.mod_inverse(T::ZERO));
    assert_panic!(T::ZERO.mod_inverse(T::from(10u8)));
    assert_panic!(T::from(123u8).mod_inverse(T::from(123u8)));
}

#[test]
fn mod_inverse_fail() {
    apply_fn_to_unsigneds!(mod_inverse_fail_helper);
}

fn mod_inverse_properties_helper<
    U: PrimitiveUnsigned + WrappingFrom<S>,
    S: PrimitiveSigned + WrappingFrom<U>,
>() {
    unsigned_pair_gen_var_38::<U>().test_properties(|(n, m)| {
        assert!(n.mod_is_reduced(&m));
        let inverse = n.mod_inverse(m);
        assert_eq!(mod_inverse_euclidean::<U, S>(n, m), inverse);
        assert_eq!(mod_inverse_binary::<U, S>(n, m), inverse);
        assert_eq!(inverse.is_some(), n.coprime_with(m));
        if let Some(inverse) = inverse {
            assert!(inverse.mod_is_reduced(&m));
            assert_eq!(inverse.mod_inverse(m), Some(n));
            assert_eq!(n.mod_mul(inverse, m), U::ONE);
            assert_eq!((m - n).mod_inverse(m), Some(m - inverse));
        }
    });

    unsigned_gen_var_6::<U>().test_properties(|m| {
        assert_eq!(U::ONE.mod_inverse(m), Some(U::ONE));
        assert_eq!((m - U::ONE).mod_inverse(m), Some(m - U::ONE));
    });

    unsigned_gen::<U>().test_properties(|x| {
        assert_panic!(x.mod_inverse(U::ZERO));
    });
}

#[test]
fn mod_inverse_properties() {
    apply_fn_to_unsigned_signed_pairs!(mod_inverse_properties_helper);
}