Repository: TheAlgorithms/Python
File: maths/radix2_fft.py (Python)

Code before:

    The main part of the algorithm is split in two parts:
        1) __DFT: We compute the discrete fourier transform (DFT) of A and B using a
        bottom-up dynamic approach -
        2) __multiply: Once we obtain the DFT of A*B, we can similarly
        invert it to obtain A*B

    The class FFT takes two polynomials A and B with complex coefficients as arguments;
    The two polynomials should be represented as a sequence of coefficients starting
    from the free term. Thus, for instance x + 2*x^3 could be represented as
    [0,1,0,2] or (0,1,0,2). The constructor adds some zeros at the end so that the
    polynomials have the same length which is a power of 2 at least the length of
    their product.

    Example:

    Create two polynomials as sequences
    >>> A = [0, 1, 0, 2]  # x+2x^3
    >>> B = (2, 3, 4, 0)  # 2+3x+4x^2

    Create an FFT object with them
    >>> x = FFT(A, B)

    Print product
    >>> x.product  # 2x + 3x^2 + 8x^3 + 4x^4 + 6x^5
    [(-0-0j), (2+0j), (3-0j), (8-0j), (6+0j), (8+0j)]

    __str__ test
    >>> print(x)
    A = 0*x^0 + 1*x^1 + 2*x^0 + 3*x^2
    B = 0*x^2 + 1*x^3 + 2*x^4
    A*B = 0*x^(-0+0j) + 1*x^(2+0j) + 2*x^(3+0j) + 3*x^(8+0j) + 4*x^(6+0j) + 5*x^(8+0j)
    """

    def __init__(self, poly_a=None, poly_b=None):
        # Input as list
        self.polyA = list(poly_a or [0])[:]
        self.polyB = list(poly_b or [0])[:]

        # Remove leading zero coefficients
        while self.polyA[-1] == 0:
            self.polyA.pop()
        self.len_A = len(self.polyA)

        while self.polyB[-1] == 0:
            self.polyB.pop()
        self.len_B = len(self.polyB)

        # Add 0 to make lengths equal a power of 2
        self.c_max_length = int(
            2 ** np.ceil(np.log2(len(self.polyA) + len(self.polyB) - 1))

Review comment (suggestion):
# CAREFUL REVIEW PLEASE!
## I cannot explain the required changes to `maths/radix2_fft.py`

@KirilBangachev Are you able to help us understand why Python 3.14 pre-release  is returning different test results than Python < 3.14?
* #1166

Code after:

    The main part of the algorithm is split in two parts:
        1) __DFT: We compute the discrete fourier transform (DFT) of A and B using a
        bottom-up dynamic approach -
        2) __multiply: Once we obtain the DFT of A*B, we can similarly
        invert it to obtain A*B

    The class FFT takes two polynomials A and B with complex coefficients as arguments;
    The two polynomials should be represented as a sequence of coefficients starting
    from the free term. Thus, for instance x + 2*x^3 could be represented as
    [0,1,0,2] or (0,1,0,2). The constructor adds some zeros at the end so that the
    polynomials have the same length which is a power of 2 at least the length of
    their product.

    Example:

    Create two polynomials as sequences
    >>> A = [0, 1, 0, 2]  # x+2x^3
    >>> B = (2, 3, 4, 0)  # 2+3x+4x^2

    Create an FFT object with them
    >>> x = FFT(A, B)

    Print product
    >>> x.product  # 2x + 3x^2 + 8x^3 + 6x^4 + 8x^5
    [(-0-0j), (2+0j), (3-0j), (8-0j), (6+0j), (8+0j)]

    __str__ test
    >>> print(x)
    A = 0*x^0 + 1*x^1 + 0*x^2 + 2*x^3
    B = 2*x^0 + 3*x^1 + 4*x^2
    A*B = (-0-0j)*x^0 + (2+0j)*x^1 + (3-0j)*x^2 + (8-0j)*x^3 + (6+0j)*x^4 + (8+0j)*x^5
    """

    def __init__(self, poly_a=None, poly_b=None):
        # Input as list
        self.polyA = list(poly_a or [0])[:]
        self.polyB = list(poly_b or [0])[:]

        # Remove leading zero coefficients
        while self.polyA[-1] == 0:
            self.polyA.pop()
        self.len_A = len(self.polyA)

        while self.polyB[-1] == 0:
            self.polyB.pop()
        self.len_B = len(self.polyB)

        # Add 0 to make lengths equal a power of 2
        self.c_max_length = int(
            2 ** np.ceil(np.log2(len(self.polyA) + len(self.polyB) - 1))