8
Necesito multiplicar dos polinomios, cada uno con coeficientes integrales pequeños. Necesito una rutina rápida de FFT en C/C++ que pueda convolucionarlos. He visto varias bibliotecas, pero parecen ser demasiado grandes repartidas en varios archivos. Lo que es importante es que necesito un código que no sea demasiado largo y pueda ser utilizado y compilado muy fácilmente en un solo archivo .c/.cpp.Transformada rápida de Fourier
- FFT debe optimizarse para entradas reales al menos si no enteros pequeños.
- La implementación de Radix 4, si está disponible, también estaría bien.
- La compilación no debería tener indicadores de compilación especiales, ya que la compilación del programa debe realizarse en un entorno externo que no puedo controlar.
Una que coincide muy bien con mis necesidades es here. Pero necesito algo dos veces más rápido.
¿Cuál es tu pregunta? Necesito un millón de dólares. Además, me gusta el queso. MUCHO. –
@muntoo - La convolución polinomial real es un problema importante en sí mismo y, por tanto, creo que es natural formular esta pregunta. No necesito pleno poder de FFT, sino solo un pequeño subconjunto específico y el hecho de que HAY una implementación de sistema operativo que se ajusta a mis necesidades, significa que tampoco es poco realista. –
¿Qué tan grandes son los polinomios? La FFT tiene mejor complejidad que la convolución directa, pero también una constante significativamente más alta, para pequeños problemas la convolución directa sería más rápida. –