malachite-nz 0.9.2

The bignum types Natural and Integer, with efficient algorithms partially derived from GMP and FLINT.
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

// Copyright © 2026 Mikhail Hogrefe
//
// Uses code adopted from the GNU MP Library.
//
//      Copyright © 2000-2002, 2012 Free Software Foundation, Inc.
//
// 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 crate::natural::arithmetic::divisible_by::{
    limbs_divisible_by_limb, limbs_divisible_by_val_ref,
};
use crate::natural::arithmetic::eq_mod::limbs_eq_limb_mod_limb;
use crate::natural::arithmetic::mod_op::{limbs_mod, limbs_mod_limb};
use crate::natural::arithmetic::sub::{limbs_sub, limbs_sub_limb};
use crate::natural::comparison::cmp::limbs_cmp;
use crate::platform::{BMOD_1_TO_MOD_1_THRESHOLD, DoubleLimb, Limb};
use malachite_base::num::arithmetic::traits::DivisibleBy;
use malachite_base::slices::slice_trailing_zeros;
use std::cmp::Ordering::*;

pub fn limbs_eq_limb_mod_naive_1(xs: &[Limb], y: Limb, ms: &[Limb]) -> bool {
    assert!(xs.len() > 1);
    assert!(ms.len() > 1);
    let mut xs_mod = if xs.len() >= ms.len() {
        limbs_mod(xs, ms)
    } else {
        xs.to_vec()
    };
    xs_mod.truncate(xs_mod.len() - slice_trailing_zeros(&xs_mod));
    xs_mod == [y]
}

pub fn limbs_eq_limb_mod_naive_2(xs: &[Limb], y: Limb, ms: &[Limb]) -> bool {
    let mut diff = limbs_sub_limb(xs, y).0;
    diff.truncate(diff.len() - slice_trailing_zeros(&diff));
    diff.len() >= ms.len() && limbs_divisible_by_val_ref(&mut diff, ms)
}

pub fn limbs_eq_mod_limb_naive_1(xs: &[Limb], ys: &[Limb], ms: Limb) -> bool {
    assert!(xs.len() > 1);
    assert!(ys.len() > 1);
    limbs_mod_limb::<DoubleLimb, Limb>(xs, ms) == limbs_mod_limb::<DoubleLimb, Limb>(ys, ms)
}

pub fn limbs_eq_mod_limb_naive_2(xs: &[Limb], ys: &[Limb], ms: Limb) -> bool {
    if xs == ys {
        return true;
    }
    let mut diff = if limbs_cmp(xs, ys) >= Equal {
        limbs_sub(xs, ys)
    } else {
        limbs_sub(ys, xs)
    }
    .0;
    diff.truncate(diff.len() - slice_trailing_zeros(&diff));
    if diff.len() == 1 {
        diff[0].divisible_by(ms)
    } else {
        limbs_divisible_by_limb(&diff, ms)
    }
}

pub fn limbs_eq_mod_naive_1(xs: &[Limb], ys: &[Limb], ms: &[Limb]) -> bool {
    let mut xs_mod = if xs.len() >= ms.len() {
        limbs_mod(xs, ms)
    } else {
        xs.to_vec()
    };
    let mut ys_mod = if ys.len() >= ms.len() {
        limbs_mod(ys, ms)
    } else {
        ys.to_vec()
    };
    xs_mod.truncate(xs_mod.len() - slice_trailing_zeros(&xs_mod));
    ys_mod.truncate(ys_mod.len() - slice_trailing_zeros(&ys_mod));
    limbs_cmp(&xs_mod, &ys_mod) == Equal
}

pub fn limbs_eq_mod_naive_2(xs: &[Limb], ys: &[Limb], ms: &[Limb]) -> bool {
    if xs == ys {
        return true;
    }
    let mut diff = if limbs_cmp(xs, ys) >= Equal {
        limbs_sub(xs, ys)
    } else {
        limbs_sub(ys, xs)
    }
    .0;
    diff.truncate(diff.len() - slice_trailing_zeros(&diff));
    diff.len() >= ms.len() && limbs_divisible_by_val_ref(&mut diff, ms)
}

/// Benchmarks show that this is never faster than just calling `limbs_eq_limb_mod_limb`.
///
/// xs.len() must be greater than 1; m must be nonzero.
///
/// This is equivalent to `mpz_congruent_ui_p` from `mpz/cong_ui.c`, GMP 6.2.1, where `a` is
/// non-negative.
pub fn combined_limbs_eq_limb_mod_limb(xs: &[Limb], y: Limb, m: Limb) -> bool {
    if xs.len() < BMOD_1_TO_MOD_1_THRESHOLD {
        limbs_mod_limb::<DoubleLimb, Limb>(xs, m) == y % m
    } else {
        limbs_eq_limb_mod_limb(xs, y, m)
    }
}