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

| ||||

Posted in reply to Adam D. Ruppe | On 04/10/2010 08:58 PM, Adam D. Ruppe wrote: > 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. Yah, it's clear that we're not looking anywhere near 100%. I'm a bit sad we don't have an adequate baseline, but the fact that two distinct methods obtained the same result is encouraging. > 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. Then you haven't wasted your day! On to the next task: compute minOR and maxOR for _signed_ values. It turns out minOR its also nontrivial... When we're done, we can pass the functions to Walter so he can integrate them within his compiler. Right now the compiler uses a wrong algorithm. Andrei |

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

| ||||

Posted in reply to bearophile | I have filed a "report": http://d.puremagic.com/issues/show_bug.cgi?id=4077 Bye, bearophile |

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

| ||||

Posted in reply to bearophile | ```
On 04/10/2010 09:55 PM, bearophile wrote:
> I have filed a "report":
> http://d.puremagic.com/issues/show_bug.cgi?id=4077
Perfect, thanks. Your decision to contribute with reports is very appreciated.
Andrei
``` |

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

| ||||

Posted in reply to Andrei Alexandrescu | On Sat, Apr 10, 2010 at 09:21:07PM -0500, Andrei Alexandrescu wrote: > Yah, it's clear that we're not looking anywhere near 100%. I'm a bit sad we don't have an adequate baseline, but the fact that two distinct methods obtained the same result is encouraging. My brute-force program was buggy, but I think I fixed it. Here's the main(): ======== uint min_a = 0; uint min_b = 0; for(uint max_a = min_a; max_a <= 256; max_a++) for(uint max_b = min_b; max_b <= 256; max_b++) { uint real_max = 0; 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), format("%b | %b !<= %b (from %b %b)", a, b, max_c(max_a, max_b), max_a, max_b)); assert((a|b) >= min_c(min_a, min_b)); if((a | b) > real_max) real_max = (a|b); } assert(max_c(max_a, max_b) == real_max, format("[%b, %b]. expected: %d, got %d (min == %d)", max_a, max_b, max_c(max_a, max_b), real_max, min_c(min_a, min_b))); } writeln("success"); ======= With so many nested loops, it is slow as dirt, but what it does is try every value in the given range and record the maximum number encountered. If it doesn't match at any step, it throws. But, it works for me. I spent a chunk of the day eyeballing the output too to ensure it is right (and to figure out the pattern that led to the final function). Now, the thing is if you change min_a or min_b, it breaks the real_max; like I said in the other message, if min == max, for example, you get the case where 4|4 isn't the max, since 4|3 isn't available. I'm not sure how to fix that, but I am pretty convinced that to get the perfect solution, the max_c function needs to know min_a and min_b too. Still, this solution works very well in the min_a = min_b = 0 case, so it is at least a decent bound. > On to the next task: compute minOR and maxOR for _signed_ values. It turns out minOR its also nontrivial... Nontrivial is an understatement. I started asking if it can even be done without assuming a size.. I do think you can, by assuming the sizes are equal, whatever they are, but it still is not easy. I still like the idea of just casting it. How often would it cause problems in real code anyway? The only starting point I have is: Of either max_a or max_b is negative, the result of the OR is going to be negative, since that sign bit is one, and we can't change a one to a zero on any OR operation. So, the max value will be positive iff both values are possibly positive. But taking that one statement to working code is too hard for my blood. > When we're done, we can pass the functions to Walter so he can integrate them within his compiler. Right now the compiler uses a wrong algorithm. Indeed. We're getting there, but still a ways to go. -- Adam D. Ruppe http://arsdnet.net |

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

| ||||

Posted in reply to Adam D. Ruppe | Adam D. Ruppe wrote: > I am pretty convinced that to get the > perfect solution, the max_c function needs to know min_a and min_b too. Absolutely! :) I had just started writing an e-mail about it. Andrei Alexandrescu wrote: >> On to the next task: compute minOR and maxOR for _signed_ values. It >> turns out minOR its also nontrivial... How about computing minOR for unsigned values first? ;) The proposed solution of max(min_a, min_b) is correct only for a couple of corner cases. Ali |

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

| ||||

Posted in reply to Andrei Alexandrescu Attachments: - signature.asc (OpenPGP digital signature)
| Andrei Alexandrescu wrote: > 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? > It's not equivalent to yours, because it was a bit late and I was tired. Moreover it doesn't work: it should be: maxa | ((1 << (highbit (maxb)+1))-1) Which still isn't as tight as yours but at least works :) Between 0 and 64, it is optimal for 92% cases whereas yours is optimal for over 98% cases. > 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, "%)"); > } > Note that this is incomplete. Besides, it is very easy to get 100% accuracy with this test: just define maxOR to be maxA|maxB :) I used the following C++ code for my tests: int main (int, char**) { int count = 0; int countTight = 0; for (uint32_t minA = 0; minA < 64; ++minA) for (uint32_t maxA = minA; maxA < 64; ++maxA) for (uint32_t minB = 0; minB < 64; ++minB) for (uint32_t maxB = minB; maxB < 64; ++maxB) { bool reached = false; uint32_t max = maxOr (minA, minB, maxA, maxB); for (uint32_t a = minA; a <= maxA; ++a) for (uint32_t b = minB; b <= maxB; ++b) { if ((a|b) > max) { printf ("minA=%x\n" "maxA=%x\n" "minB=%x\n" "maxB=%x\n" "a=%x\n" "b=%x\n" "a|b=%x\n" "maxOr=%x\n", minA, maxA, minB, maxB, a, b, a|b, max); exit (1); } if ((a|b) == max) reached = true; } if (reached) ++countTight; ++count; } printf ("Total: %d\n", count); printf ("Tight: %d (%g%%)\n", countTight, countTight * 100. / count); printf ("Loose: %d (%g%%)\n", (count - countTight), (count - countTight) * 100. / count); return 0; } OTOH, my solution was slightly faster (4.98s to your 5.34s) Jerome -- mailto:jeberger@free.fr http://jeberger.free.fr Jabber: jeberger@jabber.fr |

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

| ||||

Posted in reply to Don | ```
Am 10.04.2010, 23:17 Uhr, schrieb Don <nospam@nospam.com>:
> 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.
How about this?
import std.stdio, std.conv, std.intrinsic;
void main(string[] args)
{
int total = 0, match = 0, from = to!(int)(args[1]), to = to!(int)(args[2]);
uint res, resBF;
for(int i = from; i < to; ++i)
{
for(int j = i; j < to; ++j)
{
for(int k = from; k < to; ++k)
{
for(int m = k; m < to; ++m)
{
++total;
res = maxOr(i, j, k, m);
resBF = maxOrBF(i, j, k, m);
if(res == resBF) ++match;
//else writefln("mismatch: minA %s, maxA %s, minB %s, maxB %s, maxOr %s, maxOrBF %s", i, j, k, m, res, resBF);
}
}
}
}
writefln("total %s, match %s", total, match);
}
uint max(uint a, uint b)
{
return (a > b) ? a : b;
}
uint maxOr(uint minA, uint maxA, uint minB, uint maxB)
{
uint result = minA | maxA | minB | maxB,
diff = max(maxA - minA, maxB - minB);
if(diff)
{
result |= (1 << (bsr(diff) + 1)) - 1;
}
return result;
}
/* compute result using brute force */
uint maxOrBF(uint minA, uint maxA, uint minB, uint maxB)
{
return bitsSetInIntervallBF(minA, maxA) | bitsSetInIntervallBF(minB, maxB);
}
uint bitsSetInIntervallBF(uint min, uint max)
{
uint result = 0;
for(; min <= max; ++min)
{
result |= min;
}
return result;
}
``` |

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

| ||||

Posted in reply to Jérôme M. Berger Attachments: - signature.asc (OpenPGP digital signature)
| OK, I found a solution that is optimal in over 99% of the cases (99.195% to be precise), while still being fast (because it avoids looping over the bits): ==============================8<------------------------------ uint32_t maxOr (uint32_t minA, uint32_t minB, uint32_t maxA, uint32_t maxB) { if (maxA == 0) return maxB; if (maxB == 0) return maxA; uint32_t a = maxA ^ minA; if (a != 0) a = ((1 << highbit (a)) - 1); uint32_t b = maxB ^ minB; if (b != 0) b = ((1 << highbit (b)) - 1); uint32_t t = maxA & maxB; if (t != 0) t = ((1 << highbit (t)) - 1); return min (maxA|maxB|a|b, maxA|maxB|t); } ------------------------------>8============================== Mostly it's black magic ;) and it's **much** simpler than the first version that reached those performances. The explanation is in the rest of the message. I will only talk about the ``a`` side of the problem here (i.e assume ``maxB==minB``). The ``b`` side is symmetrical. The idea is to build a value that is between minA and maxA and will set as many bits as possible when or'ed with maxB: - The first thing we do is to notice that minA and maxA have the following structure (in binary): ``minA=A0x`` and ``maxA=A1y`` where the ``A`` part is identical. Any number between minA and maxA will therefore be of the form ``a=Az``. A very conservative estimate tells us that if we set ``z`` to all ones, then ``maxB|maxA|z`` will be greater than ``maxB|a`` for all ``a``. This is computed by ``(1 << highbit (maxA ^ minA)) - 1``; - Another way to look at the problem is to say that a ``0`` bit in maxA cannot be set unless some higher ``1`` bit is unset. For example if maxA is ``0b10`` then if we want to set bit 0, we need to unset bit 1 (which will give us ``0b01``). So by doing this we get a lower value for ``a|maxB`` unless this bit was already set in maxB. The expression ``maxA & maxB`` gives us the bits that we can unset. Therefore only bits that are less significant than the high bit of ``maxA & maxB`` may be set. This is stored into the variable ``t``; - Either method works, but neither is perfect. By taking the minimum of the two results, we get the best of both worlds (although still isn't perfect). Jerome -- mailto:jeberger@free.fr http://jeberger.free.fr Jabber: jeberger@jabber.fr |

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

| ||||

Posted in reply to Jérôme M. Berger | � wrote: > The idea is to build a value that is between minA and maxA and will > set as many bits as possible when or'ed with maxB: The assumption that maxB would be the value that produces the maximum a|b is not correct. A lower valued b may fill more gaps in the bit representation of what is calculated from min_a and max_a. Your function failed for me with the following values: min_a 00000000000000000000000011001000 000000c8 200 max_a 00000000000000000000001100001111 0000030f 783 min_b 00000000000000000000000001000101 00000045 69 max_b 00000000000000000000001001100001 00000261 609 calculated 00000000000000000000001001100101 00000265 613 WRONG! empirical 00000000000000000000001111111111 000003ff 1023 emp_max_a 00000000000000000000000110011110 0000019e 414 emp_max_b 00000000000000000000001001100001 00000261 609 Please see my test code elsewhere in the same thread: :) http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108851 Ali |

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

| ||||

Posted in reply to Ali Çehreli Attachments: - maxor.cc
- signature.asc (OpenPGP digital signature)
| Ali Çehreli wrote: > � wrote: > >> The idea is to build a value that is between minA and maxA and will set as many bits as possible when or'ed with maxB: > > The assumption that maxB would be the value that produces the maximum a|b is not correct. A lower valued b may fill more gaps in the bit representation of what is calculated from min_a and max_a. > > Your function failed for me with the following values: > > min_a 00000000000000000000000011001000 000000c8 200 > max_a 00000000000000000000001100001111 0000030f 783 > min_b 00000000000000000000000001000101 00000045 69 > max_b 00000000000000000000001001100001 00000261 609 > calculated 00000000000000000000001001100101 00000265 613 > WRONG! empirical 00000000000000000000001111111111 000003ff 1023 > emp_max_a 00000000000000000000000110011110 0000019e 414 > emp_max_b 00000000000000000000001001100001 00000261 609 > > Please see my test code elsewhere in the same thread: :) > > http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108851 > The "calculated" value above obviously was not computed with my function! Since the return value from my function includes maxA and maxB, at least all bits that are set in either of those should be set in the output. I've run my code with those input and the result is 3ff as expected... (See attached source file). Jerome -- mailto:jeberger@free.fr http://jeberger.free.fr Jabber: jeberger@jabber.fr |