Explain the fast Walsh–Hadamard transform in simple steps or pseudocode I've read that the fast Walsh–Hadamard transform is a way to efficiently calculate the linearity/non-linearity of an S-box. Can I get a description of it in simple steps or pseudocode that is restricted to simpler notation and terminology?
The fast Walsh-Hadamard transform algorithm generally applies to Hadamard matrices $H_n$ which are of dimension $2^n\times 2^n, n\geq 1$. Using row and column transpositions, $H_n$ can be arranged so that it is of the form
$$H_n = \left[\begin{matrix}H_{n-1}&amp; H_{n-1}\\H_{n-1}&amp; -H_{n-1}\end{matrix}\right].$$ As a special case, note that
$$H_1 = \left[\begin{matrix}+1&amp; +1\\+1&amp; -1\end{matrix}\right].$$

Now, the Hadamard transform of the (row) vector $\mathbf x$ of length $2^n$
is the row vector $\mathbf xH$ where, if we partition $\mathbf x$ as the
concatenation of $2^{n-1}$-vectors $\mathbf x_L$ and $\mathbf x_R$
$\bigr($that is, $\mathbf x = \big[\mathbf x_L, \mathbf x_R\big]\bigr)$, then we can write
$$\mathbf xH = \big[\mathbf x_L, \mathbf x_R\big]\left[\begin{matrix}H_{n-1}&amp; H_{n-1}\\H_{n-1}&amp; -H_{n-1}\end{matrix}\right]
= \big[\mathbf x_LH_{n-1}+\mathbf x_RH_{n-1}, \mathbf x_LH_{n-1} - \mathbf x_RH_{n-1}\big].$$
This suggests that if we have already computed $\mathbf x_LH_{n-1}$ and $\mathbf x_RH_{n-1}$, we can compute $\mathbf xH$ in $2^n$ more additions/subtractions. So, we can proceed recursively, partitioning $\mathbf x_L$ into $\big[\mathbf x_{LL}, \mathbf x_{LR}\big]$ and 
$\mathbf x_R$ into $\big[\mathbf x_{RL}, \mathbf x_{RR}\big]$, and 
repeat the above calculations with shorter vectors,.... 

Pseudocode
would be something like

recursive function FHT$(\mathbf x)$
begin
partition $\mathbf x$ into two equal-length parts $\mathbf x_L$ and $\mathbf x_R$
$\mathbf y_L$ = FHT$(\mathbf x_L)$; $\mathbf y_R$ = FHT$(\mathbf x_R)$
return $\big[\mathbf y_L+\mathbf y_R,\mathbf y_L-\mathbf y_R\big]$.
end   

The total number of additions/subtractions is $n2^n$; there are no multiplications needed