Andrei Alexandrescu wrote:
On 04/12/2010 12:57 PM, "Jérôme M. Berger" wrote:
Andrei Alexandrescu wrote:
On 04/11/2010 09:18 PM, Adam D. Ruppe wrote:
On Sun, Apr 11, 2010 at 10:00:41PM -0400, Steven Schveighoffer wrote:
We are talking about range propagation, a function of the compiler,
not a function of the compiled program. Therefore, slower but more
exact functions should be preferred, since they only affect the
compile time.
I agree with this. While my solution has a certain beauty to it and is
fast, your solution accurately covers all the bases, whereas mine
fails with
min> 1. I say we go with your's.
Agreed. Steve's solution is the best we have for unsigned numbers.
Andrei
Nope, not anymore...
Jerome
Looks great, thanks Jerome!
Now, how about that case in which some or all of the ranges involved
include negative values? A simple approach is to define them in terms of
ranges for unsigned numbers. Here are the cases I identified:
a) If both ranges cross zero, then:
minOR == setmsb(min(
minOR(nomsb(min_a), nomsb(-1), nomsb(min_b), nomsb(max_b)),
minOR(nomsb(min_a), nomsb(max_a), nomsb(min_b), nomsb(-1))))
maxOR == maxOR(0, max_a, 0, max_b)
b) If both ranges are negative, then:
minOR == setmsb(minOR(nomsb(max_a), nomsb(min_a), nomsb(max_b),
nomsb(min_b)))
maxOR == setmsb(maxOR(nomsb(max_a), nomsb(min_a), nomsb(max_b),
nomsb(min_b)))
c) If a crosses zero and b doesn't:
minOR == setmsb(minOR(nomsb(min_a), nomsb(-1), min_b, max_b))
maxOR == maxOR(0, max_a, min_b, max_b)
The primitive nomsb clears off the sign bit in a number, and setmsb sets
it.
Makes sense?
Andrei
A comment: The way DMD currently does range propagation (storing range
as union{long, ulong}) is wrong. Currently when mixed signed+-unsigned
operations happen, it gives very pessimistic results.
The sign bit should be stored separately.
sign value
1 1xxxxx Negative, long.min..-1
1 0xxxxx (Never occurs)
0 0xxxxx 0..long.max
0 1xxxxx long.max+1..ulong.max
I'm not sure if that makes this case a little more, or a little less
complicated. But this defines the problem a bit better.
