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?
