Nice work!
I've convinced myself that what you're doing will work. If you
sacrifice the two least significant bits for zero padding, you can avoid
"code_sum % pseudoliberty_count == 0" check.
On Wed, 2007-11-14 at 21:02 -0500, Eric Boesch wrote:
> Sorry, I didn't mean to send that one yet. I pressed tab, meaning to
> print a tab character, and return soon after, which caused gmail to,
> first, change the focus to the "send" button, and second, send the
> mail. That last bit was supposed to be
>
> if (code_sum < 5 * threshold) {
> int pseudoliberty_count = code_sum / threshold;
> if (code_sum % pseudoliberty_count == 0) {
> int average = code_sum / pseudoliberty_count;
> if (average is in my original code_value set) then there is
> just one liberty.
> }
> }
>
> The "if average is in my original code_value set" seems like a
> bottleneck here, requiring about #bits (i.e. about 9, since 361 is a
> 9-bit number) operations no matter how you do it as far as I can tell
> (unless you use a stupidly gigantic lookup table), and there's a
> solution to that, too, if you don't mind wasting a little more space.
> Use base 8 instead of base 5. Unfortunately, then it is no longer
> possible (without using a separate pseudoliberty count) to squeeze the
> result into a 32-bit number and be sure that, for chains with 19
> liberties, for example, you don't get overflow. But it does permit
> using a bitmask to convert the "in my original code_value set" test to
> constant-time:
>
> if ((average & 0b110110110110110110110110110) == 0) { then there
> is just one liberty }
>
> Here, 0b<foo> is the binary number foo (yes, I know that's not
> legitimate C code) and I'm supposing that #bits == 9. I hope I got
> this right -- I'm sort of hurrying to correct it before anybody wasted
> too much time trying to decode it. (Sorry, Jason :)
>
> On 11/14/07, Eric Boesch <[EMAIL PROTECTED]> wrote:
> > Encode each number by swapping base 2 with base 5, without changing
> > the digits. So binary 11011 (27) is represented as base-5 11011 (756).
> > This allows you to sum up to 4 such numbers without experiencing
> > overflow from one digit to the next (since 4 1's adds up to just 4).
> > Essentially, you are performing b additions in parallel. If the
> > numbers you are summing are all the same, and the pseudoliberty count
> > (#libs) is no more than 4, then each base-5 digit of the sum will
> > equal 0 or #libs.
> >
> > With a slight modification, you can also eliminate the pseudoliberty
> > count completely and just use a single number. Take the largest code
> > value you will need, add 1, multiply by four, round up to the next
> > power of 5, and add this value to every code value, and now you can
> > just use the test
> >
> _______________________________________________
> computer-go mailing list
> [email protected]
> http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
