April 10, 2010
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 out a zero. Therefore, x|y >= x && x|y >= y, which only works on the max(mina, minb) function.


-- 
Adam D. Ruppe
http://arsdnet.net
April 10, 2010
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 only set bits -
> it can never take a one and spit out a zero. Therefore, x|y>= x&&  x|y>= y,
> which only works on the max(mina, minb) function.

Sorry, I meant max of the two minima.

Andrei
April 10, 2010
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, 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).
> 
> It tries to set all bits in which maxa is zero starting and keeps them set if the resulting number is less than maxb.
> 
	In other words: maxa | ((1 << highbit (maxb))-1) where:

int highbit (uint n) {
   auto result = 0;
   if (n & 0xFFFF0000) {
      result += 16;
      n = n >> 16;
   }
   if (n & 0xFF00) {
      result += 8;
      n = n >> 8;
   }
   if (n & 0xF0) {
      result += 4;
      n = n >> 4;
   }
   if (n & 0xC) {
      result += 2;
      n = n >> 2;
   }
   if (n & 0x2) {
      result += 1;
      n = n >> 1;
   }
   if (n & 0x1) {
      result += 1;
   }
   return result;
}

		Jerome
-- 
mailto:jeberger@free.fr
http://jeberger.free.fr
Jabber: jeberger@jabber.fr



April 10, 2010
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 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).
>>
>> It tries to set all bits in which maxa is zero starting and keeps them
>> set if the resulting number is less than maxb.
>>
> 	In other words: maxa | ((1<<  highbit (maxb))-1) where:
>
> int highbit (uint n) {
>     auto result = 0;
>     if (n&  0xFFFF0000) {
>        result += 16;
>        n = n>>  16;
>     }
>     if (n&  0xFF00) {
>        result += 8;
>        n = n>>  8;
>     }
>     if (n&  0xF0) {
>        result += 4;
>        n = n>>  4;
>     }
>     if (n&  0xC) {
>        result += 2;
>        n = n>>  2;
>     }
>     if (n&  0x2) {
>        result += 1;
>        n = n>>  1;
>     }
>     if (n&  0x1) {
>        result += 1;
>     }
>     return result;
> }
>
> 		Jerome

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?

The program below compiles, runs, and prints

total=100000000; equal=3850865 (3.85087%)

Here it is:

import std.contracts, std.stdio;

uint maxOR(uint maxa, uint maxb) {
    return maxa | ((1 << highbit (maxb))-1);
}

uint highbit(uint n) {
   auto result = 0;
   if (n & 0xFFFF0000) {
      result += 16;
      n = n >> 16;
   }
   if (n & 0xFF00) {
      result += 8;
      n = n >> 8;
   }
   if (n & 0xF0) {
      result += 4;
      n = n >> 4;
   }
   if (n & 0xC) {
      result += 2;
      n = n >> 2;
   }
   if (n & 0x2) {
      result += 1;
      n = n >> 1;
   }
   if (n & 0x1) {
      result += 1;
   }
   return result;
}

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, "%)");
}

However, your method is not the tightest; seems like mine is tighter. When I replaced maxOR with this:

uint maxOR2(uint maxa, uint maxb) {
    if (maxa < maxb) return maxOR(maxb, maxa);
    uint candidate = 0;
    uint mask = 1u << 31;
    for (uint i = 0; i < 32; ++i, mask >>= 1) {
        if (maxa & mask) continue;
        auto t = candidate | (1 << (31 - i));
        if (t <= maxb) candidate = t;
    }
    return maxa | candidate;
}

I got:

total=100000000; equal=9822516 (9.82252%)

Besides, I verified that my method returns numbers <= yours.


Andrei
April 10, 2010
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 | mask;
        if (t <= maxb) candidate = t;
    }
    return maxa | candidate;
}

Among other things I remove the test whether maxa >= maxb at the beginning of the function. I now obtain:

total=100000000; equal=14585400 (14.5854%)

so this function is better than all others so far. But I don't understand why it beats this one:

uint maxOR(uint maxa, uint maxb) {
    if (maxa < maxb) return maxOR(maxb, maxa); // added
    uint candidate = 0;
    uint mask = 1u << 31;
    for (; mask; mask >>= 1) {
        if (maxa & mask) continue;
        auto t = candidate | mask;
        if (t <= maxb) candidate = t;
    }
    return maxa | candidate;
}


Andrei
April 10, 2010
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=100000000; equal=14585400 (14.5854%)

with the function:

uint maxOR(uint maxa, uint maxb) {
    uint candidate = 0;
    uint mask = 1u << 31;
    for (; mask; mask >>= 1) {
        if (maxa & mask) continue;
        auto t = candidate | mask;
        if (t <= maxb) candidate = t;
    }
    return maxa | candidate;
}

Inserting a test and a recursive call at the top keeps the result but actually slows down execution a bit.


Andrei
April 10, 2010
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, uint b) { return (a >= b) ? b : a; }
uint numbits(uint a) { return a == 0 ? a : (bsr(a) + 1); }

uint max_c(uint a, uint b) {
	uint mn = min(a, b);
	uint mx = max(a, b);
	if(mn == 0)
		return mx;
	// if there is a bit we can reuse, it grants us everything before it too
	uint reusable = mn & mx;
	if(reusable)
		return (mx | ((1 << numbits(reusable)) - 1)) | mn;
	else
		return mx | mn;
}

uint min_c(uint min_a, uint min_b) {
	return max(min_a, min_b);
}
=====

I can't believe I spent all day on this...

-- 
Adam D. Ruppe
http://arsdnet.net
April 10, 2010
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 max_c function returns, it doesn't always match if the minimums change.

This might be a bug; it is unintuitive that it would do this, but it actually makes sense. Consider if min == max, you only have one value to work with.

let max_a = 4, min_a = 0;

max_b = 4

You can get 7 out of it, since 3 < 4, so it is a possible number and: 100 | 011 == 7

But, if min_b == 4, the only possible value for b is 4. And: 100 | 100 == 4.

Increasing min_b does indeed decrease the max you can get.


Nice fact, but I've spent too much time on this already, so I'll call it done with this:

My max_c included some unnecessary code: my reusable mask obsoletes all of my special case code! So, we can bring the program down to three lines:

import std.intrinsic;
uint numbits(uint a) { return a == 0 ? a : (bsr(a) + 1); }
uint max_c(uint a, uint b) { return a | ((1 << numbits(a&b)) - 1) | b; }

It passes my test, though since I bugged it up the first time, I might have done it again.

-- 
Adam D. Ruppe
http://arsdnet.net
April 11, 2010
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 empirically calculated max_c and compare it to
> what my max_c function returns, it doesn't always match if the minimums change.
>
> This might be a bug; it is unintuitive that it would do this, but it actually
> makes sense. Consider if min == max, you only have one value to work with.
>
> let max_a = 4, min_a = 0;
>
> max_b = 4
>
> You can get 7 out of it, since 3<  4, so it is a possible number and: 100 | 011 == 7
>
> But, if min_b == 4, the only possible value for b is 4. And: 100 | 100 == 4.
>
> Increasing min_b does indeed decrease the max you can get.
>
>
> Nice fact, but I've spent too much time on this already, so I'll call it done with
> this:
>
> My max_c included some unnecessary code: my reusable mask obsoletes all of
> my special case code! So, we can bring the program down to three lines:
>
> import std.intrinsic;
> uint numbits(uint a) { return a == 0 ? a : (bsr(a) + 1); }
> uint max_c(uint a, uint b) { return a | ((1<<  numbits(a&b)) - 1) | b; }
>
> It passes my test, though since I bugged it up the first time, I might have done
> it again.

What results does it yield with my main() test harness?

Andrei
April 11, 2010
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.

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.

-- 
Adam D. Ruppe
http://arsdnet.net