Problem with generic integer nth root

1

So I'm trying to implement integer nth root and I'm having some problems implementing this without unsafe code. For example:

pub fn nth_root<T> (value: T, n: T) -> Option<T>
    where T: ::num::Integer + Into<usize> + Clone {
    let mut x = T::one();
    let mut x_old: T = T::zero();
    let nm1 = n.clone() - T::one();
    let nm1u: usize = nm1.clone().into();
    for _ in 0..100 {
        x_old = x.clone();
        x = (nm1.clone() * x.clone() + value.clone() / ::num::pow(x.clone(), nm1u.clone())) / n.clone();
        if x_old == x {
            return Some(x)
        }
    }
    None
}

Note that I'm using the num crate. Now this for instance does not compile because the trait std::convert::From is not implemented for usize. I tried using this directly by converting to f64, rounding and verifying it backwards, but than there is the issue that std::convert::From<f64> is not implemented for i32and fori64you can't make it tof64`. My question is how should I write this correctly so that it works for all integer values ?

2

I just copied and pasted that code, and it does compile, with only a warning:

warning: value assigned to `x_old` is never read, #[warn(unused_assignments)] on by default

Can you update your example?

3

Can you try [here] (Rust Playground), you probably don't have a main function to call it from?

4

So first I thought it was just going to be that you had a signed vs unsigned mismatch and that switching your a and b variables from i32 to u32, to match the unsignedness of your Into constraint.

But then I realized that actually, Into is not implemented for most integers at all. See
From in std::convert - Rust and note that only u8 has that conversion built in. My understanding is that that is because T -> usize could be lossy for any types greater than 8 bit, if you are running on an 8 bit platform (so that usize is 8 bits). Having that conversion be built in for u8 makes sense since it can't be lossy on any platform architecture that is intended to be supported by rust. That cannot be said for the other types.

Looking at the documentation for pow, in the num crate, it looks like it takes T for the base, but usize for the exponent, whereas you are trying to use a T for the exponent as well, which would require a conversion that could wraparound, given above.

But once you fix those issues, you are still left with some issues that I don't know how you would want to solve.

Notably, with a revised type signature of

pub fn nth_root<T>(value: T, n: usize) -> Option<T>

The compiler is now all sorts of grumpy about this line: (simplified from yours)

 x = (nm1 * x + value / ::num::pow(x, nm1)) / n;

because even though we've made the arguments to pow be correct, the Add, Mul, Div operators are also not defined for usize and a generic Integer.

Note that all of this is because the compiler is trying to protect us from ourselves. In this case, no version of your original type signature (nor mine in the link above) can be remotely safe without a lot of run-time checking for overflows, etc.

So you could go in various directions. You could create a version that output Option (or i128), and explicitly upconvert to larger internal variables than your arguments. You could do a run-time check to make sure that usize is less than T, and be more conservative about your output type, etc, etc. Or if you were intent on maximizing performance, you might skip trying to make a single implementation, be ideal, and instead use specialization to create multiple versions.

2 Likes
5

Hi,
Thanks for the nice reply and these were exactly the issues I was facing. Thanks to someone from the IRC channel he suggested to add to the trait bounds ToPrimitive and FromPrimitive which allows you to convert the T to any primitive type and operate there. I wish there was a more elegant solution, but I did not manage to find any and used this suggestion.