Algorithme Toom-Cook

Étant donné deux nombres m et n en base b, on commence par choisir une nouvelle base B = bⁱ afin que le nombre de chiffres en base B de m et n soit au plus k (par exemple 3 pour Toom-3). Un choix usuel est :

${\displaystyle i=\max \left\{\left\lfloor {\frac {\lfloor \log _{b}m\rfloor }{k}}\right\rfloor ,\left\lfloor {\frac {\lfloor \log _{b}n\rfloor }{k}}\right\rfloor \right\}+1.}$

Ainsi on peut définir les polynômes dont ces chiffres correspondent à leurs coefficient, c'est-à-dire :

${\displaystyle P(x)=\sum _{i=0}^{k-1}m_{i}x^{i},}$

${\displaystyle Q(x)=\sum _{i=0}^{k-1}n_{i}x^{i}.}$

On remarque que P(B) = m et Q(B) = n, ainsi si on effectue le produit des polynômes pour avoir R(x) = P(x) · Q(x) alors l’évaluation de ce produit en B coïncide avec le produit recherché: R(B) = m·n.

Maintenant que nous avons défini les polynômes P et Q, calculer leur produit se fait par la méthode d’évaluation-interpolation. Pour cela on va évaluer le résultat du polynôme produit R en plusieurs points que l'on utilisera ensuite afin de l'interpoler et donc d'en trouver les coefficients.

Comme P et Q sont de degrés (k − 1), alors leur produit est de degré (2 · k − 2). Par exemple dans le cas de Toom-3, le produit de P et Q est de degré 4, il nous faut donc 5 points pour en calculer l’interpolation. Le choix des points importe peu, il suffit de garantir que l'interpolation est possible (ce qui sera rappelé dans la section Interpolation). Par exemple pour Toom-3, les points traditionnellement choisis sont ${\displaystyle 0,1,-1,2,\infty }$.

Ainsi ces évaluations sur P nous donne :

${\displaystyle P(0)=m_{0},}$

${\displaystyle P(1)=m_{2}+m_{1}+m_{0},}$

${\displaystyle P(-1)=m_{2}-m_{1}+m_{0},}$

${\displaystyle P(2)=4\cdot m_{2}+2\cdot m_{1}+m_{0},}$

${\displaystyle P(\infty )=m_{2}.}$

On procède de manière similaire pour Q.

Une fois qu'on a nos différentes évaluations, il est alors possible de calculer ${\displaystyle R(a_{i})=P(a_{i})\cdot Q(a_{i})}$ pour chaque point d'évaluation a_i. Dans le cas de Toom-3, on rappelle que ces points sont ${\displaystyle (a_{i})_{0\leq i\leq 4}=(0,1,-1,2,\infty )}$. Comme on multiplie deux nombres de taille l, on peut réappliquer récursivement notre algorithme pour calculer ces sous-produits.

Une fois qu'on a nos valeurs r_i pour i compris entre 0 et 2k - 2, on peut alors réécrire les relations entre P, Q et R de manière matricielle. Pour plus de clarté on explicitera le cas k = 3:

${\displaystyle {\begin{pmatrix}R(0)\\R(1)\\R(-1)\\R(2)\\R(\infty )\end{pmatrix}}={\begin{pmatrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\\1&2&4&8&16\\0&0&0&0&1\end{pmatrix}}{\begin{pmatrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{pmatrix}}.}$

Cette matrice de passage correspondant à une matrice de Vandermonde, il suffisait alors de prendre des points deux à deux distincts pour qu'elle soit inversible. Ce qui se traduit alors par :

${\displaystyle {\begin{pmatrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{pmatrix}}={\begin{pmatrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\\1&2&4&8&16\\0&0&0&0&1\end{pmatrix}}^{-1}{\begin{pmatrix}R(0)\\R(1)\\R(-1)\\R(2)\\R(\infty )\end{pmatrix}}.}$

En calculant cet inverse, on obtient alors :

${\displaystyle {\begin{pmatrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{pmatrix}}={\begin{pmatrix}1&0&0&0&0\\-{\frac {1}{2}}&1&-{\frac {1}{3}}&-{\frac {1}{6}}&2\\-1&{\frac {1}{2}}&{\frac {1}{2}}&0&-1\\{\frac {1}{2}}&-{\frac {1}{2}}&-{\frac {1}{6}}&{\frac {1}{6}}&-2\\0&0&0&0&1\end{pmatrix}}{\begin{pmatrix}R(0)\\R(1)\\R(-1)\\R(2)\\R(\infty )\end{pmatrix}}.\qquad (1)}$

Finalement, il ne nous reste plus qu'à évaluer la valeur de ${\displaystyle R(B)=\sum _{i=0}^{2k-2}r_{i}B^{i}}$ afin d'obtenir le résultat du produit. Comme B est une puissance de notre base de travail b, cela se fait simplement à l'aide d'additions avec retenue.