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/
