A Galois week

Codeforces returned this week with its Round 534 on Tuesday (problems, results, top 5 on the left, analysis). mnbvmar won not just thanks to being the only contestant to solve the hardest problem E, but also thanks to being much faster than his peers on the first three problems, which might've been the key to unlocking the strategy of solving E instead of D. Well done!

TopCoder SRM 748 on Saturday wrapped up the second stage of the race to TCO19 (problems, results, top 5 on the left, my screencast, analysis). tourist was the only one able to solve the hard problem, but he also had the fastest time on both the easy and the medium. Congratulations on the very convincing victory!

The hard problem has introduced me to the concept of nim multiplication which, on one side, allows solving products of coin turning games, and on the other side, together with the nim addition — bitwise xor — induces a finite field of characteristic 2 over the nimbers less than 2²ⁿ for any n. I find this sudden appearance of finite fields exceedingly beautiful :)

The Wikipedia article implies that for computing the nim multiplication, we just need the following two facts:

1. The nim product of a Fermat power of two (numbers of the form 2²ⁿ) with a smaller number is equal to their ordinary product;
2. The nim square of a Fermat power of two x is equal to 3x/2 as evaluated under the ordinary multiplication of natural numbers.

It took me quite some time to understand how to compute the nim multiplication using those facts, but now I think I got it, so I'll try to explain (also, does anybody have a link to where this is explained nicely? I could not find one).

First, suppose we know the nim products of powers of two. Then we can use the fact that we have a field to compute all other products by representing the multipliers as xors (nim-sums) of powers of two, for example (where all additions and multiplications are the nim ones): 3*6=(2+1)*(4+2)=2*4+2*2+1*4+1*2=8+3+4+2=8+4+1=13.

Now, the above rules allow to multiply Fermat powers of two, but we need to learn to multiply arbitrary powers of two. Here we once again use the binary representation, this time of the exponent, to represent any power of two as a (both nim and ordinary) product of Fermat powers of two, and then rely on associativity of multiplication to rearrange the Fermat powers of two in sorted order. If they're all distinct, then we can go from smallest to largest to learn that their product is equal to their ordinary product according to the first rule above; and if a Fermat power is repeated, then we use the second rule above to effectively decompose the problem into two. If we always apply the second rule to the smallest repeated power, I think we never end up with more than two occurrences of any power in our intermediate computations.

Here's an example: 2048*128=(256*4*2)*(16*4*2)=2*2*4*4*16*256=(1+2)*4*4*16*256=4*4*16*256+2*4*4*16*256=(2+4)*16*256+2*(2+4)*16*256=2*16*256+4*16*256+2*2*16*256+2*4*16*256=2*16*256+4*16*256+(1+2)*16*256+2*4*16*256=2*16*256+4*16*256+16*256+2*16*256+2*4*16*256=4*16*256+16*256+2*4*16*256=16384+4096+32768=53248.

Those two ideas can be combined to obtain a single algorithm as described in the exercise 4 at the bottom of page 14 in this article from 1978.

Thanks for reading, and check back next week!