précédent | suivant | table des matières

Multiplication des entiers

(application)

Algorithme de l'école

Soient deux entiers de n et m chiffres. La multiplication de ces 2 entiers apprise à l’école primaire est un algorithme de coût proportionnel à n×m.

Algorithme de Karatsuba

A. Karatsuba and Yu Ofman,
Multiplication of Many-Digital Numbers by Automatic Computers.
Doklady Akad. Nauk SSSR Vol. 145 (1962),
pp. 293–294. Translation in Physics-Doklady 7 (1963), pp. 595–596.

L’algorithme de Karatsuba est une application du principe « diviser pour régner » : 

Soient a et b deux nombres de 2k=n chiffres. On a :

et

donc : 

Exemple : 23*46=1058 1 8 2 4 8 1 0 5 8

Les temps de calcul sont donc donnés par la récurrence : 

Faisons l’hypothèse

on a alors : 





et donc

et

soit

Algorithme Toom-Cook

Dans l'algorithme de Karatsuba les nombres sont coupés en deux, l'algorithme de Toom-Cook (version en anglais) les coupe en trois.

haut de la page