Multiplication par des constantes entières

Introduction

Cette page concerne le problème d'effectuer des multiplications par des constantes entières à l'aide d'opérations élémentaires (par exemple, décalages vers la gauche d'un nombre de bits quelconque, correspondant à des multiplications par des puissances de deux fixées, additions et soustractions), et en particulier, les algorithmes permettant de générer de tels codes. Ces algorithmes peuvent être utilisés directement par le programmeur (par exemple en multiprécision, pour les algorithmes du style Toom-Cook afin de multiplier des entiers à grande précision et pour le calcul approché de valeurs consécutives d'un polynôme) ou bien par les compilateurs afin de générer des multiplications entières pour certains processeurs. Le code ainsi généré peut être implanté soit en logiciel, soit en matériel (par exemple, sur FPGA). Le principal problème est d'obtenir du code aussi bon que possible en un temps raisonnable (par exemple, en temps polynomial).

Papiers

Mes principaux papiers sur le sujet, dans l'ordre chronologique...

• [Lef1999b] Multiplication by an integer constant, rapport de recherche LIP RR1999-06, janvier 1999.

  Ce rapport de recherche décrit mon premier algorithme basé sur une recherche de motifs qui se répètent dans l'écriture binaire de la constante. Noter que la conjecture de la section 5.3 est fausse (c'est une conséquence des résultats de mon papier sur les minorants de la longueur du code généré); cela montre en même temps l'irrégularité du problème.

• [DinLef2000a] Constant multipliers for FPGAs (écrit avec Florent de Dinechin), dans le Second International Workshop on Engineering of Reconfigurable Hardware/Software Objects (ENREGLE 2000), juin 2000. Aussi disponible comme Rapport de recherche LIP RR2000-18.

  L'application aux FPGA...

• [Lef2001b] Multiplication par une constante, dans Réseaux et Systèmes Répartis, Calculateurs Parallèles, 2001. Une version un peu plus ancienne est disponible en anglais comme Rapport de recherche INRIA RR-4192.

  Cet article présente notamment une amélioration de mon premier algorithme basé sur une recherche de motifs; il s'agit en fait d'une extension naturelle de cet algorithme pour multiplier un même nombre par plusieurs constantes (comme dans une multiplication d'un vecteur par une matrice constante). Les divers algorithmes présentés dans ce papier sont comparés entre eux, ainsi qu'avec ce qu'on pourrait obtenir par un algorithme générant du code optimal.

• [Lef2003a] Multiplication by an integer constant: lower bounds on the code length, dans les actes de RNC'5, septembre 2003.

  Ce papier est plus théorique que les précédents. À l'aide de résultats de la théorie de l'information, on cherche ici des minorants (essentiellement asymptotiques) de la longueur d'un code de multiplication par une constante (obtenu soit par n'importe quel algorithme, ce qui correspond au cas optimal, soit par un algorithme donné). Une étude sur la taille maximale d'un décalage dans un code optimal est également effectuée.

  J'ai donné dans ce papier une classe de programmes optimaux pour lesquels le rapport asymptotique de la taille maximale d'un décalage sur la taille de la constante est de 7 / 6. J'ai trouvé plus tard un exemple similaire (et une preuve similaire) menant à un rapport asymptotique de 3 / 2: pour h ≥ 4, considérer n = (1 + 2^h)  (1 + 2^h + 2)  (1 + 2^h + 4) − 2^3h + 6, qui est un entier de 2h + 7 bits (2^2h + 6 + 2^2h + 4 + 2^2h + 2 + 2^h + 4 + 2^h + 2 + 2^h + 1) calculable par un programme optimal (4 opérations élémentaires) utilisant un décalage de 3h + 6 bits.

Je ne travaille plus sur ce sujet (tout du moins actuellement). Depuis, d'autres personnes ont travaillé dessus, cf section Voir aussi.

Logiciels

Mon répertoire de logiciels pour la multiplication par des constantes entières contient:

bernstein.c

Mon implémentation en C ISO de l'algorithme de Bernstein.

patterns

Mon implémentation en Perl de mes algorithmes basés sur des motifs communs; elle a une bonne complexité en temps, mais consomme beaucoup de mémoire, car quasiment tout est mis en cache. Lancer ce script sans argument pour obtenir un peu de documentation sur son utilisation. Note: j'ai écrit ce script Perl principalement pour mes propres travaux de recherche, pas en tant que logiciel utilisable par n'importe qui. Il est distribué sous la licence GNU General Public License (version 2 ou plus).

[2015-08] Nouveau: Le mode m est threadé. Quelques résultats avec mon algorithme sous-motifs communs (mode m, i.e. tests exhaustifs); les résultats pour 28 ≤ n ≤ 37 ont été obtenus en août et septembre 2015.

rigo.c

L'implémentation en C (utilisant GMP) de mon dernier algorithme, par Raphaël Rigo. Elle est distribuée sous la licence GNU General Public License (version 2 ou plus).

MulByConst.tar.xz

Mes anciens fichiers source avec leur historique RCS, écrits entre 2000 et 2003. Le but principal de cette archive est de pouvoir vérifier les codes utilisés pour certains de mes articles.

Voir aussi

• Pour ceux qui sont intéressés par implémenter un algorithme sur des constantes pas trop grosses (quelques dizaines de bits?), je recommande en particulier l'article Multiplierless multiple constant multiplication de Yevgen Voronenko et Markus Püschel (leur code avec un générateur en ligne).

• Radix-2r Arithmetic for Multiplication by a Constant d'Abdelkrim K. Oudjida et Nicolas Chaillet.

• Dépôt de Rocky Bernstein sur la multiplication par des constantes entières.