Redesign and document the traits/functions related to numbers

[auroranockert]

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]

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]

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]

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]

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]

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]

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.

[pnkfelix]

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]

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

[brendanzab]

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

[brendanzab]

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]

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]

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

[brendanzab]

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]

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]

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

[auroranockert]

@bjz No, I meant that the values for f32 should be the same as a C float (bit-for-bit) and that for float/f64 should be the same as a C double (bit-for-bit).

[brendanzab]

Ok cheers. I've added those constants to my latest commit.

Also, I've implemented this trait:

pub trait BitCount {
    fn population_count(&self) -> Self;
    fn leading_zeros(&self) -> Self;
    fn trailing_zeros(&self) -> Self;
}

population_count seems to work fine, based on my tests, but I might need you to go over my implementations of leading_zeros and trailing_zeros. I also need some test coverage for them. Help would be most appreciated on that front.

What other low level methods do we need? I notice there are many listed on the bikeshed, but I'm not sure how to proceed. For example, I can implement byte_swap easily using the intrinsic, but to_little_endian and to_big_endian are beyond me.

[dobkeratops]

would it be appropriate to seperate off the transcendental functions (sin,cos,exp etc..) into a trait .. seperating them from the more basic operations that fractional/real number types can implement. (these could be implemented for fixed/float/complex) perhaps even "trait TranscendentalOps : Trig+Exp"; if i've understood correctly dividing into more traits gives you more versaility in specifying what functions a custom type needs to implement; fixed point would be nice to have, they still have their uses.

It seems Haskell lumps all these in "Floating" (derived from "Fractional") but you might want to implement those for Fixed point numbers. (eg some variation of sin,cos using lookup tables..? ).... I dont think these functions are specific to the concept of a floating binary representation as such.

transcendentals could also be implemented for a 'Complex' type, eg r_exp(i_theta)=r(cos theta+i*sin theta) ... etc..

(also I see haskell has no 'fixed point' type, but it does have an integer'ratio' type for fractions. )

If you had a seperate Trig trait, maybe it could sometimes be applied to a special Angle type(with fixedpoint wrap-round,old integer LUT tricks..)..although thats less like the transcendental definition of sin/cos

not sure what a good name is either; are traits better as 'nouns'(like haskell TYPE classes sometimes are)or just a name for a function family (names like print-able etc) ... i see they are often just the name of a key operation.

[brendanzab]

How about:

pub trait Algebraic {
    fn pow(&self, n: Self) -> Self;
    fn sqrt(&self) -> Self;
    fn rsqrt(&self) -> Self;
    fn cbrt(&self) -> Self;
    fn hypot(&self, other: Self) -> Self;
}

pub trait Exponential {
    fn exp(&self) -> Self;
    fn exp2(&self) -> Self;
    fn expm1(&self) -> Self;
    fn log(&self) -> Self;
    fn log2(&self) -> Self;
    fn log10(&self) -> Self;
}

pub trait Triganomic {
    fn sin(&self) -> Self;
    fn cos(&self) -> Self;
    fn tan(&self) -> Self;
    fn asin(&self) -> Self;
    fn acos(&self) -> Self;
    fn atan(&self) -> Self;
    fn atan2(&self, other: Self) -> Self;
    fn sinh(&self) -> Self;
    fn cosh(&self) -> Self;
    fn tanh(&self) -> Self;
}

pub trait Transcendental: Triganomic
                        + Exponential {}

pub trait Real: Signed
              + Fractional
              + Algebraic
              + Transcendental {
    // Not sure where to put these
    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;

    fn to_degrees(&self) -> Self;
    fn to_radians(&self) -> Self;
}

[dobkeratops]

i'd be happy with that

[brendanzab]

Also, what do you think about these methods in the Float trait:

    fn encode(sig: Self, exp: int) -> Self;
    fn decode(&self) -> (Self, int);
    fn significand(&self) -> Self;
    fn exponent(&self) -> int;

This naming follows the lead of Haskell: http://hackage.haskell.org/packages/archive/base/4.6.0.1/doc/html/Prelude.html#t:RealFloat

I had this in a previous pull request, but it bitrotted.

The implementation on f64 might look like:

    /// Constructs a floating-point number from a significand and exponent, equivalent
    /// to: `sig * 2f64.pow(exp)`
    #[inline(always)]
    fn encode(sig: f64, exp: int) -> f64 { ldexp(sig, exp as c_int) }

    /// Splits the numder into its significand and exponent
    #[inline(always)]
    fn decode(&self) -> (f64, int) {
        let mut exp = 0;
        let sig = frexp(*self, &mut exp);
        (sig, exp as int)
    }

    #[inline(always)]
    fn significand(&self) -> f64 {
        let mut _exp = 0;
        frexp(*self, &mut _exp)
    }

    #[inline(always)]
    fn exponent(&self) -> int { ilog_radix(*self) as int }

I'm not sure what the NaN and +/-inf behavior would look like though.

[dobkeratops]

maybe there's a case for throwing the 'hyperbolic trig' into 'Exponential' - although just saying it,it sounds completely wrong - as the implemenattions are related. Not sure.. http://en.wikipedia.org/wiki/Hyperbolic_function eg sinh(x)=(exp(x)-exp(-x))/2 etc.. it would seem convinient to implement them together..

EDIT: the suggestion on IRC to make 'trait Hyperbolic' is also interesting wikipedia talks about hyperbolic & (circular) trignonometic functions seperately. Is it overkill in numberof traits? or could you fill out the hyperbolic ones more comprehensively without polluting the others..

[brendanzab]

@dobkeratops:

pub trait Exponential {
    fn exp(&self) -> Self;
    fn exp2(&self) -> Self;
    fn expm1(&self) -> Self;
    fn log(&self) -> Self;
    fn log2(&self) -> Self;
    fn log10(&self) -> Self;
}

pub trait Triganomic {
    fn sin(&self) -> Self;
    fn cos(&self) -> Self;
    fn tan(&self) -> Self;
    fn asin(&self) -> Self;
    fn acos(&self) -> Self;
    fn atan(&self) -> Self;
    fn atan2(&self, other: Self) -> Self;
}

pub trait Hyperbolic: Exponential {
    fn sinh(&self) -> Self;
    fn cosh(&self) -> Self;
    fn tanh(&self) -> Self;
}

pub trait Transcendental: Triganomic
                        + Hyperbolic {}

?

[huonw]

I would vote for not separating hyperbolic and exp, since {sin,cos,tan}h are trivially implemented with exp.

(Also, I believe that floating is designed to be implemented by anything that has a sensible exp/sin/whatever, not just floating point numbers, including complex numbers, fixed point numbers etc. So I guess the name could be changed, but it's really hard to find something that works well.)

[brendanzab]

@huonw So just have a Transcendental trait? Eg:

pub trait Transcendental {
    fn exp(&self) -> Self;
    fn exp2(&self) -> Self;
    fn expm1(&self) -> Self;
    fn log(&self) -> Self;
    fn log2(&self) -> Self;
    fn log10(&self) -> Self;

    fn sin(&self) -> Self;
    fn cos(&self) -> Self;
    fn tan(&self) -> Self;
    fn asin(&self) -> Self;
    fn acos(&self) -> Self;
    fn atan(&self) -> Self;
    fn atan2(&self, other: Self) -> Self;

    fn sinh(&self) -> Self;
    fn cosh(&self) -> Self;
    fn tanh(&self) -> Self;
}

Yeah having all those separately might be going overboard. I'm interested to hear what @dobkeratops thinks.

[huonw]

Not sure. There is an argument for separating Exp (incl. the hyperbolic fns) and Trig, but I'm really not sure.

I'm trying to think of a mathematical structure that has exp(..) but not sin(..). If there is a non-abstruse example, then I'd vote for separation, but otherwise not. But it doesn't really matter that much.

[brendanzab]

Ok, I'm going with this for now.

pub trait Trigonometric {
    fn sin(&self) -> Self;
    fn cos(&self) -> Self;
    fn tan(&self) -> Self;
    fn asin(&self) -> Self;
    fn acos(&self) -> Self;
    fn atan(&self) -> Self;
    fn atan2(&self, other: Self) -> Self;
}

pub trait Exponential {
    fn exp(&self) -> Self;
    fn exp2(&self) -> Self;
    fn expm1(&self) -> Self;
    fn log(&self) -> Self;
    fn log2(&self) -> Self;
    fn log10(&self) -> Self;

    fn sinh(&self) -> Self;
    fn cosh(&self) -> Self;
    fn tanh(&self) -> Self;
}

pub trait Transcendental: Trigonometric
                        + Exponential {}

@dobkeratops says he has use-cases for separating Trig and Exp.

By the way, I was using the term 'Triganomic', but I am informed it is actually 'Trigonometric' :) http://en.wikipedia.org/wiki/Trigonometric_functions

[dobkeratops]

perhaps 2 is a nice compromise. Trig.. and Exp.. I suggested something like this originally because i can see many situations where you just want one or the other; the beauty of traits seems to be a generic-function writer can be more specific about what a type does & doesn't need to implement. I'm no expert in guessing what the majority of users will think though :) An example of Trig only would be a specific angle type, e.g. it might wrap-round. Also i'm thinking of what happens when people implement things, if they only have 'Exp' implemented , and thats all they need, then great. Might seem like these are all 'solved problems' etc but what about SIMD(implementing vectorized versions, and simd includes variously sized fixed-point ability), or half-float... such libraries may not wait to claim they support everything.

[brendanzab]

@dobkeratops Aye. If you're aiming for performance, you don't want to give your users the wrong impression, based on what's implemented.

[huonw]

Yeah, OK, I like the separation.

I would prefer shorter trait names: Trig, Exp certainly, and maybe Real for Transcendental (this is suboptimal though).

[brendanzab]

Trig, Exp, Hyp and Real?

[brendanzab]

What about Algebraic? Thad on IRC nominates Bacon.

[dobkeratops]

agreeing on names, the hardest part :) just want to mention SIMD vectorized fixed point sine/cosine in decompression as possible use case for trig on a custom type without exp http://en.wikipedia.org/wiki/Discrete_cosine_transform

[brendanzab]

Personally I prefer the longer names because they are more flexible in the long term. Saves having to umm and ahhr about what to name a trait if it can't be shortened (if core::num was ever extended). But I'm not going to be a zealot about it. I agree with removing Transcendental and just putting them on Real

[dobkeratops]

point taken about long,unambiguous names. Throwing some more ideas in here, what might happen with Dimensional types, if they are possible in the language(?) an interesting point is the Transcendental functions dont work on dimensional values - so you might have a floating point number that should not support trig,exp.. might be messy with a class heirachy but i'm sure the trait system could get further expressing this sort of thing (does that affect if it makes sense to put them on Real..)

[brendanzab]

I would LOVE dimension types – as in units of measure in F# land. I always think back to that Mars probe that crashed because they were using different units. It would have to be compile time though. I don't know how we'd implement it using the current tools at our disposal. :(

Also, Mod and Range types like in Ada: http://stackoverflow.com/questions/16160717

[dobkeratops]

implementing dimensional types as is possible in C++ might be waiting for generic functions taking int parameters i think? - even then you might get some value expressing a Dimensioned versus Non-Dimensioned number, or a hard-coded set of them(speed,length,time etc..)

[brendanzab]

Yeah unfortunately we can't do compile time function evaluation or numeric parameters with generic functions/types.

[brendanzab]

Would anybody be able to give feedback on: https://github.com/mozilla/rust/issues/4819#issuecomment-17148065 ?

[dobkeratops]

@bjz, reading the haskell docs for reference, those functions look useful, the names are cleaned up, makes perfect sense in a "float" trait to me which could be implemented for f32,f64, (half..) I guess.

[dobkeratops]

would you consider putting lerp,invlerp in the core maths library.. fn lerp<T:Num,F:Real>(a:T,b:T,f:F)->T{a+(b-a)f} fn invlerp<T,F>(a:T,b:T,f:T)->F{(f-a)/(b-a)} invlerp(a,b,lerp(a,b,f))==f lerp(y0,y1,invlerp(x0,x1,x))== ((x-x0)(y1-y0))/(x1-x0)+y0... some like a different function that does all that,not sure what you''d call it,'lerpBetween' perhaps (perhaps thats 3 potential functions for a 'Lerp' trait)

also how would those look at the minute.. the intention above is T could be any numeric type, but F has to be some sort of fraction.. and where would it make sense for them to go in the traits graph

[pnkfelix]

@bjz I was surprised by the signatures you chose for encode, decode, significand; in particular, by the use of Self for the significand component of the Float trait:

    fn encode(sig: Self, exp: int) -> Self;
    fn decode(&self) -> (Self, int);
    fn significand(&self) -> Self;
    fn exponent(&self) -> int;

I would have guessed that some integer type (potentially a bignum) would be more appropriate there. Of course you do not want to commit to a particular integer type ahead of time, so I assume that the use of Self is a work-around for that.

Am I correct in inferring that this is just a work-around, and if we had associated types, then you would probably instead use a signature something like:

trait Float {
    ...
    type Significand;
    fn encode(sig: self::Significand, exp: int) -> Self;
    fn decode(&self) -> (self::Significand, int);
    fn significand(&self) -> self::Significand;
    fn exponent(&self) -> int;
}

? (I'm making up the syntax above; I think I accidentally left out a case for self in my syntax for associated items proposal.)

(I realize that a reasonable Float impl should be able to represent its significand fairly cheaply as a value of Self type, so this is largely an academic question, but still, better to have the type signatures feed the more precise types to us, no?)

[brendanzab]

@pnkfelix Thanks! Yes, Haskell uses an Integer for that (which I think is a bignum). As you can see in my example implementation, I was using cmath functions for that. But I'm now guessing I'm not actually getting the significand there? How would I do that?

[huonw]

@bjz and I were discussing implementing inverse hyperbolic functions on IRC since they are basically just some logs, but decided against implementing them as part of Exponential right now, since this would require a Algebraic constraint on Exponential (for the sqrt).

(Posting it here just in case someone has suggestions or preferences about this.)

[dobkeratops]

having heard that you're supposed to implement all the functions in a trait, at this point i'd vote for splitting Trig,Exp,Hyperbolic- the latter could then be more comprehensive - and I can see frequency of use being as i've ordered it there.. plenty of cases where people just need Trig; plenty of cases where people just need Exp. Far fewer users will want Hyperbolic. The hyperbolic implementations would also bring in 'sqrt' ideally it seems, and i favour splitting things in ways that reduce dependancies. It seems the only overhead is for users finding the names but these are really logical groupings,e.g. closely corresponding to how they're described on wikipedia even. I generally like the idea that with more traits, you're more granular in specifying what someone needs to implement for their use cases.

[auroranockert]

I vote for splitting them since implementing the hyperbolic functions via exp is non-trivial, you cannot just use the formulas from Wikipedia and expect sane results in floating-point. In addition I fully agree with @dobkeratops reasoning.

[huonw]

I hadn't even though about floating point. That + the sqrt thing overrules my previous objections (for me at least).

[dobkeratops]

Would a 'sincos' function make sense aswell in Trig,given you have tuples so its really easy to get multiple return values sincos(a:T)->T,T. frequently used together, and optimizations often exist for implementation

[auroranockert]

@dobkeratops (i) Yes, it could make sense depending on implementation. In the worst case it is as fast as two calls, which isn't bad. (ii) OpenGL has those, so I could see people using them. Not really sure how OpenGL implements them, but I assume they just clamp the full-range floats you pass in.

[auroranockert]

@pnkfelix I am not sure when you would want another type than self for the significand, could you give a (possibly academic) example of when it could be useful?

Also, what would the significand be interpreted as if it was a bigint? Would it be interpreted as it's value / 2^(significant bits)? How would one duplicate ldexp/frexp with encode/decode using that signature?

It might be that I am just slightly conservative and prefer the C signatures though.