dashu-int 0.6.0

Arbitrary-precision integer math library for Rust, balancing ergonomics and efficiency. Provides UBig and IBig (unsigned and signed), with small values inlined on the stack. Efficient arithmetic, modular arithmetic, and number theory (pow, ilog, gcd, gcd_ext); two's-complement bit operations; parsing and formatting in base 2-36; optional serde, rand, num-traits, rkyv, and zeroize.
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

//! Helper functions for multiplication algorithms.

use crate::{
    add,
    arch::word::{SignedWord, Word},
    memory::Memory,
    mul, Sign,
};

/// c += sign * a * b
///
/// Splits a into chunks of chunk_len, using regular multiplication for the remainder if any.
///
/// Returns carry.
pub fn add_signed_mul_split_into_chunks<F>(
    mut c: &mut [Word],
    sign: Sign,
    mut a: &[Word],
    b: &[Word],
    chunk_len: usize,
    memory: &mut Memory,
    f_add_signed_mul_chunk: F,
) -> SignedWord
where
    F: Fn(&mut [Word], Sign, &[Word], &[Word], &mut Memory) -> SignedWord,
{
    debug_assert!(a.len() >= b.len() && c.len() == a.len() + b.len());
    debug_assert!(b.len() <= chunk_len);

    let n = b.len();
    let mut carry_n = 0; // at c[n]
    while a.len() >= chunk_len {
        let (a_lo, a_hi) = a.split_at(chunk_len);
        // Propagate carry_n
        carry_n = add::add_signed_word_in_place(&mut c[n..chunk_len + n], carry_n);
        carry_n += f_add_signed_mul_chunk(&mut c[..chunk_len + n], sign, a_lo, b, memory);
        a = a_hi;
        c = &mut c[chunk_len..];
    }
    // Propagate carry_n
    let mut carry = add::add_signed_word_in_place(&mut c[n..], carry_n);
    if a.len() >= b.len() {
        carry += mul::add_signed_mul(c, sign, a, b, memory);
    } else if !a.is_empty() {
        carry += mul::add_signed_mul(c, sign, b, a, memory);
    }
    carry
}