Redesign and document the traits/functions related to numbers #4819

auroranockert · 2013-02-06T12:23:56Z

In #4789 discussion was started about redesigning the traits related to numbers and I think the first step is to design and document the traits we think are required and why.

We probably also depend on #4183 and some other bugs for the actual implementation?

(I have an initial sketch/RFC here, based on the work in #4789 etc. https://gist.github.com/JensNockert/4719287)

auroranockert · 2013-02-06T12:34:42Z

Also related to #1284 (Complex Numbers), which should be taken into consideration.

Other types that may not fit in core but should fit into the trait system

Fixed-Point
Quaternions
Polynomials
Interval Arithmetic
Matrixes and Vectors

brendanzab · 2013-02-07T20:50:32Z

Good call on making a new bug. Looking forward to seeing progress on this front - it will be of great use to maths libraries.

auroranockert · 2013-02-11T19:36:55Z

I made a bikeshed, https://github.com/mozilla/rust/wiki/Bikeshed-Numeric-Traits, hoping that it can grow into actual documentation at some point describing the thoughts going into the system. Feel free to add comments, fix bugs &c.

auroranockert · 2013-02-11T19:44:08Z

#4881, #4208, #4788, #1222, #2198, #3980, #4565, #4219, #3281 and #4231 seem like related issues, I just wanted to add them here for reference so I can see if they get magically closed in relation to this bug.

brendanzab · 2013-02-11T22:37:50Z

According to @catamorphism and @nikomatsakis (in this comment in #4183), we currently have a blockage at #4678, pushed back until the 0.7 milestone. We might have to figure out some workarounds for the time being and patch things up later once the issues are resolved.

auroranockert · 2013-02-12T12:08:28Z

Yeah, waiting for 0.7+ seems like a no-go for me too, I think we'll have to start without the operator traits and try to make sure the fix is in as early as possible for 0.7.

This restores the trait that was lost in 216e85f. `Num` will eventually be broken up into a more fine-grained trait hierarchy in the future once a design can be agreed upon. To contribute to the discussion about the future of Rust's numeric traits, please see issue #4819 and the [wiki page](https://github.com/mozilla/rust/wiki/Bikeshed-Numeric-Traits). I have also switched to [implementing NumCast using macros](brendanzab@353ce87). This removes a significant number of lines of code.

This renaming, proposed in the [Numeric Bikeshed](https://github.com/mozilla/rust/wiki/Bikeshed-Numeric-Traits#rename-modulo-into-rem-or-remainder-in-traits-and-docs), will allow us to implement div and and modulo methods that follow the conventional mathematical definitions for negative numbers without altering the definitions of the operators (and confusing systems programmers). Here is a useful answer on StackOverflow that explains the difference between `div`/`mod` and `quot`/`rem` in Haskell: (When is the difference between quotRem and divMod useful?)[http://stackoverflow.com/a/339823/679485]. This is part of the numeric trait reforms tracked in issue #4819.

As part of the numeric trait reform (see issue #4819), I have added the following traits to `core::num` and implemented them for the appropriate types: ~~~rust pub trait Signed: Num + Neg<Self> { fn abs(&self) -> Self; fn signum(&self) -> Self; fn is_positive(&self) -> bool; fn is_negative(&self) -> bool; } pub trait Unsigned: Num {} pub trait Natural: Num + Ord + Quot<Self,Self> + Rem<Self,Self> { fn div(&self, other: Self) -> Self; fn modulo(&self, other: Self) -> Self; fn div_mod(&self, other: Self) -> (Self,Self); fn quot_rem(&self, other: Self) -> (Self,Self); fn gcd(&self, other: Self) -> Self; fn lcm(&self, other: Self) -> Self; fn divisible_by(&self, other: Self) -> bool; fn is_even(&self) -> bool; fn is_odd(&self) -> bool; } ~~~ I have not implemented `Natural` for `BigInt` and `BigUInt` because they're a little over my head. Help with this would be most appreciated.

pnkfelix · 2013-04-24T14:17:37Z

�Was happy to see popcount (aka sideways-add). Any chance we could find a more self-documenting name than clz and ctz for the other two functions in the BitCount trait? (Would leadingzeros and trailingzeros be acceptable?)

auroranockert · 2013-04-24T14:22:30Z

I think you're right, it is a lot more clear with the longer names. I updated the bikeshed.

brendanzab · 2013-04-25T10:40:29Z

I'll implement pop_count, leading_zeros and trailing_zeros on a BitCount trait on my next pull request. Thanks for the suggestion!

brendanzab · 2013-04-25T10:54:17Z

If we're going for 'self-documenting', I wonder if either bit_count or bits_set would be better than pop_count. The description in the LLVM docs says, "The llvm.ctpop family of intrinsics counts the number of bits set in a value."

thestinger · 2013-04-25T14:16:09Z

Population count is self-documenting in my opinion, and it's the domain term for it.

Python has a method called bit_count and it does something completely different (counts the bits needed to represent the number - including zeroes).

brendanzab · 2013-04-25T18:13:58Z

Ahh ok. If it's a domain term that's fine.

As part of the numeric trait reform (see issue #4819), I have added the following traits to `core::num` and implemented them for floating point types: ~~~rust pub trait Round { fn floor(&self) -> Self; fn ceil(&self) -> Self; fn round(&self) -> Self; fn trunc(&self) -> Self; fn fract(&self) -> Self; } pub trait Fractional: Num + Ord + Round + Quot<Self,Self> { fn recip(&self) -> Self; } pub trait Real: Signed + Fractional { // Common Constants fn pi() -> Self; fn two_pi() -> Self; fn frac_pi_2() -> Self; fn frac_pi_3() -> Self; fn frac_pi_4() -> Self; fn frac_pi_6() -> Self; fn frac_pi_8() -> Self; fn frac_1_pi() -> Self; fn frac_2_pi() -> Self; fn frac_2_sqrtpi() -> Self; fn sqrt2() -> Self; fn frac_1_sqrt2() -> Self; fn e() -> Self; fn log2_e() -> Self; fn log10_e() -> Self; fn log_2() -> Self; fn log_10() -> Self; // Exponential functions fn pow(&self, n: Self) -> Self; fn exp(&self) -> Self; fn exp2(&self) -> Self; fn expm1(&self) -> Self; fn ldexp(&self, n: int) -> Self; fn log(&self) -> Self; fn log2(&self) -> Self; fn log10(&self) -> Self; fn log_radix(&self) -> Self; fn ilog_radix(&self) -> int; fn sqrt(&self) -> Self; fn rsqrt(&self) -> Self; fn cbrt(&self) -> Self; // Angular conversions fn to_degrees(&self) -> Self; fn to_radians(&self) -> Self; // Triganomic functions fn hypot(&self, other: Self) -> Self; fn sin(&self) -> Self; fn cos(&self) -> Self; fn tan(&self) -> Self; // Inverse triganomic functions fn asin(&self) -> Self; fn acos(&self) -> Self; fn atan(&self) -> Self; fn atan2(&self, other: Self) -> Self; // Hyperbolic triganomic functions fn sinh(&self) -> Self; fn cosh(&self) -> Self; fn tanh(&self) -> Self; } /// Methods that are harder to implement and not commonly used. pub trait RealExt: Real { // Gamma functions fn lgamma(&self) -> (int, Self); fn tgamma(&self) -> Self; // Bessel functions fn j0(&self) -> Self; fn j1(&self) -> Self; fn jn(&self, n: int) -> Self; fn y0(&self) -> Self; fn y1(&self) -> Self; fn yn(&self, n: int) -> Self; } ~~~ The constants in `Real` could be [associated items](http://smallcultfollowing.com/babysteps/blog/2013/04/03/associated-items-continued/) in the future (see issue #5527). At the moment I have left the constants in `{float|f32|f64}::consts` in case folks need to access these at compile time. There are also instances of `int` in `Real` and `RealExt`. In the future these could be replaced with an associated `INTEGER` type on `Real`. `Natural` has also been renamed to `Integer`. This is because `Natural` normally means 'positive integer' in mathematics. It is therefore strange to implement it on signed integer types. `Integer` is probably a better choice. I have also switched some of the `Integer` methods to take borrowed pointers as arguments. This brings them in line with the `Quot` and `Rem` traits, and is be better for large Integer types like `BigInt` and `BigUint` because they don't need to be copied unnecessarily. There has also been considerable discussion on the mailing list and IRC about the renaming of the `Div` and `Modulo` traits to `Quot` and `Rem`. Depending on the outcome of these discussions they might be renamed again.

brendanzab · 2013-04-25T20:55:23Z

Does rust use the same floating point constants as the C99 standard (see section 5.2.4.2.2, item 14)? I notice that the double values are the same as those defined in core::f64. Unfortunately they aren't included in core::f32 or core::float (although I assume float is the same as f64).

auroranockert · 2013-04-25T22:12:42Z

If the constants are not the same for f32/f64 then that would be a bug. The ones used in C headers are crafted to give correctly rounded values.

brendanzab · 2013-04-25T22:19:28Z

@JensNockert So the various min/max values (including _exp, _10_exp) should be the same for f64/f32?

Casorati · 2013-08-17T15:22:00Z

I would like to discuss some minor issues I see with the Signed trait here. Currently it is defined as

pub trait Signed: Num
                + Neg<Self> {
    fn abs(&self) -> Self;
    fn abs_sub(&self, other: &Self) -> Self;
    fn signum(&self) -> Self;

    fn is_positive(&self) -> bool;
    fn is_negative(&self) -> bool;
}

All of the functions in this trait can also be implemented for 'unsigned' types considering that unsigned actually means non negative to us. Furthermore abs is usually understood to be the L2 norm and is defined for normed vector space and we probably want to define it for complex numbers but skip the rest of this trait. Also the most important function specific to signed types is the additive inverse, which gets implemented as Neg which is part of the Num trait.

I think it would be better to have a Normed trait containing abs and maybe abs_sub, putting signum, is_positive and is_negative into the Num trait and making the Singed trait contain Neg and maybe a copysign function as in C/C++.

huonw · 2013-08-18T10:03:28Z

@Casorati putting signum, is_positive and is_negative on Num would be a step backwards, e.g. what would they do for integer modulo rings, or polynomials?

(I agree about abs though, although it requires a more general signature to be properly useful, it can't be -> Self.)

Casorati · 2013-08-18T14:14:03Z

@huonw The integer types (both the singed and unsigned ones) are already modulo rings so I don't see any problem there. In practice one either chooses to represent them by numbers in a range [0, 2a[ or [-a, a[ and defines the sign to be the sign of the representing element in that range. Polynomials are vector spaces and how often have you seen algorithms which are expected to work for both int32 and polynomials at the same time?

I think complex numbers are much more relevant to this discussion not only because they define a very special vector space but also because the complex type in part of the C99 standard. If we want them to implement the trait Num, then you are right, signum functions must be put elsewhere.

How about this:

Num stays as it is, negation is defined for unsigned types the same way as in C/C++ which also extends well to other modulo rings.
abs and sub_abs are moved to a new trait Normed.
signum, is_positive and is_negative remain in trait Signed (maybe change its name) and the trait gets implemented for unsigned types. Unsigned trait gets removed. Alternatively, once could consider a generic implementation for all types implementing Ord and Zero (like here).

huonw · 2013-08-18T23:24:52Z

The integer types (both the singed and unsigned ones) are already modulo rings so I don't see any problem there

I know, but they are rarely used for their modulo-ring properties; they are just pretending to be ℤ and ℕ (also, strictly speaking, signed overflow is undefined behaviour (in C, not 100% sure about LLVM), not wrap around, so the signed variants aren't necessarily/always modulo rings).

Polynomials are vector spaces and how often have you seen algorithms which are expected to work for both int32 and polynomials at the same time?

This isn't about algorithms for both (although Euclid's algorithm is one example); it's for having to coerce polynomials into a Num trait with properties that don't fit. As you say, complex numbers are a decent example.

negation is defined for unsigned types the same way as in C/C++ which also extends well to other modulo rings.

I'm not sure I understand this, but currently we have Num approximately being "Ring", so negation is necessarily well defined for all types that would implement Num (including uint etc; I don't understand why this is even worth bringing up; changing the semantics of -(1u) would be a very peculiar step, and any possible change would have to make a + (-a) != 0 for some a).

Those changes sound ok to me; but as I said before, we'd need something like

trait Normed<Base> {
    fn abs(&self) -> Base;
    fn abs_sub(&self, other: &Self) -> Self;
}

for Normed to actually be useful as a fully generic trait.

huonw · 2013-08-18T23:38:34Z

(Also, I guess abs_sub doesn't actually apply to Normed; as far as I can tell, it is only defined on (sub-rings of) the reals.)

Casorati · 2013-08-19T11:53:29Z

What do you think about generic implementations like

fn is_positive<T:Zero+Ord>(x: T) -> bool
{
    x > Zero::zero::<T>()
}

fn is_negative<T:Zero+Ord>(x: T) -> bool
{
    x < Zero::zero::<T>()
}

fn sgn<T:Zero+Ord+One+Neg<T>>(x: T) -> T
{
    let zero = Zero::zero::<T>();
    if(x>zero) {One::one::<T>()}
    else if(x<zero) {-One::one::<T>()}
    else {zero}
}

Although it would be nice to have a branchless implementation for sgn whenever possible.

SiegeLord · 2013-08-26T01:02:07Z

std::int::pow seems to be have been left behind in all of this. Should it be made an associated function or a part of a trait?

Somehow this was missed! cc #4819

erickt · 2013-09-16T16:55:13Z

Hey folks. I'm working on a syntax extension that will auto-generate int <-> enum conversion functions. This will replace most of the functionality in std::num::NumCast. Here's a sketch of what I'm working on right now:

pub trait ToPrimitive {
    fn to_int(&self) -> Option<int>;
    #[inline] fn to_i8(&self) -> Option<i8> { self.to_int().and_then(|x| Some(x as i8)) }
    ...
    fn to_uint(&self) -> Option<uint>;
    #[inline] fn to_u8(&self) -> Option<u8> { self.to_uint().and_then(|x| Some(x as u8)) }
    ...
    fn to_float(&self) -> Option<float>;
    #[inline] fn to_f32(&self) -> Option<f32> { self.to_float().and_then(|x| Some(x as f32)) }
    ...
}

pub trait FromPrimitive {
    fn from_int(n: int) -> Option<Self>;
    #[inline] fn from_i8(n: i8) -> Option<Self> { FromPrimitive::from_int(n as int) }
    ...
    fn from_uint(n: uint) -> Option<Self>;
    #[inline] fn from_u8(n: u8) -> Option<Self> { FromPrimitive::from_uint(n as uint) }
    ...
    fn from_float(n: float) -> Option<Self>;
    #[inline] fn from_f32(n: f32) -> Option<Self> { FromPrimitive::from_float(n as float) }
    ...
}

As opposed to NumCast, this will eventually be doing checked casting, which does make the conversion a little slower. However, assuming the src and dst types have the same sign and the dst type is the szme size or larger, we can skip the range check.

Open questions from IRC:

how do we handle float conversions since not every value is representable as a float/f32/f64?
Do we also support .floor_to_int(), .sign_extend_to_int(), .zero_extend_to_int() and etc?
Should we instead have FromCheckedPrimitive and leave FromPrimitive to handle unchecked casts? (I'm against this one)

huonw · 2013-09-17T09:21:42Z

Should we instead have FromCheckedPrimitive and leave FromPrimitive to handle unchecked casts? (I'm against this one)

I'd guess a .from_uint().unwrap() will compile to almost exactly what a .from_uint_unchecked() would do anyway? (At least with optimisations, since from_uint and unwrap would both get inlined and so the branch on Some/None in unwrap would be eliminated and merged with the relevant part of from_uint.)

This PR solves one of the pain points with c-style enums. Simplifies writing a fn to convert from an int/uint to an enum. It does this through a `#[deriving(FromPrimitive)]` syntax extension. Before this is committed though, we need to discuss if `ToPrimitive`/`FromPrimitive` has the right design (cc #4819). I've changed all the `.to_int()` and `from_int()` style functions to return `Option<int>` so we can handle partial functions. For this PR though only enums and `extra::num::bigint::*` take advantage of returning None for unrepresentable values. In the long run it'd be better if `i64.to_i8()` returned `None` if the value was too large, but I'll save this for a future PR. Closes #3868.

alexcrichton · 2014-04-01T23:42:17Z

Closing in favor of #10387. The recent trend has been to reduce the number of traits in the num module, allowing fine-grained mathematical principles to reside in a separate crate, not in libstd.

brendanzab · 2014-04-05T21:00:09Z

Thanks! This has been a great journey. I think we have have all learned a great deal and are finally converging on the best design we can considering the challenges. Hopefully we can avoid the problems that the Haskell98 and Scala libs have faced as our library ecosystem evolves.

auroranockert mentioned this issue Feb 6, 2013

integers shouldn't implement num::Round #4789

Closed

kud1ing mentioned this issue Feb 6, 2013

infinity-related functions shouldn't be generic over Num #4788

Closed

brendanzab mentioned this issue Feb 14, 2013

Problem with self when inheriting generic traits. #4183

Closed

brendanzab mentioned this issue Apr 13, 2013

Restore Num trait and use macros to implement and test NumCast #5869

Merged

brendanzab mentioned this issue Apr 21, 2013

Rename Div operator trait to Quot and Modulo operator trait to Rem #5990

Merged

This was referenced Apr 21, 2013

Proposal: Implement assignment operator overloads #5992

Closed

Trait reform #5527

Closed

Implement Signed, Unsigned and Natural traits #6041

Closed

brendanzab mentioned this issue Apr 24, 2013

Add Fractional, Real, and RealExt traits and update Round trait. Rename Natural trait to Integer. #6048

Merged

brendanzab mentioned this issue Apr 26, 2013

Add traits for primitive numeric types #6071

Closed

This was referenced Sep 8, 2013

std::num cleanups, add Clone and DeepClone constraints to num::Primitive #9051

Closed

Add Orderable bound to num::Primitive #9182

Closed

bors added a commit that referenced this issue Sep 14, 2013

auto merge of #9182 : bjz/rust/master, r=brson

bca015d

Somehow this was missed! cc #4819

erickt mentioned this issue Sep 17, 2013

Add {To,From}Primitive conversion trait, add #[deriving(FromPrimitive)] for enums #9250

Merged

brendanzab mentioned this issue Sep 20, 2013

Rename the NaN and is_NaN methods to lowercase. #9321

Merged

huonw mentioned this issue Sep 23, 2013

Figure out a good convention for normalizing rational numbers #5738

Closed

brendanzab mentioned this issue Nov 9, 2013

Flatten numeric trait hierarchy and allow for user extensibility. #10387

Closed

alexcrichton closed this as completed Apr 1, 2014

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Redesign and document the traits/functions related to numbers #4819

Redesign and document the traits/functions related to numbers #4819

auroranockert commented Feb 6, 2013

auroranockert commented Feb 6, 2013

brendanzab commented Feb 7, 2013

auroranockert commented Feb 11, 2013

auroranockert commented Feb 11, 2013

brendanzab commented Feb 11, 2013

auroranockert commented Feb 12, 2013

pnkfelix commented Apr 24, 2013

auroranockert commented Apr 24, 2013

brendanzab commented Apr 25, 2013

brendanzab commented Apr 25, 2013

thestinger commented Apr 25, 2013

brendanzab commented Apr 25, 2013

brendanzab commented Apr 25, 2013

auroranockert commented Apr 25, 2013

brendanzab commented Apr 25, 2013

Casorati commented Aug 17, 2013

huonw commented Aug 18, 2013

Casorati commented Aug 18, 2013

huonw commented Aug 18, 2013

huonw commented Aug 18, 2013

Casorati commented Aug 19, 2013

SiegeLord commented Aug 26, 2013

erickt commented Sep 16, 2013

huonw commented Sep 17, 2013

alexcrichton commented Apr 1, 2014

brendanzab commented Apr 5, 2014

Redesign and document the traits/functions related to numbers #4819

Redesign and document the traits/functions related to numbers #4819

Comments

auroranockert commented Feb 6, 2013

auroranockert commented Feb 6, 2013

brendanzab commented Feb 7, 2013

auroranockert commented Feb 11, 2013

auroranockert commented Feb 11, 2013

brendanzab commented Feb 11, 2013

auroranockert commented Feb 12, 2013

pnkfelix commented Apr 24, 2013

auroranockert commented Apr 24, 2013

brendanzab commented Apr 25, 2013

brendanzab commented Apr 25, 2013

thestinger commented Apr 25, 2013

brendanzab commented Apr 25, 2013

brendanzab commented Apr 25, 2013

auroranockert commented Apr 25, 2013

brendanzab commented Apr 25, 2013

Casorati commented Aug 17, 2013

huonw commented Aug 18, 2013

Casorati commented Aug 18, 2013

huonw commented Aug 18, 2013

huonw commented Aug 18, 2013

Casorati commented Aug 19, 2013

SiegeLord commented Aug 26, 2013

erickt commented Sep 16, 2013

huonw commented Sep 17, 2013

alexcrichton commented Apr 1, 2014

brendanzab commented Apr 5, 2014