• 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

Ellery Newcomer <ellery-newcomer utulsa.edu> writes:

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?

Matthias Walter <xammy xammy.homelinux.net> writes:

On 11/27/2010 12:54 PM, Ellery Newcomer wrote:
 Hello.

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

 x % y

You 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

=?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= <jeberger free.fr> writes:

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 % y

 You 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?!
=20

	The 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

Ellery Newcomer <ellery-newcomer utulsa.edu> writes:

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 % y

 You 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