value range propagation for %

[Ellery Newcomer]

Hello.

Today I've been thinking about calculating the range of values for

x % y

it is bounded by -|y| and |y|, but for small ranges for x, it is 
possible to do better. When x is a subrange of y, the result range can 
be computed exactly and in constant time; however when x is not a 
subrange of y, I can't think of an exact algorithm that has a better 
running time than O(yrange).

I'm vaguely certain that for unbounded positive integers, you can't do 
better than linear, consider

x = m!
y in [1, m]

But that certainty would evaporate in the presence of tricks or may not 
apply when y is bounded above by 2^^n.

  Anybody know any tricks?