Fast Walsh–Hadamard transform

In computational mathematics, the Hadamard ordered fast Walsh–Hadamard transform is an efficient algorithm to compute the Walsh–Hadamard transform. A naive implementation of the WHT of order would have a computational complexity of O(). The FWHT_h requires only additions or subtractions.
The FWHT_h is a divide-and-conquer algorithm that recursively breaks down a WHT of size into two smaller WHTs of size. This implementation follows the recursive definition of the Hadamard matrix :
The normalization factors for each stage may be grouped together or even omitted.
The sequency-ordered, also known as Walsh-ordered, fast Walsh–Hadamard transform, FWHT_w, is obtained by computing the FWHT_h as above, and then rearranging the outputs.
A simple fast nonrecursive implementation of the Walsh–Hadamard transform follows from decomposition of the Hadamard transform matrix as, where A is m-th root of.

Python example code

import math
def fwht -> None:
"""In-place Fast Walsh–Hadamard Transform of array a."""
assert math.log2.is_integer, "length of a is a power of 2"
h = 1
while h < len:
# perform FWHT
for i in range:
for j in range:
x = a
y = a
a = x + y
a = x - y
# normalize and increment
a /= math.sqrt
h *= 2