## digitalmars.D - value range propagation for %

- Ellery Newcomer (15/15) Nov 27 2010 Hello.
- Matthias Walter (6/9) Nov 27 2010 You might want to state the problem more precisely. What exactly is a
- =?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= (14/26) Nov 27 2010 The full problem may be stated as:
- Ellery Newcomer (6/18) Nov 27 2010 Jerome hit it. Looking for the minimum and maximum (though more precise

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?

Nov 27 2010

On 11/27/2010 12:54 PM, Ellery Newcomer wrote:Hello. Today I've been thinking about calculating the range of values for x % yYou might want to state the problem more precisely. What exactly is a "range of values x % y" ? Do you look at the result for x,y in some sets? Or is either x or y fixed? From your example I would suppose that x shall be fixed and y goes through a range?! Matthias

Nov 27 2010

Matthias Walter wrote:On 11/27/2010 12:54 PM, Ellery Newcomer wrote:Hello. Today I've been thinking about calculating the range of values for x % yYou might want to state the problem more precisely. What exactly is a "range of values x % y" ? Do you look at the result for x,y in some sets? Or is either x or y fixed? From your example I would suppose that=x shall be fixed and y goes through a range?! =20The full problem may be stated as: For all x such that: xl <=3D x <=3D xh and for all y such that: yl <=3D y <=3D yh define: z =3D x % y Now, compute values zl and zh such that: zl <=3D z <=3D zh and there exists x and y such that z =3D=3D zl and there exists x and y such that z =3D=3D zh Jerome --=20 mailto:jeberger free.fr http://jeberger.free.fr Jabber: jeberger jabber.fr

Nov 27 2010

Jerome hit it. Looking for the minimum and maximum (though more precise constraints would be nice). I forgot to say that at the moment, I'm considering x to be fixed because it's (approximately) the most difficult case, but x generally goes through a range. On 11/27/2010 12:30 PM, Matthias Walter wrote:On 11/27/2010 12:54 PM, Ellery Newcomer wrote:Hello. Today I've been thinking about calculating the range of values for x % yYou might want to state the problem more precisely. What exactly is a "range of values x % y" ? Do you look at the result for x,y in some sets? Or is either x or y fixed? From your example I would suppose that x shall be fixed and y goes through a range?! Matthias

Nov 27 2010