k1r1t0's blog

[Tutorial] XOR Convolution without math
By k1r1t0, 8 months ago, In English

Recently I was trying to solve the following problem: 102441E - Очень простая сумма.

In process of solving it, I realised that I need to use xor convolution and just copied FWHT code somewhere from the internet. My solution passed, but I wanted to know how does it work, so started searching info on FWHT and xor convolution.

After some time of going through endless blogs talking about weird matrices and other difficult stuff, I decided to reinvent everything on my own, as I always do. Here I will describe a simple algorithmic way to look at xor convolution, I hope that it doesn't contain any crucial mistakes and will be useful for you.

The Algorithm

Let the size of the arrays be $$$2^n$$$, we want to calculate

$$$C_i = \sum_{j\oplus k=i}{A_j\cdot B_k}$$$

for all $$$0\le i\le 2^n - 1$$$.

If we look at halves of the arrays separately, first half consists of indices with $$$n$$$-th bit set to zero, and the second consists of indices with $$$n$$$-th bit set to one, so the sum becomes

$$$C0_i = \sum_{j\oplus k=i}{A0_j\cdot B0_k+A1_j\cdot B1_k}$$$
$$$C1_i = \sum_{j\oplus k=i}{A0_j\cdot B1_k+A1_j\cdot B0_k}$$$

where $$$X0$$$ is the first half of $$$X$$$ and $$$X1$$$ is the second.

Let's take a look at the xor convolution of $$$A0+A1$$$ and $$$B0+B1$$$:

$$$D0_i=\sum_{j\oplus k=i}{(A0_j+A1_j)(B0_k+B1_k)}=\sum_{j\oplus k=i}{A0_j\cdot B0_k+A0_j\cdot B1_k+A1_j\cdot B0_k+A1_j\cdot B1_k}$$$

OMG! $$$D0_i = C0_i + C1_i$$$, now we just need to somehow get $$$C0$$$ and $$$C1$$$ out of $$$D0$$$. How to make different parts of the sum distinguishable from each other? Just add some minus signs and hope that everything will work out!

$$$D1_i=\sum_{j\oplus k=i}{(A0_j-A1_j)(B0_k-B1_k)}=\sum_{j\oplus k=i}{A0_j\cdot B0_k-A0_j\cdot B1_k-A1_j\cdot B0_k+A1_j\cdot B1_k}$$$

That's really cool. Now we can see that $$$C0_i = \frac{D0_i + D1_i}{2}$$$ and $$$C1_i = \frac{D0_i - D1_i}{2}$$$.

So the final algorithm is to recursively calculate $$$D0$$$ and $$$D1$$$ and then get $$$C0$$$ and $$$C1$$$ from them. There are $$$O(n)$$$ levels of recursion and $$$O(2^n)$$$ operations on each level, which gives us $$$O(n2^n)$$$ recursive algorithm.

Implementation

Iterative Implementation and Interesting Results

Let's implement the same algorithm iterative way by computing everything in place. Also let's divide everything by $$$2^n$$$ in the end instead of dividing by $$$2$$$ every step. The implementation looks like this:

Implementation

It's not hard to see that now the code does the following: transform a to special form; tranform b to special form; calculate c; tranform c from special form;, so you can separate transformations into functions. I'm not sure if you can do more than one multiplication between transformations, but it's still impressive how simple all of this can be.

  • Vote: I like it
  • +231
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

First time i understand what convolution is

Thanks!!

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Also can you do it for other convolutions Also

xor ,or ,and many other

→ Reply
»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Dang this is really clean! I spent some time reading this blog a while ago (https://mirror.codeforces.com/blog/entry/115438) which I also found pretty clean.

It seems FWHT is useless because we can do AND/OR/XOR convolutions without it? I never learned it though, when I looked at some blog about it I was intimidated haha.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I now realize that this IS FWHT :face_palm:

    → Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

Is it possible to do this with xor base 3? (Without the use of complex numbers)

→ Reply