Implement more number theory functions about num-integer HOT 9 OPEN

From @hauleth on July 1, 2016 12:0

It would be great!

from num-integer.

From @koverstreet on July 5, 2016 21:49

I'd like to see these implemented as generics over ring/field traits. Especially with specialization coming soon (or has it landed?), this is really the right way to go.

from num-integer.

From @ejmahler on July 6, 2016 5:3

Could you give a really quick example, to illustrate what you're picturing?

from num-integer.

From @koverstreet on July 6, 2016 5:11

Along the lines of a numeric tower (read up on Haskell's if you're curious) - except, I have no intention of trying to do a full numeric tower because no one seems to be able to get that right.

All I'm thinking for now is - define traits for Group, Ring, Field, etc. so we have a place to stick generic algorithms. I tend to think we shouldn't even have the various traits inherit from each other, at least for now - BigUint can always inherit from each of Group/Ring/whatever.

Basically keep it as simple as possible for now - nothing more than a place to stick things that should work on anything that's a group/ring/field.

gcd(), lcm()... perhaps a few others should then become generic functions on whatever the appropriate trait is, with specializations where it matters for performance.

from num-integer.

From @hauleth on July 7, 2016 22:44

I think that having additional structures defined using typenum would feel more "natural".

from num-integer.

From @ejmahler on July 17, 2016 12:50

I understand the high-level picture of what you're looking for, @koverstreet . A set of composable traits that can be included and maybe specialized for each type.

So starting small for now with jsut a "ring" trait that implements all sorts of modular arithmetic functions on this -- what's the correct way to implement this? I wouldn't call myself a rust expert yet so I need some guidance.

The following is what my mind jumps to, but this obviously doesn't compile because you can't implement a trait in terms of another trait -- you need a concrete type. But if we implement this trait for all the primitive types explicitly, that defeats the point of composition of these traits, doesn't it?

pub trait Ring {
    fn pow_mod(&self, exponent: &Self, modulo: &Self) -> Self;
}

impl Ring for Integer {
    fn pow_mod(&self, exponent: &Self, modulo: &Self) -> Self {
             //...
        }
}

We could implement these as standalone template functions:
pub fn pow_mod<T: Integer + Copy>(.......

But again that kind of defeats the point. So how should this be done?

from num-integer.

From @vks on March 17, 2017 17:16

I would like to implement some related number theory functions: modular exponentiation, extended euclid's algorithm, modular multiplicative inverse.

I implemented all of these some time ago here.

from num-integer.

Personally, I think it would be fine to do these without the more ambitious trait categories, but I'm also open to that if someone wants to try it.

from num-integer.

FWIW, I created num-modular and num-prime crates for the same purpose. They accept generic parameters and they're decently optimized.

Note that the implementation for num_bigint::BigUint is very naive, because advanced implementations need num_bigint to expose some of the inner APIs.

from num-integer.