rust-num / num-traits

Numeric traits for generic mathematics in Rust
Apache License 2.0
732 stars 135 forks source link

Add a trait for perfect power checking #233

Open cmpute opened 2 years ago

cmpute commented 2 years ago

I propose to add the following trait to support perfect power checking (especially perfect square checking)

pub trait ExactRoots : Roots + Pow<u32, Output = Self> {
    fn nth_root_exact(&self, n: u32) -> Option<Self> {
        let r = self.nth_root(n);
        if &r.pow(n) == self { Some(r) } else { None }
    }
    fn sqrt_exact(&self) -> Option<Self> { self.nth_root_exact(2) }
    fn cbrt_exact(&self) -> Option<Self> { self.nth_root_exact(3) }
    fn is_nth_power(&self, n: u32) -> bool { self.nth_root_exact(n).is_some() }
    fn is_square(&self) -> bool { self.sqrt_exact().is_some() }
    fn is_cubic(&self) -> bool { self.cbrt_exact().is_some() }
}

Fast perfect square checking can be implemented for primitive types (and also possibly big integers) using modular arithmetics. These functions can be useful in number theory related calculations.