Represent, evaluate and get the degree of a polynomial in rust

This article assumes that you already understand what polynomials are and the different concepts around them like univariate and multivariate polynomials.A univariate ploymonial contains a single variable(say x) and non-negative powers of the polynomial which can then be multiplied by coefficients.

This is a univariate polynomial:

3x² + 2x + 7

X is the single variable, 2, 1, 0 are the non-negative powers, 3, 2 and 7 are coefficients.

Now that we have that cleared up, let’s translate it into code(I’m excited):

Representation

//This assumes there is one coefficient for every power of X
struct UnivariatePoly {  
    coeffs: Vec<u64>,
}

The first step is creating a struct that hold the polynomial. We will be working with a dense representation for simplicity. Ideally, it is better to use prime fields in real world cases, we keeping it at u64, again to keep it as simple as possible.

Degree

The degree of a polynomial translates to the highest power in that equation. Looking at our example from earlier, (3x² + 2x + 7), 2 is the degree of the polynomial because it is the highest power in the equation. Assuming we had the values arranged from the lowest to highest degree order, we would have [7, 2,3], with the index as the power. In case it is not already clear to you, the power of 7 is 0 ( 7x⁰ \= 7). So when getting the degree, we could just get the highest index. in this case, 3 is as index 2, so we use .len() to get the length then to -1 to get the index.

impl UnivariatePoly {
    fn degree(&self) -> usize {
        if self.coeffs.is_empty() {
            return 0;
        }
        // Degree is one less than length for non-zero polynomial
        self.coeffs.len() - 1
    }
}

Evaluate

Now that we got the degree out of the way, let’s evaluate the polynomial. All we need is a point at which we can evaluate the polynomial. There are two ways to code this out, using a for loop or .iter(). We are going to use .iter() for memory safety and tidiness. .iter() loops through our indexes, .enumerate() collects them an .map() perfoms the calculation. we use .sum to get the sum of all the calculations.

fn evaluate(&self, x: f64) -> f64 {
    self.coeffs
        .iter()
        .enumerate()
        .map(|(i, coefficient)| coefficient * x.powf(i as f64))
        .sum()
}

and now the full code:

//This assumes there is one coefficient for every power of X
struct UnivariatePoly {
    coeffs: Vec<u64>,
}

impl UnivariatePoly {
    fn degree(&self) -> usize {
        if self.coeffs.is_empty() {
            return 0;
        }
        // Degree is one less than length for non-zero polynomial
        self.coeffs.len() - 1
    }

    fn evaluate(&self, x: f64) -> f64 {
        self.coeffs
            .iter()
            .enumerate()
            .map(|(i, coefficient)| *coefficient as f64 * x.powf(i as f64))
            .sum()
    }
}

fn main() {
    // Test polynomial 1: f(x) = 3 + 2x + 5x^2
    let poly1 = UnivariatePoly {
        coeffs: vec![3, 2, 5],
    };

    // Test polynomial 2: f(x) = 1 + 0x + 0x^2 + 4x^3
    let poly2 = UnivariatePoly {
        coeffs: vec![1, 0, 0, 4],
    };   

    // Test degree function
    println!("Polynomial 1 degree: {}", poly1.degree()); // Should be 2
    println!("Polynomial 2 degree: {}", poly2.degree()); // Should be 3

    // Test evaluate function
    println!("\nPolynomial 1 evaluation:");
    println!("f(0) = {}", poly1.evaluate(0.0)); // Should be 3
    println!("f(1) = {}", poly1.evaluate(1.0)); // Should be 3 + 2 + 5 = 10
    println!("f(2) = {}", poly1.evaluate(2.0)); // Should be 3 + 2*2 + 5*2^2 = 3 + 4 + 20 = 27

    println!("\nPolynomial 2 evaluation:");
    println!("f(0) = {}", poly2.evaluate(0.0)); // Should be 1
    println!("f(1) = {}", poly2.evaluate(1.0)); // Should be 1 + 0 + 0 + 4 = 5
    println!("f(2) = {}", poly2.evaluate(2.0)); // Should be 1 + 0 + 0 + 4*2^3 = 1 + 32 = 33

}

I hope you learnt something.