Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
Discussion fermée
#1 26-01-2009 14:41:16
- sinuspax
- Membre
- Inscription : 19-08-2008
- Messages : 47
Algorithme de Karatsuba
C'est une méthode permettant de multiplier plus rapidement deux nombres.
L'astuce consiste à trouver, par différence, la somme des produits intermédiaires. De cette façon, si nous multplions deux nombres, trois produits seront utilisés au lieu de quatre avec la méthode classique.
Ex :
26 x 34
2 x 3 = 6
6 x 4 = 24
(2 - 6) x (3 - 4) = 4
On peut faire aussi :
(2 + 6) x (3 + 4) = 56 (qui est la somme totale des produits). Mais la soustraction est plus économique que l'addition sur les grands nombres.
Résultat final :
6 x 100 + (6 + 24 - 4) x 10 + 24 = 600 + 260 + 24 = 884.
Ou :
6 x 100 + (56 - 24 + 6) x 10 + 24 = 600 + 260 + 24 = 884.
682 x 253 devient :
68 x 25
2 x 3
(68 - 2) x (25 - 3) = 66 x 22
68 x 25
6 x 2 = 12
8 x 5 = 40
(6 - 8) x (2 - 5) = 6
12 x 100 + (12 + 40 - 6) x 10 + 40 = 1700
66 x 22
6 x 2 = 12
6 x 2 = 12
(0) x (0) = 0
12 x 100 + (12 + 12) x 10 + 12 = 1452
D'où :
68 x 25 = 1700
2 x 3 = 6
(68 - 2) x (25 - 3) = 66 x 22 = 1452
1700 x 100 + (1700 + 6 - 1452) x 10 + 6 = 172546
Beaucoup de petits calculs, mais une réelle efficacité sur le plan informatique.
Sinus
Hors ligne
Pages : 1
Discussion fermée