Multiplication de polynômes utilisant la FFT

Problème : Calculer le produit de deux polynômes de manière efficace. Solution : import numpy from numpy.fft import fft, ifft def poly_mul(p1, p2): """Multiplier deux polynômes. p1 et p2 sont des tableaux de coefficients dans l'ordre des degrés croissants.""" deg1 = p1.shape[0] - 1 deg2 = p2.shape[0] - 1 # devrait être p2, pas p1 # Serait 2*(deg1 + deg2) + 1, mais le prochain puissance de 2 gère le +1 total_num_pts = 2 * (deg1 + deg2) next_power_of_2 = 1 << (total_num_pts - 1).bit_length()