Multiplicando inteiros com Fast Fourier Transform - FFT

Aviso: O objetivo destas notas não é fornecer um algoritmo para multiplicar inteiros e, sim, explanar de maneira concisa (e não muito detalhada) o embasamento teórico desta aplicação do FFT.

Você pode entender os computadores modernos simplesmente como grandes e poderosas calculadoras. A capacidade de memória e a velocidade com que estas máquinas realizam cálculos gigantescos é realmente incrível. Por trás disso tudo, existe muita matemática e engenharia. Se você já procurou entender como que um computador realiza seus cálculos, deve ter notado que existem ideias simples e geniais por trás de seus algoritmos.

Mesmo assim, o advento da criptografia RSA (só para dar um exemplo), exigiu que pudéssemos trabalhar com números inteiros muito grandes. Muito grandes mesmo!  Para ter uma ideia, dê uma olhada na lista dos maiores primos de Mersenne  conhecidos atualmente e você terá uma noção da ordem de grandeza destes números. Estamos falando de milhões de dígitos. A coisa é tão feia que, para esrever um programa que realize operações com estes números, é preciso utilizar uma biblioteca especial (existem várias bibliotecas com este propósito).

Mas o problema é mais em baixo. Multiplicar dois números é um processo extremamente custoso para um computador! Acredite, se você utilizar um algoritmo comum para multiplicar dois números com a ordem de grandeza mencionada anteriormente, terá que esperar sentado durante um bom tempo. Vamos entender mais ou menos o porquê.

Sejam e dois inteiros de dígitos, representados na base (usualmente, num computador, ). De forma geral, o produto de por é dado por

Assim, para computar o produto temos de realizar cerca de (isto é ) multiplicações entre os coeficientes da representação de e na base e depois somá-las da forma adequada. Assim, efetuar o produto "usual'' entre dois inteiros num computador se torna um processo extremamente lento quando é grande. Para contornar esta situação vamos apresentar a matemática por trás de um algoritmo para multiplicar inteiros cuja complexidade é da ordem de . Existem outros algoritmos, mas este é um dos melhores.

Para compreender o que segue você precisará saber (se você não sabe, o Google sabe, use-o!):

• Álgebra Linear. Por exemplo, você deve saber o que é uma Matriz de Vandermonde, ortogonalidade e produto interno de vetores com entradas em .
• Raízes da unidade.
• Complexidade de algoritmos (pouca coisa, basicamente só saber o que é Big O).

Lema. Dados pontos em com abscissas distintas, só existe um único polinômio de grau tal que o gráfico passa por estes pontos.

Demonstração. Expresse os pontos como solução de um sistema linear onde as incógnitas são os coeficientes do polinômio. A matriz deste sistema será uma Matriz de Vandermonde invertível.

Em outras palavras, dados , o lema acima nos diz que, se conhecemos com , para um polinômio de grau , então, de alguma forma, conhecemos os coeficientes de Resta saber que pontos escolher. Esta é a ideia central da Transformada Discreta de Fourier (FFT).

Seja , . Definimos a matriz por

 

No lema seguinte, se é uma matriz complexa, denota a transposta conjugada de (isto é, a matriz adjunta).

Lema. A matriz complexa como definida acima é uma matriz ortogonal. Além disso, .

Demonstração. Primeiramente, note que

Denote a coluna de por . Se , então é dado por

pois . Note que o denominador pois . Por outro lado, .

A multiplicação de inteiros pelo FFT consiste em escolher uma base para representar estes inteiros e interpretar os dígitos como coeficientes de um polinômio. Digamos então que nossos inteiros são representados por e e realizamos a multiplicação . Com algumas ressalvas, os coeficientes de serão os dígitos da multiplicação dos inteiros (na realidade, os coeficientes do produto podem, eventualmente, ser maiores que a base e teríamos que rearranjar os coeficientes). Suponha que o grau de seja menor que ; para determinar , faremos

para 's distintos. Estes 's serão justamente as -ésimas raízes da unidade. Se organizarmos os coeficiente de (recip. ) num vetor (recip. ), então avaliar o polinômio nos 's é o mesmo que realizar a multiplicação

A priori faremos multiplicações novamente, mas o truque consiste em fatorar de forma a realizar menos multiplicações, é exatamente a isto que damos o nome de Transformada Rápida de Fourier (ou FFT, em inglês).

Antes de exibirmos a fatoração, façamos algumas definições. Para , denotaremos por a matriz de permutação que, aplicada num vetor, posiciona todas as coordenadas ímpares nas primeiras entradas e depois as pares, isto é

Por exemplo, para , a matriz é da forma

Se é par, e é como acima (isto é, ), definimos

Feito isto, temos o grandioso

Teorema. Seja e , para algum , então

 

onde é a matriz identidade de ordem e

Demonstração. Seja , com . Vamos mostrar que

Multiplicando por , obtemos

Agora, se e , então

Por fim, se , então (note que e, assim, )

Observação 1. Talvez você tenha notado que, para a demonstração deste teorema, não precisamos do fato de ser uma potência de 2, bastaria que fosse um número par. Isto realmente não é necessário para esta demonstração. Porém, na prática, o algoritmo é repetido diversas vezes e o tamanho das matrizes é sempre dividido pela metade, assim, sempre trabalhamos com alguma potência de 2 suficientemente grande.

Observação 2. Para sentir como funciona a coisa, tente fazer um exemplo para . Isto é, monte a matriz (neste caso ) e depois fatore ela segundo o teorema acima.

Em princício, para multiplicar por um vetor temos de realizar multiplicações. Mas, após fatorar , temos agora que realizar apenas

multiplicações, pois não precisamos contar a matriz de permutação, nem as matrizes identidade, e só precisa ser contada uma vez. O próximo passo seria repetir um processo análogo e fatorar as duas matrizes . Como é uma -ésima potência de 2, podemos repetir esta fatoração vezes e, assim, reduzimos drasticamente o número de multiplicações, como mostrará o teorema a seguir. É isso que torna o FFT um algoritmo tão eficiente.

Teorema. Nas condições do teorema acima, o número de multiplicações realizadas é .

Demonstração. Na realidade, após realizar o processo vezes (este não é arbitrário, lembre que ) faremos exatamente multiplicações. Existem diversas formas de realizar este cálculo. Aqui, vou utilizar o jeito mais ingênuo possível. Começamos com multiplicações. Seja o número de multiplicações realizadas após fatorarmos vezes. Assim,

• [1ª interação]
• [2ª interação]
• [3ª interação]
• ...

Já dá para ter uma ideia do que está acontecendo. Por indução, é fácil mostrar que . Iremos parar justamente na -ésima interação, pois estamos sempre dividindo por . Logo

Opa, algo está errado, não chegamos ao que queríamos! Mas a conta está certa; o fato é que, depois de realizarmos operações, a matriz dos 's será uma matriz identidade, pois, no final, teremos somente em todas as entradas da diagonal. No entanto, está contando esta matriz, mas é claro que não precisamos contá-la, pois ela não faz nada. Logo a complexidade final é dada por .

O próximo problema seria achar a tranformada inversa, ou seja, obter os coeficientes do polinômio resultante da multiplicação. Em geral, inverter uma matriz é um processo custoso, mas inverter é fácil, pois um dos primeiros lemas acima nos garante que ela é ortogonal e, mais que isso, sua inversa é dada por . Como sabemos fatorar de forma eficiente, realizamos um processo análogo para fatorar a sua transposta conjugada e, assim, obter a multiplicação de dois inteiros numa velocidade de ordem .

Isto é tudo. A Transformada Discreta de Fourier tem inúmeras outras aplicações que, por hora, fogem do propósito deste post. Se você se interessou e quer saber um pouco mais sobre o assunto, seguem alguns links (todos em inglês): Video Aula sobre FFT de Gilbert Strang, Discrete Fourier Transform, Fast Fourier Transform, Livro online sobre Transformada Discreta de Fourier.

Referências:

- "Introduction to Linear Algebra'', Gilbert Strang.
- "Primos de Mersenne (e outros primos muito grandes)'', Carlos Gustavo T.A. Moreira e Nicolau C. Saldanha.