Polynomial Functions

A Rust library for polynomial operations, including addition, multiplication, evaluation, and Lagrange interpolation for univariate polynomials.

Features

• Addition: Add two polynomials together.
• Multiplication: Multiply two polynomials.
• Evaluation: Evaluate a polynomial at a given value of x.
• Lagrange Interpolation: Perform Lagrange interpolation to find a polynomial that passes through given points.

Usage

Add the following to your Cargo.toml:

[dependencies]
 zkpolynomial = "0.1.0"

Example

Here's an example of how to use the library:

use polynomials::{Monomial, UnivariatePolynomial};

fn main() {
    // Create some monomials
    let m1 = Monomial::new(2, 3.0);
    let m2 = Monomial::new(1, 2.0);
    let m3 = Monomial::new(0, 5.0);

    // Create a polynomial
    let p = UnivariatePolynomial::new(vec![m1, m2, m3]);

    // Evaluate the polynomial at x = 4.0
    let result = p.evaluate(4.0);
    println!("P(4.0) = {}", result);

    // Perform Lagrange interpolation
    let x = vec![1.0, 2.0, 3.0];
    let y = vec![1.0, 4.0, 9.0];
    let interpolated_poly = UnivariatePolynomial::interpolate(x, y);
    println!("Interpolated Polynomial: {:?}", interpolated_poly);
}

Documentation

Monomial

Represents a single term in a polynomial, consisting of an exponent and a coefficient.

Methods

• new(exponent: u32, coefficients: f32) -> Monomial: Creates a new Monomial with the given exponent and coefficient.

• default() -> Monomial: Creates a default Monomial with an exponent of 0 and a coefficient of 0.0.

UnivariatePolynomial

Represents a polynomial, which is a sum of monomials.

Methods

• new(monomials: Vec) -> UnivariatePolynomial: Creates a new UnivariatePolynomial with the given monomials.

• default() -> UnivariatePolynomial: Creates a default

UnivariatePolynomial with no monomials and no degree.

• evaluate(&self, x: f32) -> f32: Evaluates the polynomial at a given value of x.

• degree(&mut self) -> Option: Returns the degree of the polynomial, if known.

• interpolate(x: Vec, y: Vec) -> UnivariatePolynomial: Performs Lagrange interpolation to find a polynomial that passes through the given points.

Trait Implementations

Mul for UnivariatePolynomial

Multiplies two polynomials and returns the result.

impl Mul for UnivariatePolynomial {
    type Output = UnivariatePolynomial;

    fn mul(self, p2: UnivariatePolynomial) -> Self {
        let p1: Vec<Monomial> = self.monomials;
        let p2: Vec<Monomial> = p2.monomials;

        let mut polynomial: Vec<Monomial> = Vec::new();
        for i in 0..p1.len() {
            for j in 0..p2.len() {
                polynomial.push(Monomial {
                    coefficients: p1[i].coefficients * p2[j].coefficients,
                    exponent: p1[i].exponent.wrapping_add(p2[j].exponent),
                });
            }
        }

        // Combine monomials with the same exponent
        for i in 0..polynomial.len() {
            let mut j = i + 1;
            while j < polynomial.len() {
                if polynomial[i].exponent == polynomial[j].exponent {
                    polynomial[i].coefficients += polynomial[j].coefficients;
                    polynomial.remove(j);
                } else {
                    j += 1;
                }
            }
        }
        UnivariatePolynomial {
            monomials: polynomial,
            degree: None,
        }
    }
}

Add for UnivariatePolynomial

Adds two polynomials and returns the result.

impl Add for UnivariatePolynomial {
    type Output = UnivariatePolynomial;

    fn add(self, p2: UnivariatePolynomial) -> Self {
        let p1: Vec<Monomial> = self.monomials;
        let p2: Vec<Monomial> = p2.monomials;
        let mut polynomial: Vec<Monomial> = Vec::new();
        polynomial = [p1, p2].concat();

        // Combine monomials with the same exponent
        for i in 0..polynomial.len() {
            let mut j = i + 1;
            while j < polynomial.len() {
                if polynomial[i].exponent == polynomial[j].exponent {
                    polynomial[i].coefficients += polynomial[j].coefficients;
                    polynomial.remove(j);
                } else {
                    j += 1;
                }
            }
        }
        UnivariatePolynomial {
            monomials: polynomial,
            degree: None,
        }
    }
}

Tests

Evaluate Method

Tests the evaluate method of the UnivariatePolynomial struct.

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_evaluate() {
        let default = UnivariatePolynomial::default();
        let m1 = Monomial::new(2, 3.0);
        let m2 = Monomial::new(1, 2.0);
        let m3 = Monomial::new(0, 5.0);

        let p = UnivariatePolynomial {
            monomials: vec![m1, m2, m3],
            ..default
        };
        let result = p.evaluate(4.0);
        assert_eq!(result, 61.0);
    }
}

Degree Method

Tests the degree method of the UnivariatePolynomial struct.

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_degree() {
        let default = UnivariatePolynomial::default();
        let m1 = Monomial::new(2, 3.0);
        let m2 = Monomial::new(1, 2.0);

        let mut p = UnivariatePolynomial {
            monomials: vec![m1, m2],
            ..default
        };
        let result = p.degree();
        assert_eq!(result, Some(2));
    }
}

Multiplication Method

Tests the multiplication of two

UnivariatePolynomial

s.

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_multiplication() {
        let default = UnivariatePolynomial::default();
        let m1 = Monomial::new(3, 4.0);
        let m2 = Monomial::new(2, 3.0);
        let m5 = Monomial::new(1, 3.0);
        let m3 = Monomial::new(2, 5.0);
        let m4 = Monomial::new(1, 7.0);

        let mut p1 = UnivariatePolynomial {
            monomials: vec![m1, m2, m5],
            ..default
        };
        let mut p2 = UnivariatePolynomial {
            monomials: vec![m3, m4],
            ..default
        };
        let result = p1 * p2;
        assert_eq!(result.monomials[0].coefficients, 20.0);
        assert_eq!(result.monomials[1].coefficients, 43.0);
        assert_eq!(result.monomials[2].coefficients, 36.0);
        assert_eq!(result.monomials[3].coefficients, 21.0);
        assert_eq!(result.monomials[0].exponent, 5);
        assert_eq!(result.monomials[1].exponent, 4);
        assert_eq!(result.monomials[2].exponent, 3);
        assert_eq!(result.monomials[3].exponent, 2);
    }
}

Lagrange Interpolation Method

Tests the Lagrange interpolation method.

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_interpolate() {
        let default = UnivariatePolynomial::default();
        let x = vec![1.0, 2.0, 3.0];
        let y = vec![1.0, 4.0, 9.0];
        let result = UnivariatePolynomial::interpolate(x, y);
        assert_eq!(result.monomials[0].coefficients, 1.0);
        assert_eq!(result.monomials[0].exponent, 2);
    }
}

License

This project is licensed under the MIT License. See the LICENSE file for details.

Contributing

Contributions are welcome! Please open an issue or submit a pull request on GitHub.

Repository

GitHub Repository