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:jeber...@free.fr
http://jeberger.free.fr
Jabber: jeber...@jabber.fr
signature.asc
Description: OpenPGP digital signature
