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

| ||||

Posted in reply to Andrei Alexandrescu | On Sat, Apr 10, 2010 at 04:05:06PM -0500, Andrei Alexandrescu wrote: > The minimum for unsigned numbers is very simple: min(mina, minb). mina = 1 minb = 0 min(1, 0) == 0 But, 1|0 == 1 max(mina, minb) looks to work though. Consider that ORing can only set bits - it can never take a one and spit out a zero. Therefore, x|y >= x && x|y >= y, which only works on the max(mina, minb) function. -- Adam D. Ruppe http://arsdnet.net |

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

| ||||

Posted in reply to Adam D. Ruppe | ```
On 04/10/2010 04:21 PM, Adam D. Ruppe wrote:
> On Sat, Apr 10, 2010 at 04:05:06PM -0500, Andrei Alexandrescu wrote:
>> The minimum for unsigned numbers is very simple: min(mina, minb).
>
> mina = 1
> minb = 0
>
> min(1, 0) == 0
>
> But, 1|0 == 1
>
> max(mina, minb) looks to work though. Consider that ORing can only set bits -
> it can never take a one and spit out a zero. Therefore, x|y>= x&& x|y>= y,
> which only works on the max(mina, minb) function.
Sorry, I meant max of the two minima.
Andrei
``` |

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

| ||||

Posted in reply to Andrei Alexandrescu Attachments: - signature.asc (OpenPGP digital signature)
| Andrei Alexandrescu wrote: > 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. > In other words: maxa | ((1 << highbit (maxb))-1) where: int highbit (uint n) { auto result = 0; if (n & 0xFFFF0000) { result += 16; n = n >> 16; } if (n & 0xFF00) { result += 8; n = n >> 8; } if (n & 0xF0) { result += 4; n = n >> 4; } if (n & 0xC) { result += 2; n = n >> 2; } if (n & 0x2) { result += 1; n = n >> 1; } if (n & 0x1) { result += 1; } return result; } Jerome -- mailto:jeberger@free.fr http://jeberger.free.fr Jabber: jeberger@jabber.fr |

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

| ||||

Posted in reply to Jérôme M. Berger | ```
On 04/10/2010 04:50 PM, "Jérôme M. Berger" wrote:
> Andrei Alexandrescu wrote:
>> 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.
>>
> In other words: maxa | ((1<< highbit (maxb))-1) where:
>
> int highbit (uint n) {
> auto result = 0;
> if (n& 0xFFFF0000) {
> result += 16;
> n = n>> 16;
> }
> if (n& 0xFF00) {
> result += 8;
> n = n>> 8;
> }
> if (n& 0xF0) {
> result += 4;
> n = n>> 4;
> }
> if (n& 0xC) {
> result += 2;
> n = n>> 2;
> }
> if (n& 0x2) {
> result += 1;
> n = n>> 1;
> }
> if (n& 0x1) {
> result += 1;
> }
> return result;
> }
>
> Jerome
Interesting. I don't get how your version is equivalent to mine, and I don't get how it actually works, but it seems to. Could you please explain?
The program below compiles, runs, and prints
total=100000000; equal=3850865 (3.85087%)
Here it is:
import std.contracts, std.stdio;
uint maxOR(uint maxa, uint maxb) {
return maxa | ((1 << highbit (maxb))-1);
}
uint highbit(uint n) {
auto result = 0;
if (n & 0xFFFF0000) {
result += 16;
n = n >> 16;
}
if (n & 0xFF00) {
result += 8;
n = n >> 8;
}
if (n & 0xF0) {
result += 4;
n = n >> 4;
}
if (n & 0xC) {
result += 2;
n = n >> 2;
}
if (n & 0x2) {
result += 1;
n = n >> 1;
}
if (n & 0x1) {
result += 1;
}
return result;
}
void main() {
ulong total, equal;
uint N = 10000;
foreach (a; 0 .. N) {
foreach (b; 0 .. N) {
auto c = maxOR(a, b);
enforce((a|b) <= c);
if ((a|b) == c) equal++;
total++;
}
}
writeln("total=", total, "; equal=", equal,
" (", equal * 100. / total, "%)");
}
However, your method is not the tightest; seems like mine is tighter. When I replaced maxOR with this:
uint maxOR2(uint maxa, uint maxb) {
if (maxa < maxb) return maxOR(maxb, maxa);
uint candidate = 0;
uint mask = 1u << 31;
for (uint i = 0; i < 32; ++i, mask >>= 1) {
if (maxa & mask) continue;
auto t = candidate | (1 << (31 - i));
if (t <= maxb) candidate = t;
}
return maxa | candidate;
}
I got:
total=100000000; equal=9822516 (9.82252%)
Besides, I verified that my method returns numbers <= yours.
Andrei
``` |

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

| ||||

Posted in reply to Andrei Alexandrescu | On 04/10/2010 05:33 PM, Andrei Alexandrescu wrote: [snip] One more interesting detail. I simplified the routine to: uint maxOR(uint maxa, uint maxb) { uint candidate = 0; uint mask = 1u << 31; for (; mask; mask >>= 1) { if (maxa & mask) continue; auto t = candidate | mask; if (t <= maxb) candidate = t; } return maxa | candidate; } Among other things I remove the test whether maxa >= maxb at the beginning of the function. I now obtain: total=100000000; equal=14585400 (14.5854%) so this function is better than all others so far. But I don't understand why it beats this one: uint maxOR(uint maxa, uint maxb) { if (maxa < maxb) return maxOR(maxb, maxa); // added uint candidate = 0; uint mask = 1u << 31; for (; mask; mask >>= 1) { if (maxa & mask) continue; auto t = candidate | mask; if (t <= maxb) candidate = t; } return maxa | candidate; } Andrei |

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

| ||||

Posted in reply to Andrei Alexandrescu | ```
On 04/10/2010 05:43 PM, Andrei Alexandrescu wrote:
> On 04/10/2010 05:33 PM, Andrei Alexandrescu wrote:
> [snip]
>
> One more interesting detail.
Never mind that. I mistakenly used maxOR instead of maxOR2.
To summarize: best result is
total=100000000; equal=14585400 (14.5854%)
with the function:
uint maxOR(uint maxa, uint maxb) {
uint candidate = 0;
uint mask = 1u << 31;
for (; mask; mask >>= 1) {
if (maxa & mask) continue;
auto t = candidate | mask;
if (t <= maxb) candidate = t;
}
return maxa | candidate;
}
Inserting a test and a recursive call at the top keeps the result but actually slows down execution a bit.
Andrei
``` |

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

| ||||

On Sat, Apr 10, 2010 at 04:02:05PM -0400, Adam D. Ruppe wrote: > That breaks it. Back to the drawing board. I *might* have it, but I'm not 100% confident in my test program. Here's my implementation: ==== import std.intrinsic; 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); } uint max_c(uint a, uint b) { uint mn = min(a, b); uint mx = max(a, b); if(mn == 0) return mx; // if there is a bit we can reuse, it grants us everything before it too uint reusable = mn & mx; if(reusable) return (mx | ((1 << numbits(reusable)) - 1)) | mn; else return mx | mn; } uint min_c(uint min_a, uint min_b) { return max(min_a, min_b); } ===== I can't believe I spent all day on this... -- Adam D. Ruppe http://arsdnet.net |

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

| ||||

On Sat, Apr 10, 2010 at 07:38:07PM -0400, Adam D. Ruppe wrote: > I *might* have it, but I'm not 100% confident in my test program. I think my test program is telling me something: a non-zero min_c subtracts from max_c. If I take my brute-force empirically calculated max_c and compare it to what my max_c function returns, it doesn't always match if the minimums change. This might be a bug; it is unintuitive that it would do this, but it actually makes sense. Consider if min == max, you only have one value to work with. let max_a = 4, min_a = 0; max_b = 4 You can get 7 out of it, since 3 < 4, so it is a possible number and: 100 | 011 == 7 But, if min_b == 4, the only possible value for b is 4. And: 100 | 100 == 4. Increasing min_b does indeed decrease the max you can get. Nice fact, but I've spent too much time on this already, so I'll call it done with this: My max_c included some unnecessary code: my reusable mask obsoletes all of my special case code! So, we can bring the program down to three lines: import std.intrinsic; uint numbits(uint a) { return a == 0 ? a : (bsr(a) + 1); } uint max_c(uint a, uint b) { return a | ((1 << numbits(a&b)) - 1) | b; } It passes my test, though since I bugged it up the first time, I might have done it again. -- Adam D. Ruppe http://arsdnet.net |

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

| ||||

Posted in reply to Adam D. Ruppe | ```
On 04/10/2010 06:58 PM, Adam D. Ruppe wrote:
> On Sat, Apr 10, 2010 at 07:38:07PM -0400, Adam D. Ruppe wrote:
>> I *might* have it, but I'm not 100% confident in my test program.
>
> I think my test program is telling me something: a non-zero min_c subtracts from
> max_c. If I take my brute-force empirically calculated max_c and compare it to
> what my max_c function returns, it doesn't always match if the minimums change.
>
> This might be a bug; it is unintuitive that it would do this, but it actually
> makes sense. Consider if min == max, you only have one value to work with.
>
> let max_a = 4, min_a = 0;
>
> max_b = 4
>
> You can get 7 out of it, since 3< 4, so it is a possible number and: 100 | 011 == 7
>
> But, if min_b == 4, the only possible value for b is 4. And: 100 | 100 == 4.
>
> Increasing min_b does indeed decrease the max you can get.
>
>
> Nice fact, but I've spent too much time on this already, so I'll call it done with
> this:
>
> My max_c included some unnecessary code: my reusable mask obsoletes all of
> my special case code! So, we can bring the program down to three lines:
>
> import std.intrinsic;
> uint numbits(uint a) { return a == 0 ? a : (bsr(a) + 1); }
> uint max_c(uint a, uint b) { return a | ((1<< numbits(a&b)) - 1) | b; }
>
> It passes my test, though since I bugged it up the first time, I might have done
> it again.
What results does it yield with my main() test harness?
Andrei
``` |

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

| ||||

Posted in reply to Andrei Alexandrescu | On Sat, Apr 10, 2010 at 08:42:54PM -0500, Andrei Alexandrescu wrote: > What results does it yield with my main() test harness? total=100000000; equal=14585400 (14.5854%) I think that's a perfect result. Here's why: the equality comparison checks two specific values, (a, b), but the maxOr functions return the max for the interval ([0, a], [0, b]). It wouldn't always be equal, since there are other values in there that can reach the max. For example, a = 4, b = 4. 100|100 == 100, but that range also include 4|3, 100 | 011 == 111, which is the max. Your maxOR function gives the same percentage, for probably the same reason. Though, mine runs ~7x faster on my box. -- Adam D. Ruppe http://arsdnet.net |