Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(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

Pied de page des forums