Algorithme Toom-Cook

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Caractères cyrilliques Cette page contient des caractères cyrilliques. En cas de problème, consultez Aide:Unicode ou testez votre navigateur.
image illustrant l’informatique
Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

L'algorithme Toom-Cook, plus particulièrement Toom-3, est un algorithme de multiplication dû à Andrei Toom (en) et Stephen Cook, utilisé pour multiplier deux grands nombres. Ces grands nombres sont découpés en plus petits nombres sur lesquels on effectuera les calculs. C'est un raffinement de l'algorithme de Karatsuba.

Description[modifier | modifier le code]

Multiplier deux nombres revient à multiplier deux polynômes

et

ce qui donne un troisième polynôme

En l'évaluant en cinq points

ses coefficients peuvent être déterminés

Ce calcul nécessite cinq multiplications trois fois plus simples et quelques additions

La complexité est donc

.

Références[modifier | modifier le code]