bit_manipulation.fast_walsh_hadamard_transform
==============================================

.. py:module:: bit_manipulation.fast_walsh_hadamard_transform

.. autoapi-nested-parse::

   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
---------

.. autoapisummary::

   bit_manipulation.fast_walsh_hadamard_transform.and_convolution
   bit_manipulation.fast_walsh_hadamard_transform.fwht_and
   bit_manipulation.fast_walsh_hadamard_transform.fwht_or
   bit_manipulation.fast_walsh_hadamard_transform.fwht_xor
   bit_manipulation.fast_walsh_hadamard_transform.or_convolution
   bit_manipulation.fast_walsh_hadamard_transform.xor_convolution


Module Contents
---------------

.. py:function:: 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.


.. py:function:: 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.


.. py:function:: 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.


.. py:function:: 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.


.. py:function:: 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.


.. py:function:: 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.