[T3] Duda sobre puntos de representación punto-valor

[ssoliva]

Hola! De clases tengo entendido que lo que hace que la multiplicación utilizando FFT sea O(n) es lo siguiente:

Donde se asume que los puntos v_i son iguales. Lo que me tiene confundido es que en el ejemplo de la implementación adjuntada en el enunciado dan de resultado en el ejemplo:

Donde se repite el punto -2. Esto me lleva a dos preguntas:

1. ¿Es válido que se repita un punto? ¿Cómo podemos asegurar que el resultado de la FFT de los mismos puntos para realizar la multiplicación más fácilmente?
2. Como la multiplicación es de 2n punto valores ¿con qué llenamos los otros puntos si el algoritmo siempre nos entrega n punto valores?

[mc-cari]

Hola,

1. Los valores v_i son las raíces de la unidad y siempre van a ser iguales, por eso siempre se omiten, solo se retornan los valores p(v_i) en números complejos, los cuales son 10, -2 + 2i, -2, -2 -2i.
2. Hay que agregar con cualquier punto valor válido, ya que ya hay suficientes puntos distintos para reconstruir el polinomio. Además los polinomios son los que hay que extender a tamaño 2n tal que 2n sea una potencia de 2, luego el DFT va a resultar en 2n puntos valores.