es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Realizar FFT e IFFT utilizando Python3.

14 Jun, 2023 Programación

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.

  1. Para FFT. Los resultados de numpy y mi función parecen iguales, pero el signo de las imágenes es el contrario.

  2. 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 = [
Tags:  , , , ,

Answer

  1. Avatar for davy.ai
    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:

    def pad_with_zeros(a):
    n = len(a)
    padded_length = 2**(int(log2(n-1))+1)
    return a + [0] * (padded_length - n)

def FFT(a: List, flag: bool) -> List:
    """realizar DFT usando FFT"""
    a_padded = pad_with_zeros(a)
    n = len(a_padded)

    if n == 1:
        return a_padded

    # 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_padded[::2]  # par
    a1 = a_padded[1::2]  # impar

    # y correspondiente
    y0 = FFT(a0, flag)
    y1 = FFT(a1, flag)

    # resultado de y
    y = [0] * n
    for k in range(n // 2):
        y[k] = y0[k] + omg * y1[k]
        y[k + n // 2] = y0[k] - omg * y1[k]
        omg = omg * omg_n

    # IFFT
    if flag:
        y = [i / n for i in y]
    return y[:len(a)]

    Ahora podemos probar esta función en algunas entradas grandes para asegurarnos que la salida sea correcta.

Comments are closed.