Representing difference between unsigned integers

libs
#1

This week, I twice needed to represent a difference between two unsigned numbers. Granted, one was for advent of code, but the other was typical systemsy code for list manipulation in a guts of a complicated data structure (source).

Unless I am missing something, there's no easy way to do this in Rust? The obvious solution is to say that a diff between two u32 is an i32, and then use as casts to do the computation. But this ugly, ignores overflows, and doesn't really work for u128 or usize. Originally, I wanted to suggest adding

impl u32 {
  fn [|overflowing|wrapping|checked]_add_signed(self, other: i32) -> u32
}

family of methods to primitives, but now I have some doubts.

The problem is that the magnitude of the difference between two u32 can be u32::max_value(), so using i32 here is wrong. The right type for the difference would be (bool, u32). This isn't nice to work with (as you'd need to hard-code operations on differences yourself), and doesn't look like a pit of success.

At this point, I am feeling lost: this is clearly a problem and a friction point, but I have no ideas what the solution would look like. Any suggestions?

#2

The same is true for the magnitude of the difference between two i32s. (It can also be u32::max_value().)

3 Likes
#3

Whenever you sum or difference multiple values that are each constrained to a range, you are at risk of overflowing the range. The conventional solution is to cast the values to a larger range and sum or difference in that larger range. Where differences or signed values are involved, the larger range needs to be signed, though if you are only summing unsigned values the larger range can be unsigned.

Of course this causes problems if your initial range is u128 or i128, because that is Rust's largest natively-supported range.

2 Likes
#4

I'm looking forward to eventually being able to do an Integer<LOW, HIGH> type, so that addition and subtraction and multiplication can just return wider types, and thus there's no overflow. Kinda like what's discussed in https://github.com/rust-lang/rfcs/pull/2581

Some other possible options include things like making a u31 type (could do that today in nightly with the same attributes that NonZeroU32 and friends use). The "just use a wider type" solution is pretty good -- that's how LLVM represents u32 * u32 -> u64, for example, so hopefully would optimize well for addition too. Yeah, it doesn't work for [ui]128, but those seem pretty rare anyway...

2 Likes
#5

For what it's worth, I recently began working on an implementation of ranged integers. min_const_generics is fairly limited in this regard, and the full const_generics doesn't get support arithmetic among const parameters. But it should be relatively easy to implement in a library once implemented in the compiler.

One thing of note that I ran into is that the rustc attributes expressing the min and max values currently require literals — expanding this to allow consts would allow for crates like mine to take advantage of optimizations (albeit only on nightly).

The code is available at jhpratt/deranged for the curious.

1 Like
#6

I think any fixed-size solution to this problem will fall down pretty quickly once you try to do multiple arithmetic operations in succession. What is u32::max_value() - (0u32 - u32::max_value())?

2 Likes
#7

i64 is a fixed-size accumulator that can support at least 231 additions and subtractions of u32 and i32 values. I wouldn't call 231 operationa "pretty quickly".

#8

That sounds like madness as soon as you're doing any math in a loop. Or at least, you'll still be facing the exact same overflow problems unless you've got true dependent types or a willingness to 'widen' into BigInts. And even a nicely layered type hierarchy is going to suffer from the "oops, we widened too much and now our performance suffers" and you're right back to writing code where you've got a fixed number of bits constraining you.

1 Like
#9

Sure, it doesn't solve loops, but it certainly makes straight-line code nice. I'd be happy to just have x + 2 < y work without gotchas, even if it doesn't solve every problem ever.

1 Like
#10

What I usually do is:

  • first compare the two numbers and find the larger one (you can always do it since both are unsigned)
  • then subtract the smaller one from the larger one
  • (EDIT) if first >= second, compare it with i32::MAX (which always succeeds when converting to u32); if larger, you have an overflow; if smaller, you're done.
  • if second > first, observe the difference (which is always unsigned) and check if it is larger than the absolute of the minimum signed version. (EDIT) You can always convert -(i32::MIN) into u32 by simply casting -(i32::MIN - 1) to u32, because the unsigned version will always be large enough, and then adding one.
  • (EDIT) if <= -(i32::MIN - 1), convert it into i32 and negate it and you're done (negative numbers in signed is always one larger than the positive numbers)
  • (EDIT) if == -(i32::MIN) just use i32::MIN
  • if > -(i32::MIN) then you simply have an overflow.
3 Likes
#11

2³¹, no, but 31, yes:

fn main() -> Result<(), usize> {
    let mut a = u32::max_value() as i64;
    for i in 0usize.. {
        a = a.checked_add(a).ok_or(i)?;
    }
    Ok(())
}
1 Like
#12

Needed this once more, and ended up hand-coding

use std::ops::{Add, AddAssign, Sub, SubAssign};

#[derive(Copy, Clone)]
pub enum Delta<T> {
    Add(T),
    Sub(T),
}

impl<T: Ord + Sub<Output = T>> Delta<T> {
    pub fn new(old: T, new: T) -> Delta<T> {
        if new > old {
            Delta::Add(new - old)
        } else {
            Delta::Sub(old - new)
        }
    }
}

// This won't be coherent :-(
// impl<T: AddAssign + SubAssign> AddAssign<Delta<T>> for T
impl AddAssign<Delta<usize>> for usize {
    fn add_assign(&mut self, rhs: Delta<usize>) {
        match rhs {
            Delta::Add(amt) => *self += amt,
            Delta::Sub(amt) => *self -= amt,
        }
    }
}
1 Like