Infinite precision intermediate arithmetic: how much would break?

zackw:

I'm sure there are a whole bunch of problems with this idea

In green-field there's a version of this that works great, actually. I don't think it'd be feasible to more Rust's default numerics to doing it, but for something new (or maybe a new type in Rust?) it actually works wonderfully.

Basically, you have a const-generic Int<MIN, MAX> type that represents values in MIN <= x <= MAX. A literal 4 has type Int<4, 4>. And you use the well-known rules (https://en.wikipedia.org/wiki/Interval_arithmetic#Interval_operators) to expand the range accordingly.

For example, in (a + b) / 2 if a and b are both Int<-10, 100>, then a + b has type Int<-20, 200> and 2 has type Int<2, 2>, and thus (a + b) / 2 also has type Int<-10, 100>. Exactly back to the original type, computing the correct value, and zero need to think about wrapping and such ever. Thus no need for u32::midpoint and friends, plus it automatically works for things we don't have methods for today: a binomial filter like (a + 3 * b + 3 * c + d)/8 also just works.

It's clearly a net win to only have to think about saturate/checked/wrap once at the end of an expression instead of for every step in the middle. And LLVM will already optimize down the size of your intermediates if you don't need them as big based on how it's used in the end: see https://rust.godbolt.org/z/c3fT4GcvE for an example, and note that while the rust code has u128 multiplication and addition, it's optimized down to just u32 operations.

Which means that, no

chrefr:

Widening integer operations to i/u128 makes them way more expensive

isn't the case because they're only widened if you actually need the extra precision.

The actual "downside" here is that you have to specify the types of mutable integers like loop accumulators, and things like += basically stop working inside loops. But arguably that's a good thing -- if you're summing a whole bunch of u8s you probably didn't actually want a u8 result -- and better overall than needing to worry about overflow at every operation.

In languages like C it would be really painful because for (i = 0; i < n; ++i) wouldn't work, but obviously in Rust we spell that for i in 0..n where the Range type would just do the right thing, like it does today.

(Constructing a RangeInclusiveIter from start: Integer<A, B> and last: Integer<C, D> would give you an impl Iterator<Item = Integer<A, D>>, for example. Where you'll notice that B and C are irrelevant, which is nice.)