We studied polynomial multiplication using FFT in class. Recall the algorithm given two polynomials 𝑎(𝑥)=𝑎0+𝑎1𝑥+⋯+𝑎𝑛−1𝑥𝑛

[answerhappygod]

We studied polynomial multiplication using FFT in class. Recallthe algorithm given twopolynomials 𝑎(𝑥)=𝑎0+𝑎1𝑥+⋯+𝑎𝑛−1𝑥𝑛−1a(x)=a0+a1x+⋯+an−1xn−1 and 𝑏(𝑥)=𝑏0+𝑏1𝑥+⋯+𝑏𝑚−1𝑥𝑚−1b(x)=b0+b1x+⋯+bm−1xm−1.

We Studied Polynomial Multiplication Using Fft In Class Recall The Algorithm Given Two Polynomials A X A0 A1x An 1xn 1 (37.46 KiB) Viewed 25 times

Brief Illustration of Numpy fft and ifft functions. from numpy.fft import fft, ifft from numpy import real, imag #fft --> computes fft of a list or numpy array #ifft -> computes inverse fft of list or numpy array # Create a list 1st = [1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1] # Compute its fft fft_1st0 = fft (1ste) print (f'FFT of {1st0} is\n \t {fft_1st0}') # Compute iverse fft ifft_1st0 = ifft(fft_1st0) print (f'After ifft: {ifft_lst0}') # Check that all the imaginary parts are tiny in the ifft result # Note that they will not be zero due to floating point error assert (all([abs(imag(x)) <= 1E-10 for x in ifft_lst0])), 'Something went wrong -- we should not have complex parts to the ifft # Extract the real parts print('Note that we can suppress the vanishingly small complex cofficients') fix_ifft 1st = [real(x) for x in ifft_1st0] print (f'After converting back to float: {fix_ifft_1st0}')
Implement the polynomial_multiply function below. from numpy.fft import fft, ifft from numpy import real, imag def polynomial_multiply(a_coeff_list, b_coeff_list): # Return the coefficient list of the multiplication # of the two polynomials # Returned List must be a list of floating point numbers. # Please convert list from complex to reals by using the # real function in numpy. # your code here
def check_poly(1st1, 1st2): print('‒‒‒‒‒‒‒-') print('Test # 1') # multiply (1 + x a = [1, 1, 0, -1] [2, -1, 1] b = print (f'Your code found: (1st1}') print (f'Expected: {1st2}') assert (len (1st1) len (1st2)), 'Lists have different lengths' for (k,j) in zip(1st1, 1st2): assert abs(k-j)<= 1E-05, 'Polynomials do not match' print('Passed!') # C = polynomial_multiply(a,b) assert (len (c) 6) print(f'c={c}') check_poly(c, [2,1,0,-1,1,-1]) print('-------') == = print('Test # 2') # multiply 1 - x + x^2 + 2 x^3 + 3 x^5 with -x^2 + x^4 + x^6 a = [1, -1, 1, 2, 0, 3] b [0, 0, -1, 0, 1, 0, 1] C = polynomial_multiply (a,b) assert (len(c) print (f'c={c}') == == x^3) with (2 x + x^2) - - check_poly(c, [0, 0, -1, 1, 0, -3, 2, -2, 1, 5, 0, 3]) print('- -----') print('Test # 3') # multiply 1 # with 2 12) 2x^3 + x^7 x^4 x^6 + x^8 == - 11 x^11 a = [1, 0, 0, -2, 0, b [2, 0, 0, 0, -1, 0, -1, 0, 1] 0, 0, 1, 0, 0, 0, -11] C = polynomial_multiply (a, b) assert (len(c) print (f'c={c}') 20) check_poly(c, [2, 0, 0, -4, -1, 0, -1, 4, 1, 2, 0, -25, 0, -1, 0, 12, 0, 11, 0, -11]) print('All tests passed (10 points!)')