polynomials/
lib.rs

1#![no_std]
2use core::cmp::PartialEq;
3use core::convert::From;
4use core::ops::Neg;
5use core::ops::{Add, AddAssign};
6use core::ops::{Div, DivAssign};
7use core::ops::{Index, IndexMut};
8use core::ops::{Mul, MulAssign};
9use core::ops::{Sub, SubAssign};
10use core::slice::SliceIndex;
11use serde::{Serialize, Deserialize};
12
13#[cfg_attr(test, macro_use)]
14extern crate alloc;
15use alloc::vec::{IntoIter, Vec};
16
17/// A [`Polynomial`] is just a vector of coefficients. Each coefficient corresponds to a power of
18/// `x` in increasing order. For example, the following polynomial is equal to 4x^2 + 3x - 9.
19///
20/// ```
21/// # #[macro_use] extern crate polynomials;
22/// # fn main() {
23/// // Construct polynomial 4x^2 + 3x - 9
24/// let mut a = poly![-9, 3, 4];
25/// assert_eq!(a[0], -9);
26/// assert_eq!(a[1], 3);
27/// assert_eq!(a[2], 4);
28/// # }
29/// ```
30#[derive(Debug, Clone, Serialize, Deserialize)]
31pub struct Polynomial<T>(Vec<T>);
32
33impl<T> Polynomial<T> {
34    /// Create a new, empty, instance of a polynomial.
35    pub fn new() -> Polynomial<T> {
36        Polynomial(Vec::<T>::new())
37    }
38
39    /// Adds a new coefficient to the [`Polynomial`], in the next highest order position.
40    ///
41    /// ```
42    /// # #[macro_use] extern crate polynomials;
43    /// # fn main() {
44    /// let mut a = poly![-8, 2, 4];
45    /// a.push(7);
46    /// assert_eq!(a, poly![-8, 2, 4, 7]);
47    /// # }
48    /// ```
49    pub fn push(&mut self, value: T) {
50        self.0.push(value);
51    }
52
53    /// Removes the highest order coefficient from the [`Polynomial`].
54    ///
55    /// ```
56    /// # #[macro_use] extern crate polynomials;
57    /// # fn main() {
58    /// let mut a = poly![-8, 2, 4];
59    /// assert_eq!(a.pop().unwrap(), 4);
60    /// assert_eq!(a, poly![-8, 2]);
61    /// # }
62    /// ```
63    pub fn pop(&mut self) -> Option<T> {
64        self.0.pop()
65    }
66
67    /// Calculates the degree of a [`Polynomial`].
68    ///
69    /// The following polynomial is of degree 2: (4x^2 + 2x - 8)
70    ///
71    /// ```
72    /// # #[macro_use] extern crate polynomials;
73    /// # fn main() {
74    /// let a = poly![-8, 2, 4];
75    /// assert_eq!(a.degree(), 2);
76    /// # }
77    /// ```
78    pub fn degree(&self) -> usize
79    where
80        T: Sub<T, Output = T> + Eq + Copy,
81    {
82        let mut deg = self.0.len();
83        for _ in 0..self.0.len() {
84            deg -= 1;
85
86            // Generic test if non-zero
87            if self[deg] != self[deg] - self[deg] {
88                break;
89            }
90        }
91        deg
92    }
93
94    /// Evaluate a [`Polynomial`] for some value `x`.
95    ///
96    /// The following example evaluates the polynomial (4x^2 + 2x - 8) for x = 3.
97    ///
98    /// ```
99    /// # #[macro_use] extern crate polynomials;
100    /// # fn main() {
101    /// let a = poly![-8, 2, 4];
102    /// assert_eq!(a.eval(3).unwrap(), 34);
103    /// # }
104    /// ```
105    pub fn eval<X>(&self, x: X) -> Option<T>
106    where
107        T: AddAssign + Copy,
108        X: MulAssign + Mul<T, Output = T> + Copy,
109    {
110        if self.0.len() == 0 {
111            None
112        } else {
113            let mut p = x; // running power of `x`
114            let mut res = self[0];
115            for i in 1..self.0.len() {
116                res += p * self[i];
117                p *= x;
118            }
119            Some(res)
120        }
121    }
122
123    pub fn iter(&self) -> impl Iterator<Item = &T> {
124        self.0.iter()
125    }
126
127    pub fn into_iter(self) -> impl IntoIterator<Item = T, IntoIter = IntoIter<T>> {
128        self.0.into_iter()
129    }
130}
131
132impl<T> From<Vec<T>> for Polynomial<T> {
133    fn from(v: Vec<T>) -> Self {
134        Polynomial(v)
135    }
136}
137
138impl<T> Into<Vec<T>> for Polynomial<T> {
139    fn into(self) -> Vec<T> {
140        self.0
141    }
142}
143
144impl<T, I: SliceIndex<[T]>> Index<I> for Polynomial<T> {
145    type Output = I::Output;
146
147    fn index(&self, index: I) -> &Self::Output {
148        &self.0[index]
149    }
150}
151
152impl<T, I: SliceIndex<[T]>> IndexMut<I> for Polynomial<T> {
153    fn index_mut(&mut self, index: I) -> &mut Self::Output {
154        &mut self.0[index]
155    }
156}
157
158/// Add two [`Polynomial`]s.
159///
160/// The following example adds two polynomials:
161/// (4x^2 + 2x - 8) + (x + 1) = (4x^2 + 3x - 7)
162///
163/// ```
164/// # #[macro_use] extern crate polynomials;
165/// # fn main() {
166/// let a = poly![-8, 2, 4];
167/// let b = poly![1, 1];
168/// assert_eq!(a + b, poly![-7, 3, 4]);
169/// # }
170/// ```
171impl<T: Add<Output = T>> Add for Polynomial<T>
172where
173    T: Add + Copy + Clone,
174{
175    type Output = Self;
176
177    fn add(mut self, other: Self) -> Self::Output {
178        self += other;
179        self
180    }
181}
182
183impl<T> AddAssign for Polynomial<T>
184where
185    T: Add<Output = T> + Copy,
186{
187    fn add_assign(&mut self, rhs: Self) {
188        let min_len = if self.0.len() < rhs.0.len() {
189            self.0.len()
190        } else {
191            rhs.0.len()
192        };
193        if self.0.len() == min_len {
194            for i in min_len..rhs.0.len() {
195                self.push(rhs[i]);
196            }
197        }
198        for i in 0..min_len {
199            self[i] = self[i] + rhs[i];
200        }
201    }
202}
203
204/// Subtract two [`Polynomial`]s.
205///
206/// The following example subtracts two polynomials:
207/// (4x^2 + 2x - 8) - (x + 1) = (4x^2 + x - 9)
208///
209/// ```
210/// # #[macro_use] extern crate polynomials;
211/// # fn main() {
212/// let a = poly![-8, 2, 4];
213/// let b = poly![1, 1];
214/// assert_eq!(a - b, poly![-9, 1, 4]);
215/// # }
216/// ```
217impl<T: Sub<Output = T>> Sub for Polynomial<T>
218where
219    T: Sub + Neg<Output = T> + Copy + Clone,
220{
221    type Output = Self;
222
223    fn sub(self, other: Self) -> Self::Output {
224        let mut diff = self.clone();
225        diff -= other;
226        diff
227    }
228}
229
230impl<T> SubAssign for Polynomial<T>
231where
232    T: Sub<Output = T> + Neg<Output = T> + Copy,
233{
234    fn sub_assign(&mut self, rhs: Self) {
235        let min_len = if self.0.len() < rhs.0.len() {
236            self.0.len()
237        } else {
238            rhs.0.len()
239        };
240        if self.0.len() == min_len {
241            for i in min_len..rhs.0.len() {
242                self.push(-rhs[i]);
243            }
244        }
245        for i in 0..min_len {
246            self[i] = self[i] - rhs[i];
247        }
248    }
249}
250
251/// Multiply two [`Polynomial`]s.
252///
253/// The following example multiplies two polynomials:
254/// (4x^2 + 2x - 8) * (x + 1) = (4x^3 + 6x^2 - 6x - 8)
255///
256/// ```
257/// # #[macro_use] extern crate polynomials;
258/// # fn main() {
259/// let a = poly![-8, 2, 4];
260/// let b = poly![1, 1];
261/// assert_eq!(a * b, poly![-8, -6, 6, 4]);
262/// # }
263/// ```
264impl<T> Mul<T> for Polynomial<T>
265where
266    T: MulAssign + Copy,
267{
268    type Output = Self;
269
270    fn mul(self, rhs: T) -> Self::Output {
271        let mut prod = self.clone();
272        prod *= rhs;
273        prod
274    }
275}
276
277impl<T> MulAssign<T> for Polynomial<T>
278where
279    T: MulAssign + Copy,
280{
281    fn mul_assign(&mut self, rhs: T) {
282        for i in 0..self.0.len() {
283            self[i] *= rhs;
284        }
285    }
286}
287
288/// Multiply a [`Polynomial`] by some value.
289///
290/// The following example multiplies a polynomial (4x^2 + 2x - 8) by 2:
291///
292/// ```
293/// # #[macro_use] extern crate polynomials;
294/// # fn main() {
295/// let p = poly![-8, 2, 4] * 2;
296/// assert_eq!(p, poly![-16, 4, 8]);
297/// # }
298/// ```
299impl<T> Mul for Polynomial<T>
300where
301    T: Mul<Output = T> + AddAssign + Sub<Output = T>,
302    T: Copy + Clone,
303{
304    type Output = Self;
305
306    fn mul(self, rhs: Self) -> Self::Output {
307        let mut new = self.clone();
308        new *= rhs;
309        new
310    }
311}
312
313impl<T> MulAssign for Polynomial<T>
314where
315    T: Mul<Output = T> + AddAssign + Sub<Output = T>,
316    T: Copy + Clone,
317{
318    fn mul_assign(&mut self, rhs: Self) {
319        let orig = self.clone();
320
321        // One of the vectors must be non-empty
322        if self.0.len() > 0 || rhs.0.len() > 0 {
323            // Since core::num does not provide the `Zero()` trait
324            // this hack lets us calculate zero from any generic
325            let zero = if self.0.len() > 0 {
326                self[0] - self[0]
327            } else {
328                rhs[0] - rhs[0]
329            };
330
331            // Clear `self`
332            for i in 0..self.0.len() {
333                self.0[i] = zero;
334            }
335
336            // Resize vector with size M + N - 1
337            self.0.resize(self.0.len() + rhs.0.len() - 1, zero);
338
339            // Calculate product
340            for i in 0..orig.0.len() {
341                for j in 0..rhs.0.len() {
342                    self[i + j] += orig[i] * rhs[j];
343                }
344            }
345        }
346    }
347}
348
349/// Divide a [`Polynomial`] by some value.
350///
351/// The following example divides a polynomial (4x^2 + 2x - 8) by 2:
352///
353/// ```
354/// # #[macro_use] extern crate polynomials;
355/// # fn main() {
356/// let p = poly![-8, 2, 4] / 2;
357/// assert_eq!(p, poly![-4, 1, 2]);
358/// # }
359/// ```
360impl<T> Div<T> for Polynomial<T>
361where
362    T: DivAssign + Copy,
363{
364    type Output = Self;
365
366    fn div(self, rhs: T) -> Self::Output {
367        let mut prod = self.clone();
368        prod /= rhs;
369        prod
370    }
371}
372
373impl<T> DivAssign<T> for Polynomial<T>
374where
375    T: DivAssign + Copy,
376{
377    fn div_assign(&mut self, rhs: T) {
378        for i in 0..self.0.len() {
379            self[i] /= rhs;
380        }
381    }
382}
383
384impl<T> PartialEq for Polynomial<T>
385where
386    T: Sub<T, Output = T> + Eq + Copy,
387{
388    fn eq(&self, other: &Self) -> bool {
389        let degree = self.degree();
390        if degree != other.degree() {
391            return false;
392        }
393        for i in 0..=degree {
394            if self[i] != other[i] {
395                return false;
396            }
397        }
398        true
399    }
400}
401impl<T> Eq for Polynomial<T> where T: Sub<T, Output = T> + Eq + Copy {}
402
403/// Creates a [`Polynomial`] from a list of coefficients in ascending order.
404///
405/// This is a wrapper around the `vec!` macro, to instantiate a polynomial from
406/// a vector of coefficients.
407///
408/// `poly!` allows `Polynomial`s to be defined with the same syntax as array expressions.
409/// There are two forms of this macro:
410///
411/// - Create a [`Polynomial`] containing a given list of coefficients:
412///
413/// ```
414/// # #[macro_use] extern crate polynomials;
415/// # fn main() {
416/// let p = poly![1, 2, 3]; // 3x^2 + 2x + 1
417/// assert_eq!(p[0], 1);
418/// assert_eq!(p[1], 2);
419/// assert_eq!(p[2], 3);
420/// # }
421/// ```
422///
423/// - Create a [`Polynomial`] from a given coefficient and size:
424///
425/// ```
426/// # #[macro_use] extern crate polynomials;
427/// # fn main() {
428/// let p = poly![1; 3]; // x^2 + x + 1
429/// assert_eq!(p, poly![1, 1, 1]);
430/// # }
431/// ```
432#[macro_export]
433macro_rules! poly {
434    ($($args:tt)*) => (
435         $crate::Polynomial::from(vec![$($args)*])
436     );
437}
438
439#[cfg(test)]
440mod tests {
441    #[test]
442    fn degree() {
443        assert_eq!(poly![8, 6, 2, 3].degree(), 3);
444        assert_eq!(poly![8, 6, 2, 3].degree(), 3);
445        assert_eq!(poly![0, 0, 6, 2, 3].degree(), 4);
446        assert_eq!(poly![0, 0].degree(), 0);
447        assert_eq!(poly![0, 99].degree(), 1);
448        assert_eq!(poly![99, 0].degree(), 0);
449    }
450
451    #[test]
452    fn eval() {
453        assert_eq!(poly![1, 1, 1, 1].eval(1).unwrap(), 4);
454        assert_eq!(poly![-2, -2, -2, -2].eval(1).unwrap(), -8);
455        assert_eq!(poly![100, 0, 0, 0].eval(9).unwrap(), 100);
456        assert_eq!(poly![0, 1, 0, 0].eval(9).unwrap(), 9);
457        assert_eq!(poly![0, 0, -1, 0].eval(9).unwrap(), -81);
458        assert_eq!(poly![0, -9, 0, 40].eval(2).unwrap(), 302);
459    }
460
461    #[test]
462    fn iter() {
463        assert_eq!(poly![0, -9, 0, 40].iter().sum::<isize>(), 31);
464    }
465
466    #[test]
467    fn add() {
468        let a = poly![-200, 6, 2, 3, 53, 0, 0]; // Higher order 0s should be ignored
469        let b = poly![-1, -6, -7, 0, 1000];
470        let c = poly![-201, 0, -5, 3, 1053];
471        assert_eq!(a.clone() + b.clone(), c);
472        assert_eq!(b + a, c);
473    }
474
475    #[test]
476    fn add_assign() {
477        let mut a = poly![-200, 6, 2, 3, 53, 0, 0]; // Higher order 0s should be ignored
478        let b = poly![-1, -6, -7, 0, 1000];
479        let c = poly![-201, 0, -5, 3, 1053];
480        a += b;
481        assert_eq!(a, c);
482
483        let mut a = poly![1]; // Low degree should be expanded
484        let b = poly![0, 1];
485        let c = poly![1, 1];
486        a += b;
487        assert_eq!(a, c);
488    }
489
490    #[test]
491    fn sub() {
492        let a = poly![-200, 6, 2, 3, 53, 0, 0]; // Higher order 0s should be ignored
493        let b = poly![-1, -6, -7, 0, 1000];
494        let c = poly![-199, 12, 9, 3, -947];
495        let d = poly![199, -12, -9, -3, 947];
496        assert_eq!(a.clone() - b.clone(), c);
497        assert_eq!(b - a, d);
498    }
499
500    #[test]
501    fn sub_assign() {
502        let mut a = poly![-200, 6, 2, 3, 53, 0, 0]; // Higher order 0s should be ignored
503        let b = poly![-1, -6, -7, 0, 1000];
504        let c = poly![-199, 12, 9, 3, -947];
505        a -= b;
506        assert_eq!(a, c);
507
508        let mut a = poly![1]; // Low degree should be expanded
509        let b = poly![0, 1];
510        let c = poly![1, -1];
511        a -= b;
512        assert_eq!(a, c);
513    }
514
515    #[test]
516    fn mul() {
517        let a = poly![1, 0, 0]; // Higher order 0s should be ignored
518        let b = poly![0];
519        let c = poly![0];
520        assert_eq!(a * b, c);
521
522        let a = poly![-7];
523        let b = poly![4];
524        let c = poly![-28];
525        assert_eq!(a * b, c);
526
527        let a = poly![0, 1];
528        let b = poly![4];
529        let c = poly![0, 4];
530        assert_eq!(a * b, c);
531
532        let a = poly![0, -1];
533        let b = poly![0, 1];
534        let c = poly![0, 0, -1];
535        assert_eq!(a * b, c);
536    }
537
538    #[test]
539    fn mul_assign() {
540        let mut a = poly![1, 0, 0]; // Higher order 0s should be ignored
541        let b = poly![0];
542        let c = poly![0];
543        a *= b;
544        assert_eq!(a, c);
545
546        let mut a = poly![-7];
547        let b = poly![4];
548        let c = poly![-28];
549        a *= b;
550        assert_eq!(a, c);
551
552        let mut a = poly![0, 1];
553        let b = poly![4];
554        let c = poly![0, 4];
555        a *= b;
556        assert_eq!(a, c);
557
558        let mut a = poly![0, -1];
559        let b = poly![0, 1];
560        let c = poly![0, 0, -1];
561        a *= b;
562        assert_eq!(a, c);
563    }
564
565    #[test]
566    fn mul_by_value() {
567        let a = poly![1, 2, 3];
568        let b = poly![2, 4, 6];
569        assert_eq!(a * 2, b);
570
571        let mut a = poly![1, 2, 3];
572        let b = poly![2, 4, 6];
573        a *= 2;
574        assert_eq!(a, b);
575    }
576
577    #[test]
578    fn div_by_value() {
579        let a = poly![2, 4, 6];
580        let b = poly![1, 2, 3];
581        assert_eq!(a / 2, b);
582
583        let mut a = poly![2, 4, 6];
584        let b = poly![1, 2, 3];
585        a /= 2;
586        assert_eq!(a, b);
587    }
588
589    #[test]
590    fn equality() {
591        let a = poly![1, 0];
592        let b = poly![-1, 0];
593        assert!(a != b);
594    }
595}
polynomials/lib.rs

polynomials/
lib.rs
