View mode: basic / threaded / horizontal-split · Log in · Help
April 10, 2010
Re: value range propagation for _bitwise_ OR
On Sat, Apr 10, 2010 at 02:57:59PM -0400, Adam D. Ruppe wrote:
> Let me test it... it seems to work. Here's the D program I used to brute-force
> the test:

The main() function there isn't an ideal test. Here's a better one:

void main() {
	for(uint max_a = 0; max_a < 100; max_a++)
	for(uint max_b = 0; max_b < 100; max_b++)
	for(uint a = 0; a <= max_a; a++)
	for(uint b = 0; b <= max_b; b++)
		assert(a|b <= max_c(max_a, max_b));
}

// note that I renamed uint max_a to max_c.

We try a whole load of max_a and max_b and test every possible value. It
still runs without throwing.

My original function for min_c works too:

uint min_c(uint a, uint b) {
	return max(a, b);
}

And you can brute force test it all:

void main() {
	for(uint min_a = 0; min_a < 50; min_a++)
	for(uint min_b = 0; min_b < 50; min_b++)
	for(uint max_a = min_a; max_a < 100; max_a++)
	for(uint max_b = min_b; max_b < 100; max_b++)
	for(uint a = min_a; a <= max_a; a++)
	for(uint b = min_b; b <= max_b; b++) {
		assert(a|b <= max_c(max_a, max_b));
		assert(a|b >= min_c(min_a, min_b));
	}
}

This, as you can expect, takes a while to run, but does so without throwing. I'm
pretty confident in the functions now.

-- 
Adam D. Ruppe
http://arsdnet.net
April 10, 2010
Re: value range propagation for logical OR
Hello Andrei,

> Consider:
> 
> byte c = a | b;
> 
> Say you already know min_a, max_a, min_b, and max_b. How do you
> compute min_c and max_c? I thought of it for a bit and it seems quite
> tricky.
> 


x_bit_max == "the largest bit in x_max ^ x_min"
x_oth_max == x_bit_max - 1;

c_max = max(a_bit_max | b_oth_max, b_bit_max | a_oth_max) | (a_max & ~(a_bit_max 
| a_oth_max));




-- 
... <IXOYE><
April 10, 2010
Re: value range propagation for logical OR
Hello BCS,

> Hello Andrei,
> 
>> Consider:
>> 
>> byte c = a | b;
>> 
>> Say you already know min_a, max_a, min_b, and max_b. How do you
>> compute min_c and max_c? I thought of it for a bit and it seems quite
>> tricky.
>> 
> x_bit_max == "the largest bit in x_max ^ x_min"
> x_oth_max == x_bit_max - 1;

// or make that

c_min = (a_max & ~(a_bit_max | a_oth_max);
c_max = max(a_bit_max | b_oth_max, b_bit_max | a_oth_max) | c_min;

> c_max = max(a_bit_max | b_oth_max, b_bit_max | a_oth_max) | (a_max &
> ~(a_bit_max | a_oth_max));
> 

-- 
... <IXOYE><
April 10, 2010
Re: value range propagation for logical OR
Hello BCS,

Scratch all that, I'm clueless. :b

-- 
... <IXOYE><
April 10, 2010
Re: value range propagation for _bitwise_ OR
On Sat, Apr 10, 2010 at 02:55:36PM -0400, bearophile wrote:
> Time ago I have even suggested to disallow bitwise ops when one or both operands are signed...

I understand the position, but I don't advocate it just because I think it would
be annoying and not give much of a benefit.

Consider the following:

for(int a = -10; a < 10; a++)
	writeln(a&1 ? "odd" : "even");

I'd just be annoyed if I had to cast a to uint just to do that. Note that it works
on negative numbers too, so it isn't strictly wrong to do it on signed ints.

I use this when doing stripes on outputted tables and stuff like that.

a % 2 does the same thing, so this specific case isn't a big deal, but I still
tend to type &1 rather than %2 out of habit (this kind of thing used to make a
real speed difference back in the DOS days when I learned it all!)

-- 
Adam D. Ruppe
http://arsdnet.net
April 10, 2010
Re: value range propagation for _bitwise_ OR
Adam D. Ruppe:
> I understand the position, but I don't advocate it just because I think it would
> be annoying and not give much of a benefit.

I have never added a bug report in Bugzilla about this because I think it doesn't give enough benefit.

Thank you for your answer,
bye,
bearophile
April 10, 2010
Re: value range propagation for _bitwise_ OR
On Sat, Apr 10, 2010 at 02:57:59PM -0400, Adam D. Ruppe wrote:
> Let me test it... it seems to work. Here's the D program I used to brute-force
> the test:

Oh no! Eyeballing again showed a problem.. I should have put parens in my asserts:

a | b < f(a,b)   !=  (a|b) < f(a,b)

That breaks it. Back to the drawing board.

-- 
Adam D. Ruppe
http://arsdnet.net
April 10, 2010
Re: value range propagation for _bitwise_ OR
Rainer Deyke wrote:
> On 4/10/2010 11:52, Andrei Alexandrescu wrote:
>> I think this would work:
>>
>> uint maxOR(uint maxa, uint maxb) {
>>     if (maxa < maxb) return maxOR(maxb, maxa);
>>     uint candidate = 0;
>>     foreach (i, bit; byBitDescending(maxa)) {
>>         if (bit) continue;
>>         auto t = candidate | (1 << (31 - i));
>>         if (t <= maxb) candidate = t;
>>     }
>>     return maxa | candidate;
>> }
> 
> This looks wrong.  Your function, if I understand it correctly, flips
> all the bits in 'maxb' (excluding the leading zeros).  If 'maxb' is
> exactly 1 less than a power of 2, then 'candidate' will be 0.  Now
> consider a in [0, 16], b in [0, 15].  Your function will produce 16, but
> the real maximum is 31.
> 
> For maximum accuracy, you have to consider the minima as well as the
> maxima when calculating the new maximum.  With 'a' in [16, 16] and 'b'
> in [16, 16], the new range can only be [16, 16].  With 'a' in [0, 16]
> and 'b' in [0, 16], the correct new range is [0, 31].
> 
> 

It's a very interesting puzzle. There are some pretty complex cases.

Consider (all numbers binary) a in [1010, 1100] and b in [101,101]. The 
maximum value is when a=1011, b=101, so max is 1111.
April 10, 2010
Re: value range propagation for _bitwise_ OR
Adam D. Ruppe:

> Oh no! Eyeballing again showed a problem.. I should have put parens in my asserts:
> a | b < f(a,b)   !=  (a|b) < f(a,b)

Bugs are gold nuggets! Yes, the precedence of bitwise operators is low, it's an error-prone thing, it's a part of C/C++/D that causes frequent bugs in programs written by everybody. I add extra parentheses when I use bitwise operators.

Unfortunately I don't see a simple way to remove this significant source of bugs from the D2 language.

When you switch on full warnings GCC warns you about few possible similar errors, suggesting to add parentheses to remove some ambiguity (for the eyes of the programmers).

This is a small example in C:

#include "stdio.h"
#include "stdlib.h"
int main() {
   int a = atoi("10");
   int b = atoi("20");
   int c = atoi("30");
   printf("%u\n", a|b <= c);
   return 0;
}

If you compile it with GCC (I am using gcc 4.4.1):

...>gcc -Wall test.c -o test
test.c: In function 'main':
test.c:9: warning: suggest parentheses around comparison in operand of '|'

You always use -Wall (and other warnings) when you write C code. So in this case the C language+compiler is able to catch a bug like yours :-)

Bye,
bearophile
April 10, 2010
Re: value range propagation for _bitwise_ OR
On 04/10/2010 01:55 PM, Rainer Deyke wrote:
> On 4/10/2010 11:52, Andrei Alexandrescu wrote:
>> I think this would work:
>>
>> uint maxOR(uint maxa, uint maxb) {
>>      if (maxa<  maxb) return maxOR(maxb, maxa);
>>      uint candidate = 0;
>>      foreach (i, bit; byBitDescending(maxa)) {
>>          if (bit) continue;
>>          auto t = candidate | (1<<  (31 - i));
>>          if (t<= maxb) candidate = t;
>>      }
>>      return maxa | candidate;
>> }
>
> This looks wrong.  Your function, if I understand it correctly, flips
> all the bits in 'maxb' (excluding the leading zeros).

It tries to set all bits in which maxa is zero starting and keeps them 
set if the resulting number is less than maxb.

> If 'maxb' is
> exactly 1 less than a power of 2, then 'candidate' will be 0.  Now
> consider a in [0, 16], b in [0, 15].  Your function will produce 16, but
> the real maximum is 31.

If maxb is 2^^N-1, then it will fill all nonzero bits of maxa.

> For maximum accuracy, you have to consider the minima as well as the
> maxima when calculating the new maximum.  With 'a' in [16, 16] and 'b'
> in [16, 16], the new range can only be [16, 16].  With 'a' in [0, 16]
> and 'b' in [0, 16], the correct new range is [0, 31].

The minimum for unsigned numbers is very simple: min(mina, minb).


Andrei
1 2 3 4 5 6
Top | Discussion index | About this forum | D home