English version

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...

Je ne travaille plus sur ce sujet (tout du moins actuellement). Depuis, d'autres personnes ont travaillé dessus. 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).

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.



webmaster@vinc17.org