Categorias
Fast Fourier Transform (FFT)
Para multiplicar dois polinômios em O (nlogn) tempo.
Neste artigo, vou descrever a multiplicação de dois polinômios em O (nlogn) tempo. Este utiliza o algoritmo Fast Fourier Transform (FFT).
O livro "Introdução aos Algoritmos" por Cormen, Leiserson e Rivest descreve a multiplicação de dois polinômios em O (nlogn) tempo. Aqui, vou descrever uma variante do método que eles usaram.
Em primeiro lugar, uma revisão sobre alguns princípios básicos:
- A (x) = a_1 + a_0 (x) + a_2 (x ^ 2 )+.....+ a_ (n-1) (x ^ (n-1)) é um polinômio de grau n-1. Periodicidade: w^(k+n)=w^k.
- A multiplicação de polinômios A (x) e B (x), ou seja, C (x) = A (x) B (x) leva O (n ^ 2) tempo.
- Para encontrar A (p) substitui-se p em vez de x no polinômio:
A(p) = a_1 + a_0 (p^2 )+.....+ a_ (n-1) (p^(n-1)).
Isto, segundo a regra de Horner é:
A(p) = p + a_0 (a_1 + p(p a_2 +.....+ (a_ (n-1 ))...). Isto leva
O (n). - Existem dois tipos de representações de polinômios:
Forma coeficiente: (a_0, a_1, a_2,....., a_ (n-1)).
Forma ponto-valor: {(x_0,y_0),(x_1,y_1),...(x_n-1, y_n-1)}, em que y(x_i) = A(x_i). - A conversão do coeficiente para ponto-valor toma formas O (n^2), mesmo sobre o uso da regra Horner, porque o valor de A(x) tem de ser encontrado a n pontos.
- A complexa raiz da unidade é um número complexo w * tal que w*^n=1.
- As raízes n da unidade são: w^0,w^1,w^2,....,w^n-1.
w=e^(2*pi*i/n) é chamado de raiz principal da unidade e todas as raízes n são competências deste w.
Com esta Informação de base podemos começar.
Para multiplicar dois polinômios A(x) e B(x), dadas em formas de coeficientes, primeiro convertemo-las para formas ponto-valor. Multiplicação em forma de ponto-valor leva a forma O (n^2).
Então convertemos de volta para a forma coeficiente.
No entanto, a conversão de coeficiente para ponto-valor leva O (n^2) tal como foi dito no ponto 5. Porém, sobre como escolher os pontos x_0, x_1 ,..... x_ (n-1) com cuidado, podemos alcançar este em O (nlogn).
Estes pontos que iremos escolher vão ser as raízes de n da unidade. Isto é o que é o Discrete Fourier Transform (DFT).
Agora, A(x)=a_0 + a_1(x) + a_2(x^2) + .....+a_(n-1)(x^(n-1)).
Esta pode ser dividida em dois polinômios: o primeiro contendo os primeiros termos n/2 e o segundo contendo os segundos termos n/2. O livro "Introdução aos Algoritmos" descreve a divisão e até mesmo os termos ímpares. Aqui, podemos chegar ao mesmo resultado, mas somente em uma forma ligeiramente diferente.
Então tomamos A_0(x) = a_0 + a_1(x) + a_2(x^2)+......+ a_(n/2-1)(x^(n/2-1))
e A_1(x) = a_(n/2) + a_(n/2+1)(x) + a_(n/2+2)(x^2)+......+a_(n-1)(x^(n/2-1)).
Assim, podemos escrever A(x) como
A(x)=A_0(x) + x^(n/2)A_1(x)-----------> (1).
Agora, substituindo w em lugar de x, vemos que x^(n/2) na equação (1) torna-se
(x^(n/2)) = (w^(n/2)) = +1,-1, ou seja, as duas raízes da unidade.
Podemos decimar as amostras em duas amostras de termos pares ou ímpares.
O ponto n-DFT inteiro tornou-se agora dois DFTs ponto n/2.
Estes dois DFTs ponto n/2 pode ainda ser dividido em dois DFTs ponto n/4, e assim por diante. Daí, a complexidade do algoritmo resultante ser O (nlogn).
Na abordagem descrita na "Introdução aos Algoritmos", as amostras são divididas em amostras pares e ímpares para obter as primeiras e segundas meias-amostras, exatamente opostas ao que obtivemos presentemente.
O algoritmo recursivo pode ser dado como:
Recursivo_FFT(a){
se(n=1) retornar a
w <- e^(2*pi*i/n)
a[0] <- (a_0,a_1,......,a_(n/2-1))
a[1] <- (a_n/2,a_(n/2 + 1),........,a_(n-1))
y[0] <- Recursivo_FFT(a[o])
y[1] <- Recursivo_FFT(a[1])
para k <- 0 to n/2 -1
começar
y_2k <- y_k[0] + y_k[1]
y_2k+1 <- y_k[0] - y_k[1]
final
retornar y
}
A equação recorrente é: T(n) = 2T(n/2) + O(n), se levarmos O(n) para cada chamada recursiva. Assim, T(n) = O(nlogn).
Assim que chegamos à forma de ponto-valor, podemos realizar a multiplicação em O(n) tempo.
A conversão de ponto-valor para a forma de coeficiente pode ser feita de forma semelhante em O(nlogn). Isto é chamado de interpolação.
Todo o processo de multiplicação tem, pois, O(nlogn).