maths.radix2_fft

Fast Polynomial Multiplication using radix-2 fast Fourier Transform.

Classes

FFT	Fast Polynomial Multiplication using radix-2 fast Fourier Transform.

Module Contents

class maths.radix2_fft.FFT(poly_a=None, poly_b=None)

Fast Polynomial Multiplication using radix-2 fast Fourier Transform.

Reference: https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm#The_radix-2_DIT_case

For polynomials of degree m and n the algorithms has complexity O(n*logn + m*logm)

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)

__dft(which)

__multiply()

__str__()

c_max_length

len_A

len_B

polyA

polyB

product

root