value range propagation for _bitwise_ OR

Adam D. Ruppe destructionator at gmail.com
Sat Apr 10 12:13:02 PDT 2010


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++)
	for(uint max_b = 0; max_b < 100; max_b++)
	for(uint a = 0; a <= max_a; a++)
	for(uint b = 0; b <= max_b; b++)
		assert(a|b <= max_c(max_a, max_b));
}

// note that I renamed uint max_a to max_c.

We try a whole load of max_a and max_b and test every possible value. It
still runs without throwing.

My original function for min_c works too:

uint min_c(uint a, uint b) {
	return max(a, b);
}

And you can brute force test it all:

void main() {
	for(uint min_a = 0; min_a < 50; min_a++)
	for(uint min_b = 0; min_b < 50; min_b++)
	for(uint max_a = min_a; max_a < 100; max_a++)
	for(uint max_b = min_b; max_b < 100; max_b++)
	for(uint a = min_a; a <= max_a; a++)
	for(uint b = min_b; b <= max_b; b++) {
		assert(a|b <= max_c(max_a, max_b));
		assert(a|b >= min_c(min_a, min_b));
	}
}

This, as you can expect, takes a while to run, but does so without throwing. I'm
pretty confident in the functions now.

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



More information about the Digitalmars-d mailing list