View mode: basic / threaded / horizontal-split · Log in · Help
April 11, 2010
Re: value range propagation for _bitwise_ OR
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
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
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
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
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
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
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
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
� 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
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
1 2 3 4 5 6 7 8
Top | Discussion index | About this forum | D home