View mode: basic / threaded / horizontal-split · Log in · Help
April 11, 2010
Re: value range propagation for _bitwise_ OR
Jérôme M. Berger wrote:
> 	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):
> 
	I've run my function and Andrei's on all possible min, max pairs in
0..299 without checking, just for the timing. On my computer (Athlon
X2 64 @2GHz), my function took 50s and Andrei's took 266s. The
difference should be even bigger for larger numbers.

		Jerome
-- 
mailto:jeberger@free.fr
http://jeberger.free.fr
Jabber: jeberger@jabber.fr
April 11, 2010
Re: value range propagation for _bitwise_ OR
Jérôme M. Berger wrote:
> 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!

My mistake: It was your function but the highbit() that I used was not 
correct. The one I used was returning the *value* of the highest bit.

> 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).

Perhaps my test code is wrong; but I can't find my error. :/

Your function reports 0b_111 for these set of values:

        min_a = 5;
        max_a = 6;
        min_b = 4;
        max_b = 4;

But the maximum value of a|b is 6.

Ali
April 12, 2010
Re: value range propagation for _bitwise_ OR
Jérôme M. Berger Wrote:

> Jérôme M. Berger wrote:
> > 	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):
> > 
> 	I've run my function and Andrei's on all possible min, max pairs in
> 0..299 without checking, just for the timing. On my computer (Athlon
> X2 64 @2GHz), my function took 50s and Andrei's took 266s. The
> difference should be even bigger for larger numbers.

Can I ask, what is the point of having a non-exact solution (unless you are just doing this for fun)?

We are talking about range propagation, a function of the compiler, not a function of the compiled program.  Therefore, slower but more exact functions should be preferred, since they only affect the compile time.  Note that you will only need to do this range propagation on lines that "or" two values together, and something that reduces the runtime of the compiler by 216 seconds, but only when compiling enough code to have over 8 billion 'or' operations in it (300^4), I don't think is really that important.  Give me the exact solution that prevents me from having to cast when the compiler can prove it, even if the runtime of the compiler is slightly slower.

Just my $.02

-Steve
April 12, 2010
Re: value range propagation for _bitwise_ OR
On Sun, Apr 11, 2010 at 10:00:41PM -0400, Steven Schveighoffer wrote:
> We are talking about range propagation, a function of the compiler, not a function of the compiled program.  Therefore, slower but more exact functions should be preferred, since they only affect the compile time.

I agree with this. While my solution has a certain beauty to it and is
fast, your solution accurately covers all the bases, whereas mine fails with
min > 1. I say we go with your's.

-- 
Adam D. Ruppe
http://arsdnet.net
April 12, 2010
Re: value range propagation for _bitwise_ OR
On 04/11/2010 09:18 PM, Adam D. Ruppe wrote:
> On Sun, Apr 11, 2010 at 10:00:41PM -0400, Steven Schveighoffer wrote:
>> We are talking about range propagation, a function of the compiler, not a function of the compiled program.  Therefore, slower but more exact functions should be preferred, since they only affect the compile time.
>
> I agree with this. While my solution has a certain beauty to it and is
> fast, your solution accurately covers all the bases, whereas mine fails with
> min>  1. I say we go with your's.

Agreed. Steve's solution is the best we have for unsigned numbers.

Andrei
April 12, 2010
Re: value range propagation for _bitwise_ OR
Ali Çehreli wrote:
> Jérôme M. Berger wrote:
>> 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!
> 
> My mistake: It was your function but the highbit() that I used was not
> correct. The one I used was returning the *value* of the highest bit.
> 
>> 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).
> 
> Perhaps my test code is wrong; but I can't find my error. :/
> 
> Your function reports 0b_111 for these set of values:
> 
>         min_a = 5;
>         max_a = 6;
>         min_b = 4;
>         max_b = 4;
> 
> But the maximum value of a|b is 6.
> 
	Yes, like I said with my code, it is conservative. It will give the
optimal result for over 99% of the cases but give a slightly higher
value for the rest. I'll post a new version that's 100% precise in a
few minutes.

		Jerome
-- 
mailto:jeberger@free.fr
http://jeberger.free.fr
Jabber: jeberger@jabber.fr
April 12, 2010
Re: value range propagation for _bitwise_ OR
Steven Schveighoffer wrote:
> J�r�me M. Berger Wrote:
> 
>> J�r�me M. Berger wrote:
>>> 	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):
>>>
>> 	I've run my function and Andrei's on all possible min, max pairs in
>> 0..299 without checking, just for the timing. On my computer (Athlon
>> X2 64 @2GHz), my function took 50s and Andrei's took 266s. The
>> difference should be even bigger for larger numbers.
> 
> Can I ask, what is the point of having a non-exact solution (unless you are just doing this for fun)?
> 
> We are talking about range propagation, a function of the compiler, not a function of the compiled program.  Therefore, slower but more exact functions should be preferred, since they only affect the compile time.  Note that you will only need to do this range propagation on lines that "or" two values together, and something that reduces the runtime of the compiler by 216 seconds, but only when compiling enough code to have over 8 billion 'or' operations in it (300^4), I don't think is really that important.  Give me the exact solution that prevents me from having to cast when the compiler can prove it, even if the runtime of the compiler is slightly slower.
> 
	Funny you should say that given the current thread comparing the
speed of the D compiler to that of the Go compiler...

	We are talking about range propagation, a function of the compiler,
not a function of the compiled program. Since we can't get a 100%
accurate representation of the possible values anyway (even yours
might leave holes in the middle after all), then it might be better
to choose a faster, slightly less precise algorithm if the
difference is not too great. That's the difference between a
compiler and a full-fledged static code analysis an program prover.

	Anyway, the point is moot, I have a new version of my algorithm
with 100% precision and high speed.

		Jerome
-- 
mailto:jeberger@free.fr
http://jeberger.free.fr
Jabber: jeberger@jabber.fr
April 12, 2010
Re: value range propagation for _bitwise_ OR
Jérôme M. Berger wrote:

>> Your function reports 0b_111 for these set of values:
>>
>>         min_a = 5;
>>         max_a = 6;
>>         min_b = 4;
>>         max_b = 4;
>>
>> But the maximum value of a|b is 6.
>>
> 	Yes, like I said with my code, it is conservative. It will give the
> optimal result for over 99% of the cases but give a slightly higher
> value for the rest.

Now I see my problem: I took Andrei's puzzle literally. The implication 
of _compiler_implementation_ was too subtle for me.

That's the reason why none of my "correctly inaccurate" solutions has 
been posted to this thread. :)

Ali
April 12, 2010
Re: value range propagation for _bitwise_ OR
Here's a fast 100% precise solution:

==============================8<------------------------------
uint32_t maxOr (uint32_t minA, uint32_t minB,
               uint32_t maxA, uint32_t maxB)
{
  assert (minA <= maxA);
  assert (minB <= maxB);

  if (maxA == 0) return maxB;
  if (maxB == 0) return maxA;

  uint32_t a = maxA ^ minA;
  if (a != 0) {
     a = ((1 << (highbit (a)+1)) - 1) & maxA & maxB;
     if (a != 0)
        a = (1 << highbit (a)) - 1;
  }

  uint32_t b = maxB ^ minB;
  if (b != 0) {
     b = ((1 << (highbit (b)+1)) - 1) & maxA & maxB;
     if (b != 0)
        b = (1 << highbit (b)) - 1;
  }

  return maxA|maxB|a|b;
}
------------------------------>8==============================

		Jerome
-- 
mailto:jeberger@free.fr
http://jeberger.free.fr
Jabber: jeberger@jabber.fr
April 12, 2010
Re: value range propagation for _bitwise_ OR
Andrei Alexandrescu wrote:
> On 04/11/2010 09:18 PM, Adam D. Ruppe wrote:
>> On Sun, Apr 11, 2010 at 10:00:41PM -0400, Steven Schveighoffer wrote:
>>> We are talking about range propagation, a function of the compiler,
>>> not a function of the compiled program.  Therefore, slower but more
>>> exact functions should be preferred, since they only affect the
>>> compile time.
>>
>> I agree with this. While my solution has a certain beauty to it and is
>> fast, your solution accurately covers all the bases, whereas mine
>> fails with
>> min>  1. I say we go with your's.
> 
> Agreed. Steve's solution is the best we have for unsigned numbers.
> 
> Andrei
> 
	Nope, not anymore...

		Jerome
-- 
mailto:jeberger@free.fr
http://jeberger.free.fr
Jabber: jeberger@jabber.fr
1 2 3 4 5 6 7 8 9
Top | Discussion index | About this forum | D home