April 10, 2010 value range propagation for logical OR | ||||
---|---|---|---|---|

| ||||

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. Thanks, Andrei |

April 10, 2010 Re: value range propagation for logical OR | ||||
---|---|---|---|---|

| ||||

Posted in reply to Andrei Alexandrescu | On Sat, 10 Apr 2010 12:01:45 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote: > > 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. > > > Thanks, > > Andrei It seems like it would use the lowest minimum and the highest maximum of the two... that's what I personally would find most natural, given the semantics of bitwise OR, but maybe I'm just way off base. |

April 10, 2010 Re: value range propagation for logical OR | ||||
---|---|---|---|---|

| ||||

Posted in reply to Justin Spahr-Summers | ```
On 04/10/2010 12:22 PM, Justin Spahr-Summers wrote:
> On Sat, 10 Apr 2010 12:01:45 -0500, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> wrote:
>>
>> 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.
>>
>>
>> Thanks,
>>
>> Andrei
>
> It seems like it would use the lowest minimum and the highest maximum of
> the two... that's what I personally would find most natural, given the
> semantics of bitwise OR, but maybe I'm just way off base.
I thought the same, but consider:
a = 4;
b = 3;
Then the maximum value is 7, larger than both.
Andrei
``` |

April 10, 2010 Re: value range propagation for logical OR | ||||
---|---|---|---|---|

| ||||

Posted in reply to Andrei Alexandrescu | On Sat, Apr 10, 2010 at 12:01:45PM -0500, Andrei Alexandrescu wrote: > 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. min_c seems easy enough: min_c = max(min_a, min_b); When you or two values together, the result must be >= both of them, and this does the trick there. max_c is a bit harder. The obvious solution of: max_c = max(max_a, max_b); Fails because of 0b1100 | 0b0011... looking at this example, let's try: max_c = max_a + max_b; It covers that case, but is too big for 0b1111 | 0b1111. This might work: int numbits(number) { return the number of bits required to hold that number; } if ( numbits(max_a + max_b) > max(numbits(max_a), numbits(max_b)) ) max_c = 2 ^^ (max(numbits(max_a), numbits(max_b))) - 1; else max_c = max_a + max_b; The biggest we can possibly get is the sum of the two numbers. But, if it carries over to more bits than either option, we truncate it - OR never gives more bits than the two arguments. So we assume the max is the worst case of all ones or'd with all ones. I think this would work, but might not be the best we can possibly do. It is the best I can think of though. -- Adam D. Ruppe http://arsdnet.net |

April 10, 2010 Re: value range propagation for _bitwise_ OR | ||||
---|---|---|---|---|

| ||||

Posted in reply to Adam D. Ruppe | (By the way I meant _bitwise_ in the title.) On 04/10/2010 12:38 PM, Adam D. Ruppe wrote: > On Sat, Apr 10, 2010 at 12:01:45PM -0500, Andrei Alexandrescu wrote: >> 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. > > min_c seems easy enough: > min_c = max(min_a, min_b); > > When you or two values together, the result must be>= both of them, and this > does the trick there. Yah, that works for unsigned types. For signed types, it's tricky (as tricky as max). > max_c is a bit harder. The obvious solution of: > > max_c = max(max_a, max_b); > > Fails because of 0b1100 | 0b0011... looking at this example, let's try: > > max_c = max_a + max_b; > > It covers that case, but is too big for 0b1111 | 0b1111. Yah, sum is a bound for max, but not the exact max. This is because bitwise OR is like a sum without transport. > This might work: > > int numbits(number) { return the number of bits required to hold that number; } > > if ( numbits(max_a + max_b)> max(numbits(max_a), numbits(max_b)) ) > max_c = 2 ^^ (max(numbits(max_a), numbits(max_b))) - 1; > else > max_c = max_a + max_b; > > > The biggest we can possibly get is the sum of the two numbers. But, if it carries > over to more bits than either option, we truncate it - OR never gives more bits > than the two arguments. So we assume the max is the worst case of all ones or'd > with all ones. > > I think this would work, but might not be the best we can possibly do. It is the > best I can think of though. Even on the branch that doesn't use the sum, that's still just a bound. Consider: a = 8; b = 4; Then max(a|b) is 12, but computed with your method is 15. Andrei |

April 10, 2010 Re: value range propagation for _bitwise_ OR | ||||
---|---|---|---|---|

| ||||

Posted in reply to Andrei Alexandrescu | ```
On 04/10/2010 12:01 PM, Andrei Alexandrescu wrote:
> 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.
>
>
> Thanks,
>
> Andrei
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;
}
The idea is to find the candidate that would fill as many zeros in maxa as possible.
But this is inefficient. I'm wondering whether a simple bitwise manipulation expression could do the trick.
Andrei
``` |

April 10, 2010 Re: value range propagation for logical OR | ||||
---|---|---|---|---|

| ||||

Posted in reply to Andrei Alexandrescu | ```
Andrei Alexandrescu:
> 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.
This is Interval arithmetic. If you are able to find a book about it... (or a library for some programming language that implements it).
Bye,
bearophile
``` |

April 10, 2010 Re: value range propagation for _bitwise_ OR | ||||
---|---|---|---|---|

| ||||

Posted in reply to Andrei Alexandrescu | On Sat, Apr 10, 2010 at 12:39:22PM -0500, Andrei Alexandrescu wrote: > Yah, that works for unsigned types. For signed types, it's tricky (as tricky as max). My feeling is to go ahead and cast to unsigned, then do the calculation. For me at least, when doing bitwise ops, I assume it is unsigned anyway. > Even on the branch that doesn't use the sum, that's still just a bound. Consider: > > a = 8; > b = 4; > > Then max(a|b) is 12, but computed with your method is 15. Yeah, you're right. Bah. Maybe: max_a = max(a, b) | (2 ^^ numbits(min(a, b)) - 1); 8 | 7 == 15; Same deal, still wrong. Maybe we can throw in one more thing: let f(a, b) = the above; max_c = min(f(a, b), a | b); Let me test it... it seems to work. Here's the D program I used to brute-force the test: === import std.intrinsic; // for bsr() uint max(uint a, uint b) { return (a >= b) ? a : b; } uint min(uint a, uint b) { return (a >= b) ? b : a; } uint numbits(uint a) { return a == 0 ? a : bsr(a) + 1; } unittest { assert(numbits(0) == 0); assert(numbits(1) == 1); assert(numbits(2) == 2); assert(numbits(3) == 2); assert(numbits(4) == 3); assert(numbits(5) == 3); } uint f(uint a, uint b) { return max(a, b) | (1 << numbits(min(a, b)) - 1); } uint max_a(uint a, uint b) { return min(f(a, b), a | b); } void main() { for(uint a = 0; a <= 256; a++) for(uint b = 0; b <= 256; b++) assert(a|b <= max_a(a, b)); } ======= I compiled with the unittests, and it closed without tripping any asserts. Eyeballing the output looks right too. -- Adam D. Ruppe http://arsdnet.net |

April 10, 2010 Re: value range propagation for _bitwise_ OR | ||||
---|---|---|---|---|

| ||||

Posted in reply to Andrei Alexandrescu | 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]. -- Rainer Deyke - rainerd@eldwood.com |

April 10, 2010 Re: value range propagation for _bitwise_ OR | ||||
---|---|---|---|---|

| ||||

Posted in reply to Adam D. Ruppe | ```
Adam D. Ruppe:
> My feeling is to go ahead and cast to unsigned, then do the calculation. For me at least, when doing bitwise ops, I assume it is unsigned anyway.
Time ago I have even suggested to disallow bitwise ops when one or both operands are signed...
Bye,
bearophile
``` |

« First ‹ Prev |
---|