À vos marques, préparez-vous, multipliez !

La façon dont vous avez appris à multiplier fonctionne, mais les ordinateurs utilisent un algorithme plus rapide.

Cet été, des lignes de bataille ont été tracées pour un simple problème de mathématiques : 8 ÷ 2(2 + 2) = ? Si vous divisez d’abord 8 par 2, vous obtenez 16, mais si vous multipliez 2 par (2 + 2) en premier, vous obtenez 1. Alors, quelle est la bonne réponse ? Le conflit a pris une telle ampleur qu’il a fait les pages du New York Times. Et comme le montre la section des commentaires, même un mathématicien professionnel qui s’est penché sur la question n’a pas suffi à rapprocher les deux parties.

Le problème ici est simplement la façon dont nous interprétons le symbole de la division. Est-ce que ÷ signifie diviser par un nombre juste après ou par tout ce qui suit ? Ce n’est pas une grande préoccupation pour la plupart des mathématiciens, car ils n’utilisent pas ce symbole très souvent. Demandez-leur de résoudre ce problème et ils feront probablement de tout cela un problème de multiplication : Une fois que vous aurez choisi de l’écrire sous l’une des formes suivantes

l’ambiguïté a disparu et la réponse est claire. En tant que question de multiplication, ce n’est pas particulièrement intéressant.

Mais une question de multiplication que les mathématiciens trouvent intéressante peut vous surprendre : Quelle est la meilleure façon de se multiplier ?

Supposons qu’on vous demande de multiplier 25 et 63. Si vous êtes comme la plupart des gens, vous prendriez probablement une calculatrice. Mais si vous ne pouviez pas en trouver un, vous utiliseriez probablement l’algorithme standard que vous avez appris à l’école primaire, en multipliant chaque chiffre d’un chiffre par chaque chiffre de l’autre et en additionnant ensuite les produits :

Si vous êtes à l’aise avec les mathématiques mentales, vous pourriez adopter une autre approche en utilisant la propriété distributive pour faciliter le calcul de la réponse dans votre tête :

25 × 63 = 25 × (60 + 3) = 25 × 60 + 25 × 3 = 1500 + 75 = 1575.

Les deux nous donnent la bonne réponse, mais est-ce que l’une est meilleure que l’autre ? C’est peut-être un choix personnel. Mais il existe au moins un moyen de comparer objectivement les méthodes de multiplication : Efficacité. Bien que l’efficacité puisse signifier différentes choses pour différentes personnes dans différents contextes, réfléchissons-en du point de vue de l’ordinateur. Combien de temps faudrait-il à un ordinateur pour effectuer la multiplication ?

L’évaluation de l’efficacité des algorithmes informatiques est complexe, mais nous adopterons une approche simple qui repose sur deux hypothèses.

  • Tout d’abord, la multiplication de deux grands nombres peut toujours être décomposée en une série de petites multiplications et d’additions.
  • Et deuxièmement, comme la plupart des ordinateurs sont conçus, les petits ajouts peuvent être effectués beaucoup plus rapidement que les petites multiplications. Ainsi, lorsqu’il s’agit de mesurer l’efficacité d’un algorithme de multiplication, ce sont les petites multiplications qui nous préoccupent le plus.

Revoyons notre exemple, 25 × 63, avec l’efficacité à l’esprit. Pour calculer 25 × 63 à l’aide de l’algorithme standard, nous avons dû effectuer quatre petites multiplications : 3 × 5, 3 × 2, 6 × 5 et 6 × 2 Les petites multiplications nous ont donné nos rangées de 15, 60, 300 et 1 200, ce qui fait 1 575. Il est important de noter que lorsque nous appliquons l’algorithme standard, 3 × 2 est réellement 3 × 2 × 10 = 60, 6 × 5 est réellement 6 × 10 × 5 = 300, et 6 × 2 est réellement 6 × 10 × 2 × 2 × 10 = 1 200. Cependant, nous ne comptons pas en multipliant par 10 par rapport à l’efficacité de notre algorithme, car il est tout aussi facile pour les ordinateurs de multiplier par 10 que pour nous – nous décalons simplement les chiffres. Il en va de même pour la multiplication par 100, 1 000, etc.

Ainsi, notre exécution de l’algorithme standard pour calculer 25 × 63 nécessite quatre petites multiplications et quelques additions. Qu’en est-il de l’approche distributive ?

25 × 63 = 25 × (60 + 3) = 25 × 60 + 25 × 3 = 1500 + 75 = 1575.

Dans le calcul de 25 × 60, nous devons multiplier 6 par 2 et 5, et dans le calcul de 25 × 3, nous devons multiplier 3 par 2 et 5. Ça fait encore quatre petites multiplications. Comme chaque méthode nécessite quatre petites multiplications, les deux méthodes sont à peu près équivalentes en termes d’efficacité, selon notre simple mesure. Il n’est donc pas surprenant que l’algorithme standard ne soit en fait qu’une application de la propriété distributive. Voyons pourquoi.

Pensez à multiplier deux nombres arbitraires à deux chiffres ‘AB’ et ‘CD’. Ici, utilisons des guillemets simples pour désigner un nombre décrit par ses chiffres: ‘AB’ est le nombre dont le chiffre des dizaines est A et dont le chiffre des unités est B. En d’autres termes, ‘AB’ est le nombre 10A + B. Ainsi, si ‘AB’ est le nombre 25, A = 2 et B = 5. Et si ‘CD’ est le nombre 63, C = 6 et D = 3.

Pour trouver le produit de ‘AB’ et’CD’, il faut multiplier les deux nombres 10A + B et 10C + D. On peut le faire en utilisant deux fois la propriété distributive :

(10A + B) × (10C + D) = 100(A × C) + 10(A × D) + 10(B × C) + B × D.

Voici à quoi ça ressemble si on branche nos numéros originaux :

25 × 63 = (10 × 2 + 5) × (10 × 6 + 3)
= 100(2 × 6) + 10(2 × 3) + 10(5 × 6) + 5 × 3
= 1200 + 60 + 300 + 15
= 1575.

Notez que toutes les composantes de notre application de l’algorithme standard sont là, juste organisées différemment. Et en termes d’efficacité, nous voyons exactement les mêmes petites multiplications réalisées dans les deux cas : 3 × 5, 3 × 2, 6 × 5 et 6 × 2 Ces deux méthodes font essentiellement la même chose. Quoi qu’il en soit, nous devons multiplier A × C, A × D, B × C et B × D. Ces quatre petites multiplications semblent fixer une limite à l’efficacité de la multiplication.

Mais en 1960, le mathématicien russe Anatoly Karatsuba a trouvé une nouvelle limite, utilisant sa propre application de la loi distributive pour trouver un moyen plus efficace de multiplier. Karatsuba a remarqué que les quatre petites multiplications nécessaires pour calculer le produit de ‘AB’ et ‘CD’ apparaissent lorsque nous multiplions les sommes de leurs chiffres, A + B et C + D :

(A + B) × (C + D) = A × C + A × C + A × D + B × C + B × D.

La somme de ces quatre petites multiplications n’est pas exactement ce que nous voulons, mais Karatsuba savait qu’il pouvait travailler avec. Voyons ce qu’il a fait.

Dans la méthode Karatsuba pour calculer ‘AB’ ×’CD’, nous effectuons d’abord les deux petites multiplications A × C et B × D. Ce sont essentiellement le chiffre des centaines (A × C) et le chiffre des unités (B × D) de notre réponse finale. (Il peut y avoir un peu de portage, mais rappelez-vous que les petits ajouts sont beaucoup plus rapides que les petites multiplications). Une multiplication négligeable par 100 nous donne deux des quatre termes que nous recherchons :

100(A × C) + B × D.

Pour compléter l’ensemble du problème de multiplication, nous voulons :

100(A × C) + 10(A × D) + 10(B × C) + B × D.

Il ne nous manque donc que 10(A × D) + 10(B × C). C’est là qu’intervient l’astuce de Karatsuba. On peut réarranger le produit des sommes de chiffres

(A + B) × (C + D) = A × C + A × C + A × D + B × C + B × D

pour obtenir

(A + B) × (C + D) – A × C – B × D = A × D + B × C.

Nous avons besoin de 10(A × D) + 10(B × C), qui est le même que 10(A × D + B × C), donc nous pouvons simplement multiplier les deux côtés de l’équation ci-dessus par 10 pour obtenir :

10((A + B) × (C + D) – A × C – B × D) = 10(A × D + B × C).

À première vue, cela ne semble pas être une amélioration. Nous avons transformé quelque chose d’assez simple avec seulement deux petites multiplications, 10(A × D + B × C), en quelque chose qui a trois multiplications,10((A + B) × (C + D) – A × C – B × D). Mais le but ultime de Karatsuba n’était pas de rendre les choses plus belles. C’était pour rendre la multiplication plus efficace. Le secret de la méthode de Karatsuba est que nous n’avons pas besoin de calculer A × C et B × D à nouveau : Ce sont les deux premières choses que nous avons multipliées. Nous les connaissons déjà !

Nous remplaçons vraiment les deux multiplications A × D et B × C par deux multiplications que nous avons déjà réalisées – A × C et B × D – et une nouvelle petite multiplication, (A + B) × (C + D). Cela signifie que nous pouvons calculer ‘AB’ ×’CD’ en utilisant seulement trois petites multiplications : A × C, B × D et (A + B) × (C + D).

La méthode de Karatsuba n’est pas facile, et vous ne l’utiliseriez certainement pas pour multiplier 25 par 63 juste pour sauver une petite multiplication. La méthode nécessite plus d’additions, et (A + B) × (C + D) pourrait même ne pas sembler si petite (bien que, si vous y pensez, la plus grande valeur de A + B ou C + D ne peut être beaucoup plus grande qu’un nombre à un chiffre). L’important, c’est que dans le contexte de la multiplication de très grands nombres, comme lorsque les ordinateurs utilisent des techniques mathématiques pour crypter et décrypter des messages secrets et des données sensibles, ces petits compromis se traduisent par de grands gains de vitesse.

Par exemple, supposons que nous voulions multiplier deux nombres à quatre chiffres comme 1 234 et 5 678. Les techniques traditionnelles de multiplication exigeraient de multiplier chaque chiffre d’un nombre par chaque chiffre de l’autre, pour un total de 4 × 4 = 16 petites multiplications. Mais une simple application de la méthode de Karatsuba peut réduire cela : En considérant 1 234 comme 12 × 100 + 34 et 5 678 comme 56 × 100 + 78 et en utilisant la propriété distributive, nous le voyons :

1234 × 5678 = (12 × 100 + 34) × (56 × 100 + 78)
= 12 × 56 × 10000 + 12 × 78 × 100 + 34 × 56 × 100 + 34 × 78.

Cela nécessite quatre produits de paires de nombres à deux chiffres qui, à quatre petites multiplications chacune, nous donnent nos 16 multiplications. Mais en utilisant la méthode de Karatsuba quatre fois, nous avons pu réduire ces quatre produits à trois petites multiplications chacune, pour un total de 12. Et cette amélioration de 25 % n’est qu’un début. D’autres applications intelligentes de la méthode de Karatsuba peuvent réduire le nombre de multiplications encore plus, et les économies augmentent à mesure que le nombre augmente.

Lorsque l’on multiplie deux nombres à n chiffres en utilisant des méthodes traditionnelles, on s’attendrait à obtenir n × n = n2 petites multiplications – chaque chiffre du premier nombre multiplié par chaque chiffre du second nombre. Mais les implémentations complètes de l’algorithme de Karatsuba ne nécessitent qu’environ n1.58  petites multiplications. Cela fait une énorme différence à mesure que les chiffres augmentent. Multiplier deux nombres à 10 chiffres par des méthodes traditionnelles nécessite 10 × 10 = 102 = 100 petites multiplications, mais seulement environ 101.58≈ 38 selon la méthode de Karatsuba. C’est une diminution de 62%. Et pour deux numéros à 100 chiffres, les économies sont encore plus grandes : 1002 = 10 000 contre 1001.58  ≈ 1 445, une différence de 85% !

Vous n’utiliseriez pas cet algorithme pour calculer un pourboire, mais lorsqu’il s’agit de multiplier de grands nombres, la méthode de Karatsuba est un grand progrès. Et une fois que Karatsuba a ouvert la porte à une multiplication plus rapide en 1960, les mathématiciens ont établi de nouveaux records de vitesse depuis lors en utilisant des techniques avancées comme la transformation de Fourier. Cette méthode transforme les problèmes de multiplication des nombres en problèmes de multiplication des polynômes, où il existe des raccourcis surprenants qui créent des algorithmes encore plus rapides – ceux que les ordinateurs utilisent encore aujourd’hui. Ces améliorations ont culminé plus tôt cette année lorsque deux chercheurs ont vérifié une conjecture vieille de près de 50 ans sur l’efficacité maximale des méthodes de multiplication, répondant finalement à la question sur la manière la plus rapide de multiplier.

Mais la question de savoir comment multiplier est encore ouverte. Connaissez vos algorithmes, mais faites ce qui fonctionne le mieux pour vous. Et rappelez-vous, la multiplication n’est pas une course. Sauf si vous essayez d’établir un nouveau record de vitesse.

Par ailleurs, dit « Math » ou « Maths » ?

Via QuantumMag

Vous connaissez désormais la meilleure façon de faire des multiplications.

Laisser un commentaire

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.