Realizar FFT e IFFT utilizando Python3.
Cuando multiplico dos enteros grandes utilizando FFT, encuentro que el resultado de FFT e IFFT nunca es correcto.
Método:
Para realizar FFT, simplemente sigo el pseudocódigo que se muestra aquí: https://i.stack.imgur.com/2IGaf.png
Las ecuaciones de FFT e IFFT son las siguientes. Por lo tanto, al realizar IFFT, solo reemplazo “a” con “y”, reemplazo “omega” con “omega ^ -1” y lo divido por “n”. Y uso “flag” para distinguirlos en mi función.
Para FFT, y será: https://i.stack.imgur.com/wYAiM.png
Para IFFT, a será: https://i.stack.imgur.com/mqzLU.png
Problema:
Para encontrar el problema, trato de comparar los resultados entre numpy.fft y mi función.
- Para FFT. Los resultados de numpy y mi función parecen iguales, pero el signo de las imágenes es el contrario.
-
Para IFFT. Simplemente encuentro que está mal y no puedo encontrar ninguna regla.
Código en Python:
Aquí está mi función de FFT y comparación:
“`python
from typing import List
from cmath import pi, exp
from numpy.fft import fft, ifft
def FFT(a: List, flag: bool) -> List:
“””Realiza DFT usando FFT”””
n = len(a)
if n == 1:
return a
# raíz compleja
omg_n = exp(2 * pi * 1j / n)
if flag:
# IFFT
omg_n = 1 / omg_n
omg = 1
# dividir a en 2 partes
a0 = a[::2] # pares
a1 = a[1::2] # impares
# correspondencia y
y0 = FFT(a0, flag)
y1 = FFT(a1, flag)
# resultado y
y = [
davy.ai
Solución
El problema aquí es que la longitud de entrada no necesariamente es una potencia de 2, lo cual es un requisito para FFT. Como resultado, la salida no es correcta.
Para resolver este problema, debemos rellenar el arreglo de entrada con ceros para que la longitud sea una potencia de 2. Así es como podemos modificar la función
FFT
para manejar esto:Ahora podemos probar esta función en algunas entradas grandes para asegurarnos que la salida sea correcta.