bit_manipulation.fast_walsh_hadamard_transform

Fast Walsh-Hadamard Transform (FWHT) for Bitwise Convolutions.

Reference: https://en.wikipedia.org/wiki/Fast_Walsh%E2%80%93Hadamard_transform Reference: https://cp-algorithms.com/algebra/walsh-hadamard-transform.html

Computes bitwise XOR, AND, and OR convolutions of two numeric sequences in O(N log N) time, where N is a positive power of 2.

Functions

and_convolution(→ list[int])	Compute bitwise AND convolution C[k] = sum_{i & j = k} (A[i] * B[j]).
fwht_and(→ list[int])	Perform Fast Walsh-Hadamard Transform for AND operation.
fwht_or(→ list[int])	Perform Fast Walsh-Hadamard Transform for OR operation.
fwht_xor(→ list[int])	Perform Fast Walsh-Hadamard Transform (or inverse) for XOR operation.
or_convolution(→ list[int])	Compute bitwise OR convolution C[k] = sum_{i | j = k} (A[i] * B[j]).
xor_convolution(→ list[int])	Compute bitwise XOR convolution C[k] = sum_{i ^ j = k} (A[i] * B[j]).

Module Contents

bit_manipulation.fast_walsh_hadamard_transform.and_convolution(sequence_a: list[int], sequence_b: list[int]) → list[int]

Compute bitwise AND convolution C[k] = sum_{i & j = k} (A[i] * B[j]).

Time Complexity: O(N log N)

>>> and_convolution([1, 2], [3, 4])
[13, 8]
>>> and_convolution([1, 2], [3])
Traceback (most recent call last):
    ...
ValueError: Input sequences must have equal length.

bit_manipulation.fast_walsh_hadamard_transform.fwht_and(sequence: list[int], inverse: bool = False) → list[int]

Perform Fast Walsh-Hadamard Transform for AND operation.

Time Complexity: O(N log N)

>>> fwht_and([1, 2])
[3, 2]
>>> fwht_and([3, 2], inverse=True)
[1, 2]
>>> fwht_and([1, 2, 3])
Traceback (most recent call last):
    ...
ValueError: Length of sequence must be a positive power of 2.

bit_manipulation.fast_walsh_hadamard_transform.fwht_or(sequence: list[int], inverse: bool = False) → list[int]

Perform Fast Walsh-Hadamard Transform for OR operation.

Time Complexity: O(N log N)

>>> fwht_or([1, 2])
[1, 3]
>>> fwht_or([1, 3], inverse=True)
[1, 2]
>>> fwht_or([1, 2, 3])
Traceback (most recent call last):
    ...
ValueError: Length of sequence must be a positive power of 2.

bit_manipulation.fast_walsh_hadamard_transform.fwht_xor(sequence: list[int], inverse: bool = False) → list[int]

Perform Fast Walsh-Hadamard Transform (or inverse) for XOR operation.

Time Complexity: O(N log N)

>>> fwht_xor([1, 2, 3, 4])
[10, -2, -4, 0]
>>> fwht_xor([10, -2, -4, 0], inverse=True)
[1, 2, 3, 4]
>>> fwht_xor([1, 2, 3])
Traceback (most recent call last):
    ...
ValueError: Length of sequence must be a positive power of 2.
>>> fwht_xor([])
Traceback (most recent call last):
    ...
ValueError: Length of sequence must be a positive power of 2.
>>> fwht_xor([1, 2, 3, 5], inverse=True)
Traceback (most recent call last):
    ...
ValueError: Inverse XOR transform requires elements divisible by sequence length.

bit_manipulation.fast_walsh_hadamard_transform.or_convolution(sequence_a: list[int], sequence_b: list[int]) → list[int]

Compute bitwise OR convolution C[k] = sum_{i | j = k} (A[i] * B[j]).

Time Complexity: O(N log N)

>>> or_convolution([1, 2], [3, 4])
[3, 18]
>>> or_convolution([1, 2], [3])
Traceback (most recent call last):
    ...
ValueError: Input sequences must have equal length.

bit_manipulation.fast_walsh_hadamard_transform.xor_convolution(sequence_a: list[int], sequence_b: list[int]) → list[int]

Compute bitwise XOR convolution C[k] = sum_{i ^ j = k} (A[i] * B[j]).

Time Complexity: O(N log N)

>>> xor_convolution([1, 2], [3, 4])
[11, 10]
>>> xor_convolution([1, 2], [3])
Traceback (most recent call last):
    ...
ValueError: Input sequences must have equal length.