value range propagation for _bitwise_ OR

["Jérôme M. Berger"]

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:jeberger at free.fr
http://jeberger.free.fr
Jabber: jeberger at jabber.fr

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: OpenPGP digital signature
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20100411/39e7fb1b/attachment.pgp>