<commit_before>use std::ops::Shl;
use traits::{One, Zero};

use big_digit::{self, BigDigit, DoubleBigDigit, SignedDoubleBigDigit};
use biguint::BigUint;

struct MontyReducer {
    n0inv: BigDigit,
}

// k0 = -m**-1 mod 2**BITS. Algorithm from: <NAME>. "On Newton–Raphson
// Iteration for Multiplicative Inverses Modulo Prime Powers".
fn inv_mod_alt(b: BigDigit) -> BigDigit {
    assert_ne!(b & 1, 0);

    let mut k0 = 2 - b as SignedDoubleBigDigit;
    let mut t = (b - 1) as SignedDoubleBigDigit;
    let mut i = 1;
    while i < big_digit::BITS {
        t = t.wrapping_mul(t);
        k0 = k0.wrapping_mul(t + 1);

        i <<= 1;
    }
    -k0 as BigDigit
}

impl MontyReducer {
    fn new(n: &BigUint) -> Self {
        let n0inv = inv_mod_alt(n.data[0]);
        MontyReducer { n0inv }
    }
}

/// Computes z mod m = x * y * 2 ** (-n*_W) mod m<commit_msg>Don't use field shorthands for older rustc<commit_after>use std::ops::Shl;
use traits::{One, Zero};

use big_digit::{self, BigDigit, DoubleBigDigit, SignedDoubleBigDigit};
use biguint::BigUint;

struct MontyReducer {
    n0inv: BigDigit,
}

// k0 = -m**-1 mod 2**BITS. Algorithm from: <NAME>. "On Newton–Raphson
// Iteration for Multiplicative Inverses Modulo Prime Powers".
fn inv_mod_alt(b: BigDigit) -> BigDigit {
    assert_ne!(b & 1, 0);

    let mut k0 = 2 - b as SignedDoubleBigDigit;
    let mut t = (b - 1) as SignedDoubleBigDigit;
    let mut i = 1;
    while i < big_digit::BITS {
        t = t.wrapping_mul(t);
        k0 = k0.wrapping_mul(t + 1);

        i <<= 1;
    }
    -k0 as BigDigit
}

impl MontyReducer {
    fn new(n: &BigUint) -> Self {
        let n0inv = inv_mod_alt(n.data[0]);
        MontyReducer { n0inv: n0inv }
    }
}

/// Computes z mod m = x * y * 2 ** (-n*_W) mod m
{'fraction_non_alphanumeric': 0.14156285390713477, 'fraction_numerical': 0.022083805209513023, 'mean_word_length': 2.7436440677966103, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4459186', 'n_tokens_mistral': 732, 'n_tokens_neox': 701, 'n_words': 188}