calculer res [i + j] = a [i] * b [j] dans Nlg (N) [duplicate] - algorithme, fft, convolution

Duplication possible:
Algorithme de convolution rapide

J'ai deux tableaux a et b de longueur N. Je veux calculer le tableau de résultat comme

res[i+j] += a[i]*b[j]

Est-il possible de calculer cela en utilisant FFT ou quelque chose de similaire dans le temps plus rapide que N ^ 2. J'ai déjà vu cette question Convolution rapide 1D sans FFT mais je ne suis pas sûr de savoir comment faire cela en utilisant FFT.

EG: A=[1,2,3],B[2,4,6]
res[3] = A[1]*B[2]+A[2]*B[1]

Merci d'avance

Réponses:

De ce que je comprends, vous voulez l’algorithme FFT. ici vous avez une implémentation de cet algorithme, ainsi qu'une bonne explication sur la façon de mettre en œuvre l'algorithme FFT.