Multiplication naïve (multiplication par boucle d'addition)

La multiplication naïve, également appelée multiplication par boucle d'addition, est la méthode la plus simple permettant de réaliser une multiplication sans utiliser directement l'opérateur de multiplication (*). Son principe consiste à remplacer une multiplication par une succession d'additions répétées. Bien que cette approche soit très facile à comprendre et à programmer, elle est également l'une des plus lentes lorsque les nombres à traiter deviennent importants. Pour cette raison, elle est principalement utilisée dans les ouvrages pédagogiques, les cours d'algorithmique et les démonstrations sur le fonctionnement des opérations arithmétiques. En pratique, les compilateurs, les processeurs et les bibliothèques mathématiques utilisent des algorithmes beaucoup plus performants.

Le fonctionnement est particulièrement intuitif. Pour calculer a × b, il suffit d'additionner la valeur a à elle-même b fois. Ainsi, pour calculer 6 × 4, l'algorithme effectue successivement les additions 6 + 6 + 6 + 6, ce qui produit le résultat 24. Cette technique correspond exactement à la définition mathématique de la multiplication comme étant une addition répétée. Son principal avantage réside dans sa simplicité de mise en ouvre, puisqu'elle ne nécessite qu'une boucle et une addition.

On obtient alors un algorithme semblable au suivant :

Dans cet algorithme, la variable produit est initialisée à zéro. À chaque itération de la boucle, la valeur de a est ajoutée au résultat courant. Après b répétitions, la variable produit contient le résultat final de la multiplication. Cet algorithme est très facile à comprendre et constitue souvent l'un des premiers exemples utilisés pour illustrer les boucles dans un langage de programmation.

Cependant, cette approche présente un inconvénient majeur : son temps d'exécution dépend directement de la valeur du multiplicateur. Si la variable b contient un très grand nombre, la boucle devra être exécutée un très grand nombre de fois, ce qui ralentira considérablement le programme. À l'inverse, si b est une petite valeur, le calcul sera relativement rapide. Ainsi, multiplier 5 × 1 000 000 nécessite un million d'additions, ce qui est extrêmement coûteux comparativement à une simple instruction de multiplication fournie par le processeur.

Une première optimisation consiste donc à utiliser comme compteur de boucle la plus petite des deux valeurs. Si a est inférieur à b, les deux variables sont simplement échangées avant de commencer le calcul. De cette manière, la boucle est exécutée le moins grand nombre de fois possible, ce qui permet de réduire le temps d'exécution sans modifier le résultat de la multiplication.

L'algorithme optimisé devient alors :

Cette optimisation est très simple, mais elle peut avoir un impact significatif lorsque les deux opérandes sont de tailles très différentes. Par exemple, il est beaucoup plus efficace d'effectuer 5 additions de 1 000 000 que d'effectuer 1 000 000 additions de 5. Le résultat est évidemment identique, mais le nombre d'itérations de la boucle est considérablement réduit.

Malgré cette amélioration, la multiplication naïve demeure un algorithme relativement lent. Sa complexité temporelle est proportionnelle au plus petit des deux opérandes, ce qui signifie que son temps d'exécution augmente linéairement avec la taille des nombres manipulés. Cette caractéristique la rend peu adaptée aux calculs intensifs ou aux applications scientifiques nécessitant un grand nombre de multiplications.

Les processeurs modernes réalisent les multiplications à l'aide de circuits électroniques spécialisés capables d'effectuer cette opération en quelques cycles d'horloge seulement. De plus, les bibliothèques mathématiques destinées aux grands entiers utilisent des algorithmes beaucoup plus élaborés, comme la multiplication russe, la multiplication de Karatsuba, la multiplication de Toom-Cook ou encore les méthodes basées sur la transformée de Fourier rapide (FFT), selon la taille des nombres à traiter.

Remarque

• Si vous souhaitez effectuer une multiplication rapidement, il est préférable d'utiliser un algorithme plus performant que la multiplication naïve. Parmi les méthodes classiques figure notamment la multiplication russe, exploitant les décalages de bits et les additions pour réduire considérablement le nombre d'opérations nécessaires. Cette technique est beaucoup plus efficace pour les grands nombres et constitue une excellente introduction aux algorithmes de multiplication optimisés utilisés en informatique moderne.