Edit page

FFT

Introdução

O seguinte vídeo apresenta contexto histórico e uma pequena intuição do algoritmo:

Daqui em diante define-se polinómio p:CCp:\mathbb{C}\to\mathbb{C} de grau r1r-1 como:

p(c)=a0+a1c+a2c2+a3c3+a4c4++ar1cr1p(c)=a_0+a_1c+a_2c^2+a_3c^3+a_4c^4+\dots+a_{r-1}c^{r-1}

Agora, tomando λ0,λ1,λ2,,λr1C\lambda_0, \lambda_1, \lambda_2,\dots, \lambda_{r-1} \in \mathbb{C}, sabemos que:

p(λ0)=a0+a1λ0+a2λ02+a3λ03++ar1λ0r1p(λ1)=a0+a1λ1+a2λ12+a3λ13++ar1λ1r1p(λ2)=a0+a1λ2+a2λ22+a3λ23++ar1λ2r1p(λr1)=a0+a1λr1+a2λr12+a3λr13++ar1λr1r1p(\lambda_0)=a_0+a_1\lambda_0+a_2\lambda_0^2+a_3\lambda_0^3+\dots+a_{r-1}\lambda_0^{r-1}\\ p(\lambda_1)=a_0+a_1\lambda_1+a_2\lambda_1^2+a_3\lambda_1^3+\dots+a_{r-1}\lambda_1^{r-1}\\ p(\lambda_2)=a_0+a_1\lambda_2+a_2\lambda_2^2+a_3\lambda_2^3+\dots+a_{r-1}\lambda_2^{r-1}\\ \vdots\\ p(\lambda_{r-1})=a_0+a_1\lambda_{r-1}+a_2\lambda_{r-1}^2+a_3\lambda_{r-1}^3+\dots+a_{r-1}\lambda_{r-1}^{r-1}

Igualdades estas que podem ser representadas matricialmente:

[p(λ0)p(λ1)p(λ2)p(λr1)]=[a0a1a2ar1]Vr\begin{bmatrix}p(\lambda_0) & p(\lambda_1) & p(\lambda_2) &\dots & p(\lambda_{r-1})\end{bmatrix} = \begin{bmatrix}a_0& a_1 & a_2 & \dots & a_{r-1}\end{bmatrix}\cdot V_r

Onde VrV_r representa a matriz de Vandermonde. Agora vê-se que as linhas da matriz de Vandermonde devem ser preenchidas com as potências dos respetivos valores de λ\lambda. Ou seja:

Representação matricial

Matriz de Vandermonde=[λ00λ01λ02λ0r1λ10λ11λ12λ1r1λ20λ21λ22λ2r1λr10λr11λr12λr1r1]\text{Matriz de Vandermonde} = \begin{bmatrix} \lambda_0^0 & \lambda_0^1 & \lambda_0^2 & \dots & \lambda_0^{r-1} \\ \lambda_1^0 & \lambda_1^1 & \lambda_1^2 & \dots &\lambda_1^{r-1} \\ \lambda_2^0 & \lambda_2^1 & \lambda_2^2 & \dots &\lambda_2^{r-1} \\ \dots & \dots & \dots & \dots & \dots \\ \lambda_{r-1}^0 & \lambda_{r-1}^1 & \lambda_{r-1}^2 & \dots &\lambda_{r-1}^{r-1} \\ \end{bmatrix}

Chamando então à matriz à esquerda da igualdade YY, à de Vandermonde VrV_r e à dos coeficientes do polinómio XX, vem:

YT=XTVrY^T= X^TV_r

É de notar que a matriz de Vandermonde tem inversa! Assim, é possível chegar aos coeficientes de um polinómio a partir dos seus valores, e vice-versa. Neste problema, a escolha dos valores para os λs\lambda's é a parte mais importante. Escolhemos então valores especiais: as raízes de índice rr da unidade. Porquê? Utilizando estes valores, as contas são imensamente facilitadas, principalmente devido à consequente simetria da matriz de Vandermonde.

Relembrando

Chamam-se a w0,w1,w2,w3,,wr1,wr(=1)w^0, w^1, w^2, w^3,\dots, w^{r-1}, w^r(=1), as raízes de índice r da unidade, onde a raiz principal pode ser obtida através da fórmula:

w=ei2πr=cis(2πr)=cos(2πr)+isin(2πr)w=e^{i\frac{2\pi} r}=\operatorname{cis}\left(\frac{2\pi} r\right) = \cos\left(\frac {2\pi}{r}\right)+i\sin\left(\frac{2\pi} r\right)

Para r=16r=16:

Raízes de índice 16 da unidade

Assim, utilizando esta notação, a matriz de Vandermonde viria:

[1w0w02w03w0r11w1w12w13w1r11w2w22w23w2r11wr1wr12wr13wr1r1]\begin{bmatrix} 1 & w_0 & w_0^2 & w_0^3 & \dots & w_{0}^{r-1}\\ 1 & w_1 & w_1^2 & w_1^3 & \dots & w_{1}^{r-1}\\ 1 & w_2 & w_2^2 & w_2^3 & \dots & w_{2}^{r-1}\\ \dots & \dots & \dots & \dots & \dots &\dots \\ 1 & w_{r-1} & w_{r-1}^2 & w_{r-1}^3 & \dots & w_{r-1}^{r-1}\end{bmatrix}

ou seja, a raiz de Vandermonde para as raízes de índice 4 da unidade viria:

V4=[11111i1i11111i1i]V_4=\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i\\1 & -1 & 1 & -1 \\ 1 & -i & -1 & i\end{bmatrix}

Construção da inversa

Repara-se que, aproveitando-se da simetria nestes casos:

XT=YTVr1X=(VrT)1Y=Vr1YX^T= Y^T V_r^{-1} \Leftrightarrow X=(V_r^T)^{-1}Y = V_r^{-1}Y

tomando agora proveito da progressão geométrica, vem:

ρr1ρ1=1+ρ+ρ2++ρr1(ρr1)=(ρ1)(1+ρ+ρ2++ρr1)Sabendo que ρr=1, vem:ρ=1ou1+ρ+ρ2++ρr1=0\frac{\rho^r-1}{\rho-1} = 1+\rho+\rho^2+\dots+\rho^{r-1} \Leftrightarrow\\ (\rho^r-1)=(\rho-1)(1+\rho+\rho^2+\dots+\rho^{r-1})\Leftrightarrow \\\text{Sabendo que }\rho^r=1, \text{ vem:} \\ \rho=1\quad \text{ou}\quad 1+\rho+\rho^2+\dots+\rho^{r-1}=0

Como a raiz principal nunca é 1, descobrimos que a soma de todas as raízes de índice rr da unidade devem dar 0.

Tome-se então, a multiplicação entre uma linha de uma matriz de Vandermonde com uma coluna de uma outra matriz de Vandermonde, vem:

[1wkw2kw3kw(r1)k][1wjw2jw3jw(r1)j]=1+wkj+w2(kj)+w3(kj)++w(r1)(kj)\begin{bmatrix} 1 & w^k & w^{2k} & w^{3k} & \dots & w^{(r-1)k}\end{bmatrix} \cdot \begin{bmatrix} 1 \\ w^{-j} \\ w^{-2j} \\ w^{-3j} \\ \vdots \\ w^{-{(r-1)}j}\end{bmatrix} = \\ 1+w^{k-j} + w^{2(k-j)} + w^{3(k-j)} + \dots + w^{(r-1)(k-j)}

É de notar que, apesar de ww ser um complexo, como todos estes valores para ww têm módulo 1, o seu inverso equivale ao conjugado.

Agora, expandindo este pensamento para matrizes em vez de colunas/linhas, percebe-se que o resultado será uma matriz preenchida por rr (1+1+1+1...) se k=jk=j (na diagonal) e 0 caso contrário. Ou seja:

VrVr=rInVr1=1rVrV_r \cdot V_r^\dagger = rI_n \Leftrightarrow V_r^{-1} = \frac 1 r V_r^\dagger

Onde VrV_r^\dagger simboliza a matriz composta por todos os valores de VrV_r original, mas conjugados.

Ou seja,

X=1rVr(w)YX=\frac 1 r V_r(w)^\dagger Y

Para mais sobre as utilidades da matriz de Vandermonde, podem ver este vídeo.

Reversão e Matrizes de Fourier

Antes de passar à multiplicação de polinómios pela FFT, é necessário introduzir alguns conceitos essenciais que levaram à descoberta deste algoritmo.

Reversão


Função dada por:

Revk:{0,1}k{0,1}k\operatorname{Rev}_k : \{0,1\}^k \rightarrow \{0,1\}^k

Consiste em transformar uma palavra binária, de kk componentes, na sua simétrica.

Exemplos
  1. Seja k=4k = 4
    Rev4(1010)=0101\operatorname{Rev}_4(1010) = 0101

  1. Seja k=3k = 3
    Rev3(101)=101\operatorname{Rev}_3(101) = 101

É como colocar um "espelho" no final da palavra. O resultado é a sua reflexão,

n0n1nk1  nk1n1n0n_0n_1 \dots n_{k-1}\ |\ n_{k-1}\dots n_1n_0

Também se pode aplicar Revk\operatorname{Rev}_k a matrizes com 2k2^k colunas.
Segue-se um exemplo onde aplicamos a uma matriz 22×222^2\times2^2 genérica.

Rev2{[a0,0a0,1a0,2a0,3a1,0a1,1a1,2a1,3a2,0a2,1a2,2a2,3a3,0a3,1a3,2a3,3]}==Rev2{[a0,00a0,01a0,10a0,11a1,00a1,01a1,10a1,11a2,00a2,01a2,10a2,11a3,00a3,01a3,10a3,11]}=[a0,00a0,10a0,01a0,11a1,00a1,10a1,01a1,11a2,00a2,10a2,01a2,11a3,00a3,10a3,01a3,11]\operatorname{Rev}_2\left\{\begin{bmatrix}a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} \\ a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,0} & a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,0} & a_{3,1} & a_{3,2} & a_{3,3} \\\end{bmatrix}\right\} = \\ = \operatorname{Rev}_2\left\{\begin{bmatrix}a_{0,00} & a_{0,01} & a_{0,10} & a_{0,11} \\ a_{1,00} & a_{1,01} & a_{1,10} & a_{1,11} \\ a_{2,00} & a_{2,01} & a_{2,10} & a_{2,11} \\ a_{3,00} & a_{3,01} & a_{3,10} & a_{3,11} \\\end{bmatrix}\right\} \\ = \begin{bmatrix}a_{0,00} & a_{0,10} & a_{0,01} & a_{0,11} \\ a_{1,00} & a_{1,10} & a_{1,01} & a_{1,11} \\ a_{2,00} & a_{2,10} & a_{2,01} & a_{2,11} \\ a_{3,00} & a_{3,10} & a_{3,01} & a_{3,11} \\\end{bmatrix}

Note-se que a Reversão é apenas aplicada aos índices das colunas.
Através deste exemplo, é possível concluir que em matrizes 22×222^2\times2^2, esta aplicação é equivalente a trocar as duas colunas do meio.
É fácil verificar que isto é verdade para todas as matrizes com dimensão n×22n\times 2^2, com n1n\geq 1.

Matriz de Permutação

Seja PkP_k a Matriz de Permutação, e IkI_k a matriz identidade, ambas de dimensão 2k×2k2^k\times 2^k,

Pk=Revk{Ik}ePk2=PkPk=IkP_k = \operatorname{Rev}_k\{I_k\} \\ \text{e} \\ P_k^2 = P_kP_k = I_k
Exemplos
P2=Rev2{[1000010000100001]}P2=[1000001001000001]P_2 = \operatorname{Rev}_2\left\{\begin{bmatrix}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}\right\} \Leftrightarrow \\ P_2 = \begin{bmatrix}1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}

Matriz Diagonal de Fourier

Dk=[w00000w10000w20000w2k1]D_k = \begin{bmatrix} w_0 & 0 & 0 & \dots & 0 \\ 0 & w_1 & 0 &\dots & 0 \\ 0 & 0 & w_2 & \dots & 0 \\\dots & \dots & \dots & \dots & \dots \\ 0 & 0 & 0 & \dots & w_{2^k-1}\end{bmatrix}

Representada por DkD_k, é uma matriz diagonal de dimensão 2k×2k2^k \times 2^k, onde a sua diagonal é constituída pelas primeiras 2k2^k raízes índices 2k+12^{k+1}.

Exemplo
  1. Sendo k=2k=2, as primeiras 222^2 raízes índice 232^3 da unidade são:
e0i2π23=1,e1i2π23=22+i22,e2i2π23=i,e3i2π23=22+i22 e^{0i\cdot\frac{2\pi}{2^3}} = 1 ,\quad e^{1i\cdot\frac{2\pi}{2^3}} = \frac{\sqrt{2}}{2} + i\frac{\sqrt{2}}{2},\quad e^{2i\cdot\frac{2\pi}{2^3}} = i,\quad e^{3i\cdot\frac{2\pi}{2^3}} = -\frac{\sqrt{2}}{2} + i\frac{\sqrt{2}}{2}

logo

D2=[1000022+i220000i000022+i22]D_2 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & \frac{\sqrt{2}}{2} + i\frac{\sqrt{2}}{2} & 0 & 0 \\ 0 & 0 & i & 0 \\ 0 & 0 & 0 & -\frac{\sqrt{2}}{2} + i\frac{\sqrt{2}}{2}\end{bmatrix}

Matriz de Fourier

Fk(w)F_k(w), a Matriz de Fourier de dimensão 2k×2k2^k\times2^k, é dada por:

Fk(w)=νk(w)PkF_k(w) = \nu_k(w) \cdot P_k

onde

  • ww é a raiz principal da unidade, com:
    w=ei2π2k=cos(2π2k)+isin(2π2k)w = e^{i\frac{2\pi}{2^k}} = \cos\left(\frac {2\pi}{2^k}\right)+i\sin\left(\frac{2\pi} {2^k}\right)
  • PkP_k é a Matriz de Permutação de ordem kk
  • νk(w)\nu_k(w) equivalente à Matriz de Vandermonde Vr(w)V_r(w), tal que 2k=r2^k=r.

Em suma, é o produto da Matriz de Permutação pela Matriz de Vandermonde.


Define-se, agora, os problemas de Valoração e Interpolação, com base na Matriz de Fourier.

Valoração
Y=νk(w)X=νk(w)PkPk1X=(νk(w)Pk)(PkX)=Fk(w)(PkX)\begin{aligned} Y &= \nu_k(w)X \\ &= \nu_k(w)P_kP_k^{-1}X \\ &= (\nu_k(w)P_k)(P_kX) \\ &= F_k(w)(P_kX) \end{aligned}
Interpolação
X=1rνk(w)Y=1rνk(w)PkPkY=1rνk(w)PkPkY=1r(νk(w)Pk)(PkY)=1rFk(w)(PkY)=1rFk(w)(PkY)=1r[Fk(w)(PkY)]=1rFk(w)(PkY)\begin{aligned} X &=\frac 1 r \nu_k(w)^\dagger Y \\ &= \frac 1 r \nu_k(w)^\dagger P_kP_kY \\ &= \frac 1 r \nu_k(w)^\dagger P_k^\dagger P_k^\dagger Y \\ &= \frac 1 r (\nu_k(w) P_k)^\dagger (P_kY^\dagger)^\dagger\\ &= \frac 1 r F_k(w)^\dagger (P_kY^\dagger)^\dagger \\ &= \frac 1 r F_k(w)^\dagger (P_kY^\dagger)^\dagger\\ &= \frac 1 r [F_k(w) (P_kY^\dagger)]^\dagger\\ &= \frac 1 r F_k(w) (P_kY^\dagger) \end{aligned}

Teorema de Cooley e Tukey

Para todo o kN0k \in \N_0, a Matriz de Fourier Fk(w)F_k(w) admite a seguinte definição recursiva:

F0(1)=1Fk+1=[Fk(w2)DkFk(w2)Fk(w2)DkFk(w2)]F_0(1) = 1 \\ F_{k+1} = \begin{bmatrix}F_k(w^2) & D_kF_k(w^2)\\ F_k(w^2) & -D_kF_k(w^2)\end{bmatrix}

Esta estrutura recursiva é a base do algoritmo FFT.

Multiplicação de polinómios - FFT

Exemplo
p1(n)=n+1p2(n)=3n+2q(n)=p1(n)×p2(n)p_1(n) = n + 1 \\ p_2(n) = 3n+2 \\ q(n) = p_1(n) \times p_2(n)

Queremos determinar q(n)q(n)

Passo 1
Como ambos os polinómios têm grau 11, o seu produto terá grau 22 (1+1)(1+1) e no máximo 33 componentes (grau+1)(\text{grau}+1). Assim, o menor kNk \in \N tal que 2k32^k \geq 3 é 22.
Logo, iremos usar vetores de dimensão 222^2 para representar os polinómios.
Assim, o primeiro polinómio é representado por (1,1,0,0)(1,1,0,0) e o segundo por (2,3,0,0)(2,3,0,0).
Passo 2
Aplicar Revk\operatorname{Rev}_k, com k=2k=2

0001101100011011(1,1,0,0)(2,3,0,0)(1,0,1,0)(2,0,3,0)\begin{matrix} 00 & 01 & 10 & 11 && 00 & 01 & 10 & 11 \\ (1, & 1, & 0, & 0) && (2, & 3, & 0, & 0) \\ (1, & 0, & 1, & 0) && (2, & 0, & 3, & 0) \end{matrix}

Passo 3

F2(i)[1010]=[F1(1)D1F1(1)F1(1)D1F1(1)][1010]=[[1111][10]+[100i][1111][10][1111][10][100i][1111][10]]=[[11]+[100i][11][11][100i][11]]=[21+i01i]F_2(i) \begin{bmatrix}1\\0\\1\\0\end{bmatrix}= \begin{bmatrix}F_1(-1) & D_1F_1(-1)\\ F_1(-1) & -D_1F_1(-1)\end{bmatrix}\begin{bmatrix}1\\0\\1\\0\end{bmatrix}\\ = \begin{bmatrix} \begin{bmatrix}1&1\\1&-1\end{bmatrix} \begin{bmatrix}1\\0\end{bmatrix}+ \begin{bmatrix}1 & 0 \\ 0 & i\end{bmatrix} \begin{bmatrix}1&1\\1&-1\end{bmatrix} \begin{bmatrix}1\\0\end{bmatrix}\\ \begin{bmatrix}1&1\\1&-1\end{bmatrix} \begin{bmatrix}1\\0\end{bmatrix}- \begin{bmatrix}1 & 0 \\ 0 & i\end{bmatrix} \begin{bmatrix}1&1\\1&-1\end{bmatrix}\begin{bmatrix}1\\0\end{bmatrix} \end{bmatrix}\\ =\begin{bmatrix} \begin{bmatrix}1\\1\end{bmatrix}+\begin{bmatrix}1 & 0 \\ 0 & i\end{bmatrix}\begin{bmatrix}1\\1\end{bmatrix}\\ \begin{bmatrix}1\\1\end{bmatrix}-\begin{bmatrix}1 & 0 \\ 0 & i\end{bmatrix}\begin{bmatrix}1\\1\end{bmatrix} \end{bmatrix}\\ =\begin{bmatrix}2\\1+i\\0\\1-i\end{bmatrix}

Relembrar que (2,1+i,0,1i)(2,1+i,0,1-i) são os valores de p1(n)p_1(n) substituindo nn pelas raízes de índice 222^2 da unidade: (1,i,1,i)(1,i,-1,-i)

F2(i)[2030]=[F1(1)D1F1(1)F1(1)D1F1(1)][2030]=[[1111][20]+[100i][1111][30][1111][20][100i][1111][30]]=[[22]+[100i][33] [22][100i][33]]=[52+3i123i]F_2(i) \begin{bmatrix}2\\0\\3\\0\end{bmatrix}= \begin{bmatrix}F_1(-1) & D_1F_1(-1)\\ F_1(-1) & -D_1F_1(-1)\end{bmatrix}\begin{bmatrix}2\\0\\3\\0\end{bmatrix}\\ = \begin{bmatrix} \begin{bmatrix}1&1\\1&-1\end{bmatrix} \begin{bmatrix}2\\0\end{bmatrix}+ \begin{bmatrix}1 & 0 \\ 0 & i\end{bmatrix} \begin{bmatrix}1&1\\1&-1\end{bmatrix} \begin{bmatrix}3\\0\end{bmatrix}\\ \begin{bmatrix}1&1\\1&-1\end{bmatrix} \begin{bmatrix}2\\0\end{bmatrix}- \begin{bmatrix}1 & 0 \\ 0 & i\end{bmatrix} \begin{bmatrix}1&1\\1&-1\end{bmatrix}\begin{bmatrix}3\\0\end{bmatrix} \end{bmatrix}\\ =\begin{bmatrix} \begin{bmatrix}2\\2\end{bmatrix}+\begin{bmatrix}1 & 0 \\ 0 & i\end{bmatrix}\begin{bmatrix}3\\3\end{bmatrix}\\~\\ \begin{bmatrix}2\\2\end{bmatrix}-\begin{bmatrix}1 & 0 \\ 0 & i\end{bmatrix}\begin{bmatrix}3\\3\end{bmatrix} \end{bmatrix}\\ =\begin{bmatrix}5\\2+3i\\-1\\2-3i\end{bmatrix}

Passo 4
Calcula-se o produto componente a componente.

(2,1+i,0,1i)(5,2+3i,1,23i)==(10,1+5i,0,15i)(2,1+i,0,1-i) \otimes (5,2+3i,-1,2-3i) = \\ =(10, -1+5i,0, -1-5i)

Estes são os valores do polinómio produto, ainda desconhecido, nos pontos 1,i,1,i1,i,-1,-i.

Passo 5
Conjugamos os valores do produto obtido, e aplicamos mais uma vez Rev2\operatorname{Rev}_2

(10,1+5i,0,15i)(10,15i,0,1+5i)(10,15i,0,1+5i)(10,0,15i,1+5i)(10,-1+5i,0,-1-5i) \rightarrow (10,-1-5i,0,-1+5i) \\ \\ \begin{matrix} (10, & -1-5i, & 0, & -1+5i) \\ (10, & 0, & -1-5i, & -1+5i) \end{matrix}

Passo 6

F2(i)[10015i1+5i]=[F1(1)D1F1(1)F1(1)D1F1(1)][10015i1+5i]=[[1111][100]+[100i][1111][15i1+5i][1111][100][100i][1111][15i1+5i]]=[[1010]+[100i][210i][1010][100i][210i]]=[820120]F_2(i) \begin{bmatrix}10\\0\\-1-5i\\-1+5i\end{bmatrix}= \begin{bmatrix}F_1(-1) & D_1F_1(-1)\\ F_1(-1) & -D_1F_1(-1)\end{bmatrix}\begin{bmatrix}10\\0\\-1-5i\\-1+5i\end{bmatrix}\\ = \begin{bmatrix} \begin{bmatrix}1&1\\1&-1\end{bmatrix} \begin{bmatrix}10\\0\end{bmatrix}+ \begin{bmatrix}1 & 0 \\ 0 & i\end{bmatrix} \begin{bmatrix}1&1\\1&-1\end{bmatrix} \begin{bmatrix}-1-5i\\-1+5i\end{bmatrix}\\ \begin{bmatrix}1&1\\1&-1\end{bmatrix} \begin{bmatrix}10\\0\end{bmatrix}- \begin{bmatrix}1 & 0 \\ 0 & i\end{bmatrix} \begin{bmatrix}1&1\\1&-1\end{bmatrix}\begin{bmatrix}-1-5i\\-1+5i\end{bmatrix} \end{bmatrix}\\ =\begin{bmatrix} \begin{bmatrix}10\\10\end{bmatrix}+\begin{bmatrix}1 & 0 \\ 0 & i\end{bmatrix}\begin{bmatrix}-2\\-10i\end{bmatrix}\\ \begin{bmatrix}10\\10\end{bmatrix}-\begin{bmatrix}1 & 0 \\ 0 & i\end{bmatrix}\begin{bmatrix}-2\\-10i\end{bmatrix} \end{bmatrix}\\ =\begin{bmatrix}8\\20\\12\\0\end{bmatrix}

Passo 7
Conjuga-se e divide-se o resultado por 22=42^2=4.

(8,20,12,0)(2,5,3,0)(8,20,12,0) \rightarrow (2,5,3,0)

Podemos concluir:

q(n)=2+5n+3n2q(n) = 2 + 5n + 3n^2

ATENÇÃO: Como os polinómios iniciais tinham valores inteiros e reais, o polinómio produto também terá. Se o resultado não for inteiro ou real, nestes casos, houve um erro de contas.


Para exemplos com k=3k = 3, consultar os slides disponibilizados na Página da Cadeira.