On Sat, 2007-11-24 at 10:36 -0700, [EMAIL PROTECTED] wrote:
> > Since 160,000 < 2*(19*19)^2, a value well below the various possible
> > sums of squares, I have to ask what additional work you've done to prove
> > that the overlap doesn't cause problems?
>
> 160,000 is greater than (19 * 19 + 1)^2, so the linear term does
> not interact with the quadratic term at all. This is not a problem.
I don't understand this logic, but...
> The unit test code in the previous email tests all possible
> combinations of up to 4 liberty values, so it has been
> empirically verified.
I missed that unit test in the sample code. Sorry.
> > PS: Did you see the solution by Eric Boesch that used bit masking and no
> > random numbers?
>
> I saw it, but I didn't understand it. However, since it does array
> references inside a for loop, it probably does at least as many
> memory accesses as this solution.
Below is the code Eric posted for his test. There are no loops or
memory references.
bool operator()(uint64_t codeSum) const {
return codeSum < mThreshold && !((codeSum/(codeSum/mDivisor)) & mMask);
}
Note that there are two divisions, but these can be eliminated with some
creativity:
bool operator()(uint64_t codeSum) const {
switch(codeSum>>XXX){
case 1:
return true; // 64 bit code
return !(codeSum & mMask); // 32 bit code
case 2:
return !(codeSum & mMaskLeftOne);
case 3:
return ((codeSum&altMaskLeftOne)>>1) == (codeSum&altMask); // 64 bit
return (((codeSum&altMaskLeftOne)>>1) == (codeSum&altMask))
&& !(codeSum & altMaskLeftTwo); // 32 bit
case 4:
return !(codeSum & mMaskLeftTwo);
default:
return false;
}
}
where
mMask = 0b 110 110 110 110...110 11;
mMastLeftOne = mMask<<1 | 1;
mMastLeftTwo = mMask<<2 | 3;
altMask = 0b 001 001 001 001...001 00;
altMaskLeftOne = altMask<<1;
altMaskLeftTwo = altMask<<2;
I know the definition of mMask and altMask isn't legit C, but hopefully
the formatting gives the right idea. Eric gave real code that covers
most of this. All variable names, when matching Eric's, would use the
definition from his code.
The two bits of padding on the right, that I previously suggested, can
be eliminated with this alternate methodology, reducing the minimum
number of bits from 31 to 29, but that still means that overflow is
possible... Creating more strict tests on 32 bit machines. My code
sample gives some duplicate lines of code, the comments indicate which
line is for 32 bit and which is for 64 bit.
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
