adic 0.5.1

Arithmetic and rootfinding for p-adic numbers
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

use std::ops::{Add, Mul, Neg, Sub, Rem};
use itertools::{EitherOrBoth, Itertools, repeat_n};
use num::Zero;

use crate::{
    local_num::{LocalInteger, LocalOne, LocalZero},
    mapping::Differentiable,
};
use super::{euclid, Polynomial};


// === Polynomial ===

impl<T> Zero for Polynomial<T>
where T: Clone + LocalZero {
    fn zero() -> Self {
        Self::new(vec![])
    }
    fn is_zero(&self) -> bool {
        self.coefficients().all(T::is_local_zero)
    }
}


impl<T> Add for Polynomial<T>
where T: Clone + LocalZero {
    type Output = Self;

    fn add(self, rhs: Self) -> Self::Output {

        let new_coefficients = self
            .into_coefficients()
            .zip_longest(rhs.into_coefficients())
            .map(|new| match new {
                EitherOrBoth::Both(lhs, rhs ) => lhs + rhs,
                EitherOrBoth::Left(lhs) => lhs,
                EitherOrBoth::Right(rhs) => rhs,
            })
            .collect();

        Polynomial::new(new_coefficients)
    }
}

impl<T> Mul for Polynomial<T>
where T: Clone + LocalZero + LocalOne {
    type Output = Self;

    // Ignore suspicious + in the Mul impl
    #[allow(clippy::suspicious_arithmetic_impl)]
    fn mul(self, rhs: Self) -> Self::Output {

        // NOTE: this could probably be made more efficient but works well as-is
        let mut out = Polynomial::new(vec![]);
        for (deg_lhs, lhs_term) in self.into_coefficients().enumerate() {
            let coefficients = repeat_n(lhs_term.local_zero(), deg_lhs)
                .chain(rhs.clone().into_coefficients())
                .map(|rhs_term| lhs_term.clone() * rhs_term)
                .collect();
            out = out + Polynomial::new(coefficients);
        }

        out
    }
}

impl<T> Neg for Polynomial<T>
where T: Clone + LocalZero + std::ops::Neg<Output=T> {
    type Output = Self;

    fn neg(self) -> Self::Output {
        let coefficients = self.clone()
            .into_coefficients()
            .map(|a| -a)
            .collect();

        Polynomial::new(coefficients)
    }
}

impl<T> Sub for Polynomial<T>
where T: Clone + LocalZero + std::ops::Sub<Output=T> {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self::Output {

        let new_coefficients = self
            .into_coefficients()
            .zip_longest(rhs.into_coefficients())
            .map(|new| match new {
                EitherOrBoth::Both(lhs, rhs ) => lhs - rhs,
                EitherOrBoth::Left(lhs) => lhs,
                EitherOrBoth::Right(rhs) => rhs.local_zero() - rhs,
            })
            .collect();

        Polynomial::new(new_coefficients)
    }
}

impl<T> Rem for Polynomial<T>
where T: Clone + LocalInteger {
    type Output = Self;
    fn rem(self, rhs: Self) -> Self::Output {
        let (_quotient, remainder, mult) = euclid::euclidean_pseudo_div(self, &rhs);
        remainder.map_coefficients(|c| c / mult.clone())
    }
}

impl<T> Differentiable for Polynomial<T>
where T: Clone + LocalZero + LocalOne {
    type Output = Self;
    fn into_derivative(self) -> Self {

        let Some((zero, one)) = self.coefficients().next().map(|c| (c.local_zero(), c.local_one())) else {
            return Self::new(vec![])
        };

        let mut deg = zero;
        let mut new_coefficients = vec![];
        for coeff in self.into_coefficients().skip(1) {
            deg = deg + one.clone();
            new_coefficients.push(deg.clone() * coeff.clone());
        }

        Self::new(new_coefficients)

    }
}