April 11, 2010 Re: value range propagation for _bitwise_ OR | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jérôme M. Berger Attachments:
| 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jérôme M. Berger | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jérôme M. Berger | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Steven Schveighoffer | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Adam D. Ruppe | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ali Çehreli Attachments:
| 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Steven Schveighoffer Attachments:
| 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jérôme M. Berger | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jérôme M. Berger Attachments:
| 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu Attachments:
| 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 |
Copyright © 1999-2021 by the D Language Foundation