brendanzab / algebra

Abstract algebra for Rust (still very much a WIP!)
Apache License 2.0
60 stars 9 forks source link

Consider using brendanzab/approx for approximate equality traits. #30

Open sebcrozet opened 8 years ago

WaDelma commented 8 years ago

Currently ApproxEq is implemented only for some of primitives in approx: https://github.com/brendanzab/approx/issues/6

brendanzab commented 8 years ago

I'm wondering if we should even have approximate traits... could we just accept that our structures won't match up to the ideal mathematical versions? Seems like most of out impls just use the Approx versions...

sebcrozet commented 8 years ago

Well I am also in favor to dedicate this crate to approximate algebra. In practice, exact computation usually comes with a significant impact in term of performance and memory needs. So in practice, algorithms using exact arithmetic will require an implementation that is very different from those using approximate arithmetic (for performance reasons). In the end, there is no point in keeping exact traits and approximate ones in the same crate since a single implementation will never mix them. Another use of exact algebraic structures is with non-numerical objects, e.g., function spaces. Those can be left to another crate as well.

Also, if we dedicate this crate to approximate algebra, we could remove the ugly Approx suffix from the trait names.

ApproxEq is still a must-have though.

WaDelma commented 8 years ago

Well one problem that approximate stuff is that there is different kinds of innaccuracies:

Under/overflow and structure breaking values can be mitigated with wrappers, but precision cannot.
If we focus on approximate algebra, then there should atleast be some way of telling why there is innaccuracy and maybe even measure it.

And the idea would be to have two separate crates: one for approximate and one for exact and then have them work together?

brendanzab commented 8 years ago

Agreed - there is that annoying question - how do you abstract over unsigned integers, integers, floats, fixed point, bignums, and composites of those... they all have different properties when it comes to precision/approximation :(

sebcrozet commented 8 years ago

@WaDelma

And the idea would be to have two separate crates: one for approximate and one for exact and then have them work together?

The two separate crates don't even have to work together. It makes no sense for an approximate value to be used in an exact context; and conversely, using a exact value in an approximate context would probably yield poor performances in practice (an algorithm using exact arithmetic must be designed specifically to take in account the performance impacts ).

@brendanzab

I think the goal of this crate is just to describe some families of objects. We describe what is a group, a vector space, and expect them to be implemented for type that work well for approximate computations. For a specific algorithm, the choice of the actual type, depending on which precision/approximation properties it has, it left to the user. So we could provide traits that allow the user to check which kind of inaccuracies should be expected from a given generic type. For example:

// Instead of this, we could use traits `Bounded`, `FixedPoint`, etc.
// with methods to retrieve their intrinsic characteristics.
enum InnacuracyCategory<S> {
  Bounded(S, S),
  ContainsInfinite,
  ContainsNaN,
  etc.
}

trait ApproximateValue: ApproxEq {
   fn get_category(&self) -> InnacuracyCategory<Self>;
}

For a given generic type, the user is then free to combine traits describing algebraic properties, with traits describing inaccuracy properties in order to provide a robust implementation of an algorithm.

brendanzab commented 8 years ago

Oh, interesting thinking. I wonder if there would be a way to encode that statically...?