Version française

Multiplication by Integer Constants

Introduction

This page deals with the problem of performing multiplications by integer constants using elementary operations (e.g. left shifts by any number of bits, corresponding to multiplications by fixed powers of two, additions and subtractions), and in particular, algorithms generating such codes. These algorithms can be used either directly by the programmer (for instance in multiple precision, for the Toom-Cook-like algorithms to multiply large multiple-precision integers and for the approximate computation of consecutive values of a polynomial) or by compilers to generate integer multiplications for some processors. The generated code can be implemented either in software or in hardware (e.g. on FPGAs). The main problem is to obtain a code as good as possible in a reasonable time (for instance, in a polynomial time).

Papers

My main papers on this subject, in chronological order...

I no longer work on this subject (at least currently). Other people have worked on it since. For those who are interested in implementing an algorithm on not too large constants (a few dozens of bits?), I recommend in particular the article Multiplierless multiple constant multiplication by Yevgen Voronenko and Markus Püschel (their code with an on-line generator).

Software

My software directory for the multiplication by integer constants contains:

bernstein.c

My implementation in ISO C of Bernstein's algorithm.

patterns

My implementation in Perl of my algorithms based on repeating patterns; it has a good time complexity, but uses much memory, as almost everything is cached. Run this script without arguments for some documentation on its usage. Note: I wrote this Perl script mainly for my own research work, not as a software that can be used by anyone. It is distributed under the GNU General Public License (version 2 or later).

[2015-08] New: Mode m is threaded. Some results with my common subpatterns algorithm (mode m, i.e. exhaustive tests); results for 28 ≤ n ≤ 37 were obtained in August and September 2015.

rigo.c

The implementation in C (using GMP) of my latest algorithm, by Raphaël Rigo. It is distributed under the GNU General Public License (version 2 or later).

MulByConst.tar.xz

My old source files with their RCS history, written between 2000 and 2003. The main goal of this archive is to be able to check the codes used for some of my articles.



webmaster@vinc17.org