La Transformée De Fourier Rapide
J'ai besoin de multiplier deux polynômes de chaque ayant de petits intégrale des coefficients. J'ai besoin d'un rapide FFT routine en C/C++ qui peut convolution. J'ai vu plusieurs bibliothèques, mais ils semblent être trop grand, réparties sur plusieurs fichiers. Ce qui est important est que je besoin de code qui n'est pas trop long et peut être très facilement utilisé et compilés en un seul .c/.cpp fichier.
- FFT doit être optimisé pour des entrées réelles, au moins, si pas de petits nombres.
- Radix 4 mise en œuvre si disponible serait bien aussi.
- De la compilation, il ne devrait pas prendre compilation spéciale des drapeaux de compilation de programme qui doit être fait dans un environnement externe qui je ne peux pas contrôler.
Un bien correspond à mes besoins est ici. Mais j'ai besoin de quelque chose deux fois plus vite.
Quelle est votre question? J'ai besoin d'un million de dollars. Aussi, j'aime le fromage. BEAUCOUP.
Réel polynôme de convolution est un problème important en lui-même, et donc je pense qu'il est naturel de poser cette question. Je n'ai pas besoin de toute la puissance de la FFT, mais pour un petit sous-ensemble et le fait qu'il s'AGIT d'un OS de la mise en œuvre presque répondant à mes besoins, signifie qu'il n'est pas irréaliste.
De quelle taille sont les polynômes? La FFT a mieux la complexité de convolution directe, mais aussi beaucoup plus constante, pour les petits problèmes de convolution directe serait plus rapide.
Assez grande. Degré est autour de 10^6. J'en suis sûr, un temps O(N^2) l'algorithme ne fonctionne pas dans un délai raisonnable.
Réel polynôme de convolution est un problème important en lui-même, et donc je pense qu'il est naturel de poser cette question. Je n'ai pas besoin de toute la puissance de la FFT, mais pour un petit sous-ensemble et le fait qu'il s'AGIT d'un OS de la mise en œuvre presque répondant à mes besoins, signifie qu'il n'est pas irréaliste.
De quelle taille sont les polynômes? La FFT a mieux la complexité de convolution directe, mais aussi beaucoup plus constante, pour les petits problèmes de convolution directe serait plus rapide.
Assez grande. Degré est autour de 10^6. J'en suis sûr, un temps O(N^2) l'algorithme ne fonctionne pas dans un délai raisonnable.
OriginalL'auteur Nikhil Garg | 2011-03-10
Vous devez vous connecter pour publier un commentaire.
Pour un simple et facile à utiliser FFT la mise en œuvre d'essayer KissFFT. Si vous avez besoin d'absolu, un maximum de performance si, et ne me dérange pas un peu de complexité, alors, il doit être FFTW.
OriginalL'auteur Paul R
J'ai adapté la
smbFftfonction de ce exemple sur DspDimension à mes besoins dans le passé.OriginalL'auteur LnxPrgr3
J'ai recueilli certains de mes principaux résultats de la recherche que de la forme ou de la plupart d'ajustement à la question (C/C++ FFT), et j'ai généralement organisées du plus simple au plus complexe:
N'hésitez pas à ajouter ou mettre à jour la liste.
OriginalL'auteur Andrew