number-theory 0.0.22

Fast primality, factorization and elementary number theory for integer types
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

use crate::arithmetic::inlineops::*;
use std::cmp::Ordering;

/*
   Returns index of significant digit
*/

pub(crate) fn sig_pos(x: &[u64]) -> usize {
    if x.last() == Some(&0) {
        return x.iter().rposition(|&x| x != 0).map_or(0, |i| i + 1);
    }
    x.len()
}

/*
    Slice operations
*/

// Compare slices
pub(crate) fn cmp_slice(x: &[u64], y: &[u64]) -> Ordering {
    if x.len() > y.len() {
        return Ordering::Greater;
    }
    if x.len() < y.len() {
        Ordering::Less
    } else {
        Iterator::cmp(x.iter().rev(), y.iter().rev())
    }
}

/*
   Bitwise slice operations
*/

// slice shift-right
pub(crate) fn _shr_slice(x: &mut [u64], shift: u32) -> u64 {
    let mut carry = 0u64;

    for i in x.iter_mut().rev() {
        carry = carry_shr(carry, *i, shift, i);
    }

    carry
}
// slice shift-left
pub(crate) fn shl_slice(x: &mut [u64], shift: u32) -> u64 {
    let mut carry = 0u64;

    for i in x.iter_mut() {
        carry = carry_shl(carry, *i, shift, i);
    }

    carry
}

/*

 Arithmetic slice operations

*/
#[inline]
pub(crate) fn add_slice(x: &mut [u64], y: &[u64]) -> u8 {
    //first number must be larger

    let mut carry = 0u8;

    let (lo, hi) = x.split_at_mut(y.len()); //split to make lo equal in length to y

    for (i, j) in lo.iter_mut().zip(y.iter()) {
        //add equal
        carry = adc(carry, *i, *j, i);
    }

    if carry > 0u8 {
        // if carry is greater than zero, propagate it through the rest of the array until there is no carry left

        for k in hi.iter_mut() {
            //add the carry until there is no carry
            carry = adc(carry, *k, 0u64, k);
            if carry == 0u8 {
                break;
            }
        }
    }
    carry
}

/*
   Subtraction x-y
*/

pub(crate) fn sub_slice(x: &mut [u64], y: &[u64]) -> u8 {
    //first number must be larger

    let mut carry = 0u8;

    let (lo, hi) = x.split_at_mut(y.len()); //split to make equal

    for (i, j) in lo.iter_mut().zip(y.iter()) {
        //add equal
        carry = sbb(carry, *i, *j, i);
    }

    if carry > 0u8 {
        for k in hi.iter_mut() {
            //add the carry until there is no carry
            carry = sbb(carry, *k, 0u64, k);
            if carry == 0u8 {
                break;
            }
        }
    }
    carry
}

pub(crate) fn scale_slice(x: &mut [u64], scale: u64) -> u64 {
    let mut carry = 0u64;

    for i in x.iter_mut() {
        carry = carry_mul(carry, *i, scale, i);
    }
    carry
}

// divides inplace and returns remainder
pub(crate) fn div_slice(x: &mut [u64], divisor: u64) -> u64 {
    let mut carry = 0u64;

    for i in x.iter_mut().rev() {
        carry = carry_div(carry, *i, divisor, i);
    }
    carry
}

// divides inplace and returns remainder
pub(crate) fn mod_slice(x: &[u64], divisor: u64) -> u64 {
    let mut carry = 0u64;

    for i in x.iter().rev() {
        carry = carry_mod(carry, *i, divisor);
    }
    carry
}