On 12/04/2010 01:21 PM, Ellery Newcomer wrote:
is it just me, or does this fail for
minA = 0
minB = 0
maxA = 0x80_00_00_00
maxB = 0x80_00_00_00
I'm pretty sure you need to handle 1<< 32 specially
i'm thinking this is better:
uint32_t maxOr (uint32_t minA, uint32_t minB,
uint32_t max
is it just me, or does this fail for
minA = 0
minB = 0
maxA = 0x80_00_00_00
maxB = 0x80_00_00_00
I'm pretty sure you need to handle 1 << 32 specially
Andrei Alexandrescu wrote:
On 04/12/2010 12:57 PM, "Jérôme M. Berger" wrote:
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
On Sat, 17 Apr 2010 01:55:26 -0400, Andrei Alexandrescu
wrote:
On 04/16/2010 11:43 PM, Steven Schveighoffer wrote:
Andrei Alexandrescu Wrote:
Looks great, thanks Jerome!
Now, how about that case in which some or all of the ranges
involved include negative values?
I solved already signed
Don wrote:
> Jérôme M. Berger wrote:
>> Andrei Alexandrescu wrote:
>>> On 04/16/2010 11:43 PM, Steven Schveighoffer wrote:
Andrei Alexandrescu Wrote:
> Looks great, thanks Jerome!
>
> Now, how about that case in which some or all of the ranges
> involved include negative v
Jérôme M. Berger wrote:
Andrei Alexandrescu wrote:
On 04/16/2010 11:43 PM, Steven Schveighoffer wrote:
Andrei Alexandrescu Wrote:
Looks great, thanks Jerome!
Now, how about that case in which some or all of the ranges
involved include negative values?
I solved already signed values in terms
Andrei Alexandrescu wrote:
> On 04/16/2010 11:43 PM, Steven Schveighoffer wrote:
>> Andrei Alexandrescu Wrote:
>>
>>> Looks great, thanks Jerome!
>>>
>>> Now, how about that case in which some or all of the ranges
>>> involved include negative values?
>>
>> I solved already signed values in terms o
On 04/16/2010 11:43 PM, Steven Schveighoffer wrote:
Andrei Alexandrescu Wrote:
Looks great, thanks Jerome!
Now, how about that case in which some or all of the ranges
involved include negative values?
I solved already signed values in terms of any valid unsigned
solution, see here:
http://ww
Andrei Alexandrescu Wrote:
> Looks great, thanks Jerome!
>
> Now, how about that case in which some or all of the ranges involved
> include negative values?
I solved already signed values in terms of any valid unsigned solution, see
here:
http://www.digitalmars.com/webnews/newsgroups.php?art_
On 04/12/2010 12:57 PM, "Jérôme M. Berger" wrote:
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 pro
Fawzi Mohamed:
> Please note that I (and probably you too) use overflow very often when
> you subtract unsigned values.
I think it can be useful to have two flags: one for signed integer overflows
only, and one for both signed&unsigned.
> D should also introduce the checked and uncheked stat
On 14-apr-10, at 21:55, bearophile wrote:
Sorry for the slow answer, I have some things to catch up.
Fawzi Mohamed:
integral overflow are helpful only if you have automatic conversion
to a larger type,<
I don't understand what you mean here. There are various ways to
detect overflows, f
Sorry for the slow answer, I have some things to catch up.
Fawzi Mohamed:
>integral overflow are helpful only if you have automatic conversion to a
>larger type,<
I don't understand what you mean here. There are various ways to detect
overflows, from the simple ones like using a long to comput
Steven Schveighoffer wrote:
> In my opinion? Yes, slower compilers that make code easier to write are
> better. I don't spend lots of time compiling, I spend it writing code.
> And I don't need to babysit the compiler, it goes off and does its thing.
>
> Performance is only important in the end
On Tue, 13 Apr 2010 13:37:13 -0400, Jérôme M. Berger
wrote:
Steven Schveighoffer wrote:
Jérôme M. Berger Wrote:
Steven Schveighoffer wrote:
When we're talking about the difference between O(1) and O(lgn), I'll
take accuracy over speed in my compiler any day.
And when we're talkin
Steven Schveighoffer wrote:
> using your highbit function, which is very neat BTW
>
Thanks, but I can't claim credit for it. It's a classical algorithm
which comes up regularly in programming discussions and newsgroups...
> uint maxor(uint mina, uint maxa, uint minb, uint maxb)
> {
>
Steven Schveighoffer wrote:
> Steven Schveighoffer Wrote:
>
>> I'll have to double check, I thought I copied your code verbatim (I did
>> switch around the arguments to be minA, maxA, minB, maxB to fit my test
>> harness, and I changed the uint_32_t to uint). I'll check tomorrow at work
>> whe
Fawzi Mohamed wrote:
>
> On 13-apr-10, at 12:02, Don wrote:
>> It's been part of DMD2 for a while now. It allows you to do things like:
>>
>> ubyte lowbits(int x)
>> {
>>return x & 7;
>> }
>>
>> without an explicit cast. The compiler knows that x&7 can safely fit
>> inside a single byte. Wher
Steven Schveighoffer wrote:
> Jérôme M. Berger Wrote:
>
>> Steven Schveighoffer wrote:
>>> When we're talking about the difference between O(1) and O(lgn), I'll
>>> take accuracy over speed in my compiler any day.
>> And when we're talking about the difference between 10s and 55s for
>> a min
Don wrote:
Adam D. Ruppe wrote:
On Tue, Apr 13, 2010 at 11:10:24AM -0400, Clemens wrote:
That's strange. Looking at src/backend/cod4.c, function cdbscan, in
the dmd sources, bsr seems to be implemented in terms of the bsr
opcode [1] (which I guess is the reason it's an intrinsic in the
first
Adam D. Ruppe wrote:
On Tue, Apr 13, 2010 at 11:10:24AM -0400, Clemens wrote:
That's strange. Looking at src/backend/cod4.c, function cdbscan, in the dmd
sources, bsr seems to be implemented in terms of the bsr opcode [1] (which I
guess is the reason it's an intrinsic in the first place). I wo
On Tue, Apr 13, 2010 at 11:10:24AM -0400, Clemens wrote:
> That's strange. Looking at src/backend/cod4.c, function cdbscan, in the dmd
> sources, bsr seems to be implemented in terms of the bsr opcode [1] (which I
> guess is the reason it's an intrinsic in the first place). I would have
> expect
On Tue, Apr 13, 2010 at 10:52:14AM -0400, Steven Schveighoffer wrote:
> Just a note, this code should be runnable in C++, because the compiler is
> written in C++. Is bsr available there?
I just assumed since it was in D that it was probably
in DMC too, but I can't find it in the docs, so maybe
Adam Ruppe Wrote:
> Jerome's highbit function is the same as std.intrinsic.bsr. I wonder
> which is faster?
>
> I ran a test, and for 100 million iterations (1..1000), the
> intrinsic beat out his function be a mere 300 milliseconds on my box.
> - highbit ran in an average of 1897 ms and bsr
Steven Schveighoffer:
> I never would have thought of doing a binary search for the high bit, it
> is definitely a novel idea to me :)
You can learn something from this page (it can also be useful for the
translation to C++):
http://graphics.stanford.edu/~seander/bithacks.html
Bye,
bearophile
On Tue, 13 Apr 2010 09:56:34 -0400, Adam Ruppe
wrote:
Jerome's highbit function is the same as std.intrinsic.bsr. I wonder
which is faster?
Just a note, this code should be runnable in C++, because the compiler is
written in C++. Is bsr available there?
Recompiling with -inline -O -re
Jerome's highbit function is the same as std.intrinsic.bsr. I wonder
which is faster?
I ran a test, and for 100 million iterations (1..1000), the
intrinsic beat out his function be a mere 300 milliseconds on my box.
- highbit ran in an average of 1897 ms and bsr did the same in an
average if 1
Steven Schveighoffer wrote:
On Mon, 12 Apr 2010 22:37:00 -0400, Steven Schveighoffer
wrote:
Jérôme M. Berger Wrote:
Steven Schveighoffer wrote:
> Fails for test case:
>
> minA = 4, maxA = 4, minB = 4, maxB = 6 (outputs 7, accurate result
is 6).
>
Nope, outputs 6. Note that I've run
On Mon, 12 Apr 2010 22:37:00 -0400, Steven Schveighoffer
wrote:
Jérôme M. Berger Wrote:
Steven Schveighoffer wrote:
> Fails for test case:
>
> minA = 4, maxA = 4, minB = 4, maxB = 6 (outputs 7, accurate result is
6).
>
Nope, outputs 6. Note that I've run an exhaustive search fo
On 13-apr-10, at 12:01, bearophile wrote:
Fawzi Mohamed:
I guess that I am missing something obvious, so I don't see the
reason
for range propagation, but maybe I am not the only one, so thanks for
an explanation...
Range propagation can improve the situation a little, so it's not
bad. B
On 13-apr-10, at 12:02, Don wrote:
Fawzi Mohamed wrote:
On 12-apr-10, at 21:40, Steven Schveighoffer wrote:
On Mon, 12 Apr 2010 13:45:14 -0400, Jérôme M. Berger fr> wrote:
Steven Schveighoffer wrote:
J�r�me M. Berger Wrote:
J�r�me M. Berger wrote:
OK, I found a solution that is optima
Fawzi Mohamed:
> I guess that I am missing something obvious, so I don't see the reason
> for range propagation, but maybe I am not the only one, so thanks for
> an explanation...
Range propagation can improve the situation a little, so it's not bad. But it
can't replace proper integral overf
Fawzi Mohamed wrote:
On 12-apr-10, at 21:40, Steven Schveighoffer wrote:
On Mon, 12 Apr 2010 13:45:14 -0400, Jérôme M. Berger
wrote:
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%
On 12-apr-10, at 21:40, Steven Schveighoffer wrote:
On Mon, 12 Apr 2010 13:45:14 -0400, Jérôme M. Berger
wrote:
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), w
Steven Schveighoffer Wrote:
> I'll have to double check, I thought I copied your code verbatim (I did
> switch around the arguments to be minA, maxA, minB, maxB to fit my test
> harness, and I changed the uint_32_t to uint). I'll check tomorrow at work
> where the computer I used to test is.
>
Jérôme M. Berger Wrote:
> Steven Schveighoffer wrote:
> > When we're talking about the difference between O(1) and O(lgn), I'll
> > take accuracy over speed in my compiler any day.
> And when we're talking about the difference between 10s and 55s for
> a minimal loss of accuracy, which wil
Jérôme M. Berger Wrote:
> Steven Schveighoffer wrote:
> > Fails for test case:
> >
> > minA = 4, maxA = 4, minB = 4, maxB = 6 (outputs 7, accurate result is 6).
> >
> Nope, outputs 6. Note that I've run an exhaustive search for all
> combinations in the [0, 63] range, so if there are mis
Jérôme M. Berger wrote:
Steven Schveighoffer wrote:
Fails for test case:
minA = 4, maxA = 4, minB = 4, maxB = 6 (outputs 7, accurate result is 6).
Nope, outputs 6. Note that I've run an exhaustive search for all
combinations in the [0, 63] range, so if there are mistakes they
have to
Steven Schveighoffer wrote:
> Fails for test case:
>
> minA = 4, maxA = 4, minB = 4, maxB = 6 (outputs 7, accurate result is 6).
>
Nope, outputs 6. Note that I've run an exhaustive search for all
combinations in the [0, 63] range, so if there are mistakes they
have to be outside that rang
Steven Schveighoffer wrote:
> On Mon, 12 Apr 2010 13:45:14 -0400, Jérôme M. Berger
> wrote:
>
>> 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 (e
Don wrote:
> Jérôme M. Berger wrote:
>> Steven Schveighoffer wrote:
>>> On Sun, 11 Apr 2010 22:36:33 -0400, Rainer Deyke
>>> wrote:
On 4/11/2010 13:16, Ali Çehreli wrote:
> Rainer Deyke wrote:
If you want 100% percent accuracy then you probably shouldn't be using
(min, max) pair
On Mon, 12 Apr 2010 13:56:23 -0400, Jérôme M. Berger
wrote:
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);
a
On Mon, 12 Apr 2010 13:45:14 -0400, Jérôme M. Berger
wrote:
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 t
Jérôme M. Berger wrote:
Steven Schveighoffer wrote:
On Sun, 11 Apr 2010 22:36:33 -0400, Rainer Deyke
wrote:
On 4/11/2010 13:16, Ali Çehreli wrote:
Rainer Deyke wrote:
The intention of fill_bits is to create a number that contains all of
the bits of all of the numbers from min_v to max_v.
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
>>> exac
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
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
> optima
Steven Schveighoffer wrote:
> On Sun, 11 Apr 2010 22:36:33 -0400, Rainer Deyke
> wrote:
>
>> On 4/11/2010 13:16, Ali Çehreli wrote:
>>> Rainer Deyke wrote:
>>>
The intention of fill_bits is to create a number that contains all of
the bits of all of the numbers from min_v to max_v.
>>>
>
Steven Schveighoffer wrote:
> I'll work on signed values tomorrow :)
>
Signed values are trivial:
int maxOr (int minA, int minB, int maxA, int maxB)
{
if ((minA < 0) && (maxA >= 0))
return max (maxOr (minA, minB, -1, maxB),
maxOr (0, minB, maxA, maxB));
if (
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'
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
On Mon, 12 Apr 2010 01:11:37 -0400, Rainer Deyke
wrote:
On 4/11/2010 20:51, Steven Schveighoffer wrote:
Range propagation is needed to determine if you can put a value into a
smaller type. At that point, all that is needed is the min and max.
Technically, you don't even need min and max a
On 04/11/2010 10:07 PM, Steven Schveighoffer wrote:
[snip]
I'll work on signed values tomorrow :)
This is great work, Steve!
Andrei
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
On Sun, 11 Apr 2010 00:30:07 -0400, Steven Schveighoffer
wrote:
Signed is probably trickier, suppose one is always negative and one is
always positive!
Turns out signed is really easy once you have unsigned solved.
Here is minor and maxor for signed assuming unsigned is solved:
int maxor
On 4/11/2010 20:51, Steven Schveighoffer wrote:
> Range propagation is needed to determine if you can put a value into a
> smaller type. At that point, all that is needed is the min and max.
Technically, you don't even need min and max at that point. A bit mask
would be enough.
> However, you
On Sun, 11 Apr 2010 00:30:07 -0400, Steven Schveighoffer
wrote:
Couldn't help it, this seems like such a fun problem, I had to solve it
:)
uint maxor(uint mina, uint maxa, uint minb, uint maxb)
{
uint bt = 1 << 31;
uint result = 0;
while(bt)
{
if((bt & maxa) &&
On Sun, 11 Apr 2010 22:36:33 -0400, Rainer Deyke
wrote:
On 4/11/2010 13:16, Ali Çehreli wrote:
Rainer Deyke wrote:
The intention of fill_bits is to create a number that contains all of
the bits of all of the numbers from min_v to max_v.
But no value in the range may have all those bits s
On 4/11/2010 13:16, Ali Çehreli wrote:
> Rainer Deyke wrote:
>
>> The intention of fill_bits is to create a number that contains all of
>> the bits of all of the numbers from min_v to max_v.
>
> But no value in the range may have all those bits set. As a result, a|b
> may have less bits set than
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 agre
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
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
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
Ali Çehreli wrote:
> Yes, it's incomplete, but does catch problems. :) So far, Steven
> Schveighoffer's maxor() is the only one that passes the tests. (There
> may be other solutions that I've missed.)
>
I suggest you triple-check your implementations of everyone's
algorithms since the cou
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
� 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 i
Rainer Deyke wrote:
> The intention of fill_bits is to create a number that contains all of
> the bits of all of the numbers from min_v to max_v.
But no value in the range may have all those bits set. As a result, a|b
may have less bits set than fill_bits returns.
> In other words:
>
> min_v
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_tminA, uint32_t minB,
uint32_
Am 10.04.2010, 23:17 Uhr, schrieb Don :
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)) {
i
On 4/11/2010 11:16, Ali Çehreli wrote:
> Rainer Deyke wrote:
>> How about this?
>>
>> uint fill_bits(uint min_v, uint max_v) {
>> uint mask = 0;
>> for (int i = 0; i < 32; ++i) {
>> if ((min_v | (1 << i)) <= max_v) mask |= (1 << i);
>> }
>> return mask;
>> }
>>
>> max_c = min(
>> max_
Rainer Deyke wrote:
How about this?
uint fill_bits(uint min_v, uint max_v) {
uint mask = 0;
for (int i = 0; i < 32; ++i) {
if ((min_v | (1 << i)) <= max_v) mask |= (1 << i);
}
return mask;
}
max_c = min(
max_a | fill_bits(min_b, max_b),
max_b | fill_bits(min_a, max_a));
That
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 b
How about this?
uint fill_bits(uint min_v, uint max_v) {
uint mask = 0;
for (int i = 0; i < 32; ++i) {
if ((min_v | (1 << i)) <= max_v) mask |= (1 << i);
}
return mask;
}
max_c = min(
max_a | fill_bits(min_b, max_b),
max_b | fill_bits(min_a, max_a));
--
Rainer Deyke - rain...@e
I normally lurk here, because I don't have any projects that use D and
thus I haven't really learned it. But I just wanted to say that this
problem, and the three threads of solutions, constitute one of the most
fascinating discussions I've seen on the newsgroups in quite a while --
probably be
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
On Sat, Apr 10, 2010 at 09:53:42PM -0500, Andrei Alexandrescu wrote:
> Ha! Good point. I'd forgotten the initial requirement and considered
> both values to start at 0. They don't! Adam? :o)
Yeah, my big brute-force tester program ran loops for min_a and min_b too.
And it tripped an assert.
core
On Sat, 10 Apr 2010 22:53:42 -0400, Andrei Alexandrescu
wrote:
On 04/10/2010 09:51 PM, Steven Schveighoffer wrote:
Andrei Alexandrescu Wrote:
On 04/10/2010 12:01 PM, Andrei Alexandrescu wrote:
Consider:
byte c = a | b;
Say you already know min_a, max_a, min_b, and max_b. How do you
comp
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
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
I have filed a "report":
http://d.puremagic.com/issues/show_bug.cgi?id=4077
Bye,
bearophile
Andrei Alexandrescu Wrote:
> On 04/10/2010 12:01 PM, Andrei Alexandrescu wrote:
> > Consider:
> >
> > byte c = a | b;
> >
> > Say you already know min_a, max_a, min_b, and max_b. How do you compute
> > min_c and max_c? I thought of it for a bit and it seems quite tricky.
> >
> >
> > Thanks,
> >
>
On 04/10/2010 09:51 PM, Steven Schveighoffer wrote:
Andrei Alexandrescu Wrote:
On 04/10/2010 12:01 PM, Andrei Alexandrescu wrote:
Consider:
byte c = a | b;
Say you already know min_a, max_a, min_b, and max_b. How do you
compute min_c and max_c? I thought of it for a bit and it seems
quite tr
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=1; equal=14585400 (14.5854%)
I think that's a perfect result. Here's why: the equality comparison checks
two
On Sat, Apr 10, 2010 at 08:42:54PM -0500, Andrei Alexandrescu wrote:
> What results does it yield with my main() test harness?
total=1; 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 function
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 empiric
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
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
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=1; equal=14585400 (14.5854%)
with the function:
u
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 |
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 cand
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, bi
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 on
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
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) contin
Adam D. Ruppe:
> Oh no! Eyeballing again showed a problem.. I should have put parens in my
> asserts:
> a | b < f(a,b) != (a|b) < f(a,b)
Bugs are gold nuggets! Yes, the precedence of bitwise operators is low, it's an
error-prone thing, it's a part of C/C++/D that causes frequent bugs in prog
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 = candida
On Sat, Apr 10, 2010 at 02:57:59PM -0400, Adam D. Ruppe wrote:
> Let me test it... it seems to work. Here's the D program I used to brute-force
> the test:
Oh no! Eyeballing again showed a problem.. I should have put parens in my
asserts:
a | b < f(a,b) != (a|b) < f(a,b)
That breaks it. Back
Adam D. Ruppe:
> I understand the position, but I don't advocate it just because I think it
> would
> be annoying and not give much of a benefit.
I have never added a bug report in Bugzilla about this because I think it
doesn't give enough benefit.
Thank you for your answer,
bye,
bearophile
On Sat, Apr 10, 2010 at 02:55:36PM -0400, bearophile wrote:
> Time ago I have even suggested to disallow bitwise ops when one or both
> operands are signed...
I understand the position, but I don't advocate it just because I think it would
be annoying and not give much of a benefit.
Consider the
On Sat, Apr 10, 2010 at 02:57:59PM -0400, Adam D. Ruppe wrote:
> Let me test it... it seems to work. Here's the D program I used to brute-force
> the test:
The main() function there isn't an ideal test. Here's a better one:
void main() {
for(uint max_a = 0; max_a < 100; max_a++)
f
1 - 100 of 105 matches
Mail list logo
