Skip to content

Fast Walsh–Hadamard Transform

Overview

The Walsh transform1 is used in spectral analysis as an alternative to the discrete Fourier transform, and it is widely applied in signal processing. The FFT works with doubles, whereas the Walsh transform decomposes a signal into square waves of different oscillation frequencies, so all its coefficients are integers of the same absolute value. No floating-point multiplication is needed, which makes it faster.

The FWT and the FFT therefore share the same core idea: both transform an array. We write \(FWT[A]\) for the result of applying the fast Walsh transform to an array \(A\).

The core idea of the FWT is this:

We want a new sequence \(C\) that is obtained from the sequences \(A\) and \(B\) by some rule, written \(C = A \cdot B\).

We first apply the forward transform to get \(FWT[A]\) and \(FWT[B]\), then use \(FWT[C]=FWT[A] \cdot FWT[B]\) to compute \(FWT[C]\) in \(O(n)\) time, where \(\cdot\) multiplies the two sequences position by position.

The inverse transform then recovers the sequence \(C\) itself. Altogether this takes \(O(n \log{n})\) time.

In competitive programming, the FWT is the method for convolutions in which a bitwise operation is applied to the indices.

As a formula: \(C_{i} = \sum_{i=j \oplus k}A_{j} B_{k}\)

(where \(\oplus\) is some binary bitwise operation)

Below we take \(\cup\) (bitwise OR), \(\cap\) (bitwise AND) and \(\oplus\) (bitwise XOR) as examples.

FWT for each operation

OR

If \(k=i\cup j\), then the set of positions where \(i\) has a \(1\) bit and the set of positions where \(j\) has a \(1\) bit are both subsets of the set of positions where \(k\) has a \(1\) bit.

To get \(FWT[C] = FWT[A] \cdot FWT[B]\), we have to construct a suitable rule for the FWT.

Following the definition, the natural choice is \(FWT[A]_i = A'_i = \sum_{i=i\cup j}A_{j}\): the sum over every \(j\) whose \(1\) bits form a subset of those of \(i\).

Then:

\[ \begin{aligned} FWT[A]_i\cdot FWT[B]_i&=\left(\sum_{i\cup j=i} A_j\right)\left(\sum_{i\cup k=i} B_k\right) \\ &=\sum_{i\cup j=i}\sum_{i\cup k=i}A_jB_k \\ &=\sum_{i\cup(j\cup k)=i}A_jB_k \\ &= FWT[C]_i \end{aligned} \]

Next, how do we compute \(FWT[A]\)?

Plain enumeration is out of the question: it takes \(O(n^2)\). Since we cannot enumerate over the whole array at once, we turn to divide and conquer.

Split the whole range in half. Once it is halved, the indices written in binary follow a clear pattern.

Let \(A_0\) be the first half of \(A\) and \(A_1\) the second half of the range. In \(A_0\) the highest bit, that of the largest index of \(A\), is \(0\), so the subsets of such an index all lie in \(A_0\) itself (the highest bit being \(0\)). In \(A_1\) the highest bit is \(1\), so the subsets that qualify are not only those in \(A_1\) itself but also those whose highest bit is \(0\). That is,

\[ FWT[A] = merge(FWT[A_0], FWT[A_0] + FWT[A_1]) \]

Here merge joins two arrays end to end, the way strings are concatenated, and \(+\) is ordinary addition, applied to corresponding positions.

With this halving the concatenation is done in \(O(\log{n})\) time, and every concatenation performs the operation once, so we obtain \(FWT[A]\) in \(O(n\log{n})\) time.

Now for the inversion, which is easy. We know that the subsets of \(A_0\) are just its own (\(A_0 = FWT[A_0]\)) and that the subsets of \(A_1\) are \(FWT[A_0] + FWT[A_1]\), so the recurrence for the inverse follows at once:

\[ UFWT[A'] = merge(UFWT[A_0'], UFWT[A_1'] - UFWT[A_0']) \]

The implementation follows. The forward and inverse transforms fit into a single function: pass \(\text{type}=1\) for the forward transform and \(\text{type}=-1\) for the inverse transform.

Implementation
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void Or(ll *a, ll type) {  // iterative implementation, smaller constant factor
  for (ll x = 2; x <= n; x <<= 1) {
    ll k = x >> 1;
    for (ll i = 0; i < n; i += x) {
      for (ll j = 0; j < k; j++) {
        (a[i + j + k] += a[i + j] * type) %= P;
      }
    }
  }
}

AND

By analogy with OR, AND gives similar results:

\[ FWT[A] = merge(FWT[A_0] + FWT[A_1], FWT[A_1]) \]
\[ UFWT[A'] = merge(UFWT[A_0'] - UFWT[A_1'], UFWT[A_1']) \]

The implementation follows. Pass \(\text{type}=1\) for the forward transform and \(\text{type}=-1\) for the inverse transform.

Implementation
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void And(ll *a, ll type) {
  for (ll x = 2; x <= n; x <<= 1) {
    ll k = x >> 1;
    for (ll i = 0; i < n; i += x) {
      for (ll j = 0; j < k; j++) {
        (a[i + j] += a[i + j + k] * type) %= P;
      }
    }
  }
}

XOR

XOR convolution rests on the following fact.

Let \(x\circ y\) denote the parity of the number of \(1\) bits in \(x\cap y\), that is, \(x\circ y=\text{popcnt}(x\cap y)\bmod 2\). Then \((x\circ y)\oplus (x\circ z)=x\circ(y\oplus z)\) follows easily.

The transform \(FWT[A]\) is easy to find as well.

Let \(FWT[A]_i=\sum_{i\circ j=0}A_j-\sum_{i\circ j=1}A_j\). We now verify that \(FWT[C] = FWT[A] \cdot FWT[B]\) holds:

\[ \begin{aligned} FWT[A]_iFWT[B]_i&=\left(\sum_{i\circ j=0}A_j-\sum_{i\circ j=1}A_j\right)\left(\sum_{i\circ k=0}B_k-\sum_{i\circ k=1}B_k\right) \\ &=\left(\sum_{i\circ j=0}A_j\sum_{i\circ k=0}B_k+\sum_{i\circ j=1}A_j\sum_{i\circ k=1}B_k\right)-\left(\sum_{i\circ j=0}A_j\sum_{i\circ k=1}B_k+\sum_{i\circ j=1}A_j\sum_{i\circ k=0}B_k\right) \\ &=\sum_{(j\oplus k)\circ i=0}A_jB_k-\sum_{(j\oplus k)\circ i=1}A_jB_k \\ &=FWT[C]_i \end{aligned} \]

Now let us see how to compute the values of \(A\) and \(B\) quickly. Again we use divide and conquer:

Take the subsequence \(FWT[A_0]\), in which the current bit of \(i\) is \(0\). Under \(\circ\) this bit gives the same result whether it is combined with \(0\) or with \(1\) (because \(0\cap 0=0,0\cap1=0\)), so in \(FWT[A]=\sum_{i\circ j=0}A_j-\sum_{i\circ j=1}A_j\) we have \(\sum_{i\circ j=1}A_j=0\).

Take the subsequence \(A_1\), in which the current bit of \(i\) is \(1\). Under \(\circ\) this bit gives \(0\) when combined with \(0\) and \(1\) when combined with \(1\) (because \(1\cap 0=0,1\cap1=1\)).

Putting the two cases together:

\[ FWT[A]=merge((FWT[A_0]+FWT[A_1])-0, FWT[A_0]-FWT[A_1]) \]

That is:

\[ FWT[A] = merge(FWT[A_0] + FWT[A_1], FWT[A_0] - FWT[A_1]) \]

The inverse transform follows easily:

\[ UFWT[A'] = merge(\frac{UFWT[A_0'] + UFWT[A_1']}{2}, \frac{UFWT[A_0'] - UFWT[A_1']}{2}) \]

Here is the code. Pass \(\text{type}=1\) for the forward transform and \(\text{type}=\frac{1}{2}\) for the inverse transform.

Implementation
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void Xor(ll *a, ll type) {
  for (ll x = 2; x <= n; x <<= 1) {
    ll k = x >> 1;
    for (ll i = 0; i < n; i += x) {
      for (ll j = 0; j < k; j++) {
        (a[i + j] += a[i + j + k]) %= P;
        (a[i + j + k] = a[i + j] - a[i + j + k] * 2) %= P;
        (a[i + j] *= type) %= P;
        (a[i + j + k] *= type) %= P;
      }
    }
  }
}

XNOR

By analogy with XOR, the formulas are:

\(FWT[A]_{i} = \sum_{C_1}A_{j} - \sum_{C_2}A_{j}\) (where \(C_1\) means that the number of bit positions at which the binary representations of \(i\) and \(j\) are both \(0\) is even, and \(C_2\) that this number is odd)

\[ FWT[A] = merge(FWT[A_1] - FWT[A_0], FWT[A_1] + FWT[A_0]) \]
\[ UFWT[A'] = merge(\frac{UFWT[A_1'] - UFWT[A_0']}{2}, \frac{UFWT[A_1'] + UFWT[A_0']}{2}) \]

The FWT from another angle

Let \(c(i,j)\) be the coefficient with which \(A_j\) contributes to \(FWT[A]_i\). The FWT can then be restated as:

\[ FWT[A]_i = \sum_{j=0}^{n-1} c(i,j) A_j \]

Since

\[ FWT[A]_i\cdot FWT[B]_i=FWT[C]_i \]

a short proof gives \(c(i,j)c(i,k)=c(i,j\odot k)\), where \(\odot\) is any bitwise operation.

The function \(c\) has another important property: it can be handled bit by bit.

For example, suppose we compute the transform as:

\[ FWT[A]_i = \sum_{j=0}^{n-1} c(i,j) A_j \]

This is inefficient, so we split the sum:

\[ FWT[A]_i = \sum_{j=0}^{n/2-1} c(i,j) A_j+\sum_{j=n/2}^{n-1} c(i,j) A_j \]

Compare \(i\) and \(j\) in the first sum with those in the second: only the highest bit differs.

So let \(i'\) and \(j'\) be \(i\) and \(j\) with the highest bit removed, and let \(i_0\) be the highest bit of \(i\). Then:

\[ FWT[A]_i = c(i_0,0)\sum_{j=0}^{n/2-1} c(i',j') A_j+c(i_0,1)\sum_{j=n/2}^{n-1} c(i',j') A_j \]

If \(i_0=0\):

\[ FWT[A]_i = c(0,0)\sum_{j=0}^{n/2-1} c(i',j') A_j+c(0,1)\sum_{j=n/2}^{n-1} c(i',j') A_j \]

If \(i_0=1\):

\[ FWT[A]_i = c(1,0)\sum_{j=0}^{n/2-1} c(i',j') A_j+c(1,1)\sum_{j=n/2}^{n-1} c(i',j') A_j \]

In other words, the four numbers

\[ \begin{bmatrix} c(0,0) & c(0,1) \\ c(1,0) & c(1,1) \end{bmatrix} \]

are all we need to carry out the transform. We call this matrix the bit matrix.

The inverse transform needs the inverse of this bit matrix.

If the inverse matrix is \(c^{-1}\), the original values are recovered in the same way:

\[ A_i = \sum_{j=0}^n c^{-1}(i,j) FWT[A]_j \]

The inverse matrix need not exist: a matrix with a row of \(0\)s or a column of \(0\)s, for example, has no inverse. Take particular care when constructing the matrix.

Bitwise OR

We can take:

\[ \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} \]

It satisfies \(c(i,j)c(i,k)=c(i,j\cup k)\). This is exactly the \(FWT[A]=\text{merge}(FWT[A_0], FWT[A_0]+FWT[A_1])\) we derived earlier! The following matrix satisfies the condition too, but the one above is the usual choice:

\[ \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \]

The next matrix also satisfies \(c(i,j)c(i,k)=c(i,j\cup k)\), but it has a row of \(0\)s and hence no inverse, so it is not valid:

\[ \begin{bmatrix} 0 & 0 \\ 1 & 1 \end{bmatrix} \]

The inverse transform requires inverting the matrix. For the topmost matrix this gives:

\[ \begin{bmatrix} 1 & 0 \\ -1 & 1 \end{bmatrix} \]

Then proceed as in the forward transform, with the inverse matrix in place of the original.

Bitwise AND

We can take:

\[ \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \]

It satisfies \(c(i,j)c(i,k)=c(i,j\cap k)\).

Its inverse:

\[ \begin{bmatrix} 1 & -1 \\ 0 & 1 \end{bmatrix} \]

Bitwise XOR

We can take:

\[ \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \]

It satisfies \(c(i,j)c(i,k)=c(i,j\oplus k)\).

Its inverse:

\[ \begin{bmatrix} 0.5 & 0.5 \\ 0.5 & -0.5 \end{bmatrix} \]

The FWT is a linear transformation

The FWT is a linear transformation. That is, it satisfies:

\[ FWT[A+B]=FWT[A]+FWT[B] \]

and:

\[ FWT[c\cdot A]=c\cdot FWT[A] \]

K-dimensional FWT

A bitwise operation is really an operation on \(n\)-dimensional \(\{0,1\}\) vectors. OR takes the \(\max\) in each dimension. AND takes the \(\min\) in each dimension. XOR adds the two values in each dimension and reduces the sum \(\bmod 2\).

Bitwise operations have one distinctive feature: every position of the vector is independent of the others.

What do we get if we extend \(\{0,1\}\) to \([0,K)\cap \mathbf{Z}\), that is, to base \(K\)?

The max operation

Extend \(\cup\) to base \(K\) by defining \(i\cup j\) as the digit-wise \(\max\). Then:

\[ c(i,j)c(i,k)=c(i,j\cup k) \]

For \(j=k\) this becomes:

\[ c(i,j)c(i,j)=c(i,j) \]

So in every row the \(1\)s must come before the \(0\)s; a \(1\) after a \(0\) would be invalid. Working through it by hand turns up a valid construction:

\[ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{bmatrix} \]

Inverting it gives:

\[ \begin{bmatrix} 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{bmatrix} \]

The min operation

Extend \(\cap\) to base \(K\) by defining \(i\cap j\) as the digit-wise \(\min\). Then:

\[ c(i,j)c(i,k)=c(i,j\cap k) \]

For \(j=k\) this becomes:

\[ c(i,j)c(i,j)=c(i,j) \]

So in every row the \(1\)s must come after the \(0\)s; a \(1\) before a \(0\) would be invalid. Working through it by hand turns up a valid construction:

\[ \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

Inverting it gives:

\[ \begin{bmatrix} 1 & -1 & 0 & 0 \\ 0 & 1 & -1 & 0 \\ 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

These two are rarely used. The one that sees the most use is:

Carryless addition

Extend \(\oplus\) to base \(K\) by defining \(i\oplus j\) as digit-wise addition \(\bmod K\). Then:

\[ c(i,j)c(i,k)=c(i,j\oplus k) \]

Taking \(c(i,j)=\omega_{K}^j\) meets the requirement:

\[ \omega_{K}^j\omega_{K}^k=\omega_{K}^{j\oplus k} \]

But a matrix whose rows are all the same has no inverse either, so we take \(c(i,j)=\omega_{K}^{(i-1)j}\) instead.

This gives the matrix:

\[ \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega_{K}^1 & \omega_{K}^2 & \cdots & \omega_{K}^{K-1} \\ 1 & \omega_{K}^2 & \omega_{K}^4 & \cdots & \omega_{K}^{2(K-1)} \\ 1 & \omega_{K}^3 & \omega_{K}^6 & \cdots & \omega_{K}^{3(K-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega_{K}^{K-1} & \omega_{K}^{2(K-1)} & \cdots & \omega_{K}^{(K-1)(K-1)} \end{bmatrix} \]

This is a Vandermonde matrix. Inverting it gives:

\[ \frac{1}{K}\begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega_{K}^{-1} & \omega_{K}^{-2} & \cdots & \omega_{K}^{-(K-1)} \\ 1 & \omega_{K}^{-2} & \omega_{K}^{-4} & \cdots & \omega_{K}^{-2(K-1)} \\ 1 & \omega_{K}^{-3} & \omega_{K}^{-6} & \cdots & \omega_{K}^{-3(K-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega_{K}^{-(K-1)} & \omega_{K}^{-2(K-1)} & \cdots & \omega_{K}^{-(K-1)(K-1)} \end{bmatrix} \]

If a root of unity exists for the modulus given in the problem, this is easy to implement.

But a root of unity may not exist under the given modulus, so we turn to a field extension: we artificially define an \(x\) that satisfies \(x^K=1\) and compute with \(x\) directly. Every number is then a polynomial in \(x\) of degree \(K-1\), and all we have to do is compute \(\bmod {x^K-1}\). The matrix can be written as:

\[ \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & x^1 & x^2 & \cdots & x^{K-1} \\ 1 & x^2 & x^4 & \cdots & x^{2(K-1)} \\ 1 & x^3 & x^6 & \cdots & x^{3(K-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x^{K-1} & x^{2(K-1)} & \cdots & x^{(K-1)(K-1)} \end{bmatrix} \]

This may introduce zero divisors, however, which means that one number has several representations, and we cannot tell what the true value of a number is.

So we stop working \(\bmod {x^K-1}\) and work \(\bmod\) the cyclotomic polynomial \(\Phi_{K}(x)\) instead: modulo it \(x\) has order \(K\), and it is irreducible over \(\mathbb{Q}\). We therefore define the computations above to take place \(\bmod {\Phi_{K}(x)}\).

One problem remains: reducing \(\bmod \Phi_{K}(x)\) has a large constant factor (because \(\Phi\) is itself a polynomial). But since \(\Phi_{K}(x)\mid x^K-1\), it is enough to reduce \(\bmod x^K -1\) during the computation and \(\bmod \Phi_{K}(x)\) only at the very end.

Example problems

[CF 1103E] Radix sum

Given a sequence \(a_1,a_2,...,a_n\) of length \(n\), for every \(p \in [0,n-1]\) find the number of ways to choose an integer sequence \(i_1,i_2,...,i_n\) that satisfies the following conditions, modulo \(2^{58}\):

  • \(\forall j \in [1,n] , i_j \in [1,n]\);
  • \(\sum\limits_{j=1}^n a_{i_j} = p\), where addition is defined as decimal carryless addition.

\(n\le10^5,a_i\le10^5\)

Solution

A DP comes to mind: let the state \(f_{i,s}\) mean that the first \(i\) numbers have been considered and the sum so far is \(s\). Because the FWT is linear, we can first transform to the FWT point-value representation, raise it to the \(n\)-th power, and finally transform back.

So far this is trivial, but the problem gives the modulus \(2^{58}\). No root of unity exists for it, so we use a field extension.

The cyclotomic polynomial here is \(\Phi_{10}(x)=x^4-x^3+x^2-x+1\).

The UFWT, however, has to divide by the base \(10\), and \(10\) has no modular inverse modulo \(2^{58}\). But \(5\) does have an inverse modulo \(2^{58}\), namely \(57646075230342349\), so all that is left is to divide by one more \(2\). Let \(x\) be the answer after dividing by \(5\) and \(y\) the true answer, that is, \(2^5y\equiv x\pmod{2^{64}}\). Clearly \(y\equiv \frac{x}{2^5}\pmod{2^{64-5}}\), that is, \(y\equiv \frac{x}{2^5}\pmod{2^{59}}\), so simply divide the final answer by \(2^5\). Why the problem setter wants the answer modulo \(2^{58}\) is anyone's guess, but one more reduction takes care of that.

[CF103329F] [XXII Opencup, Grand Prix of XiAn] The Struggle

Given an ellipse \(E\) in which every lattice point has coordinates in \([1,4 \cdot 10^6]\), find the value of \(\sum_{(x,y) \in E} (x \oplus y)^{33}x^{-2}y^{-1} \mod 10^9+7\).

Solution

This problem is far from a straightforward application of the FWT. The problem setter has written a detailed editorial in English; see this link.

References


  1. Wikipedia (in Chinese) ↩