Implementing the Euclidean Algorithm for Euclidean Domains in Rust.
In this story we are going to implement an algorithm that determines the greatest common divisor of two polynomials. Remember, polynomials over a field F (for instance the real numbers), can be given the structure of a commutative ring F[x] by the usual definition of multiplication and addition (more on this here). This structure can be easily implemented in Rust as has been done here.
A very interesting aspect of polynomials appeared to us when looking at ways how to determine the greatest common divisor of two polynomials (see here). The algorithm turned out to be very similar to the traditional one on the ring of integers Z and we were able to find an abstraction, i.e. Euclidean domain, that covers both F[x] and Z and allows the GCD to work as “usually”. All this can be read in more detail here.
We start by declaring a trait that intends to represent an Euclidean domain:
use std::ops::{Add, Mul, Neg, Sub};
pub trait EuclideanDomain<U>
where
Self: Clone
+ Add<Self, Output = Self>
+ Mul<Self…
