**Abstract:**A new approach to the computation of long
integers cube - third power - computation based on a splitting in two
divide et impera approach and on a modified Toom-Cook unbalanced
method is presented. A detailed description of its practical
implementation by using the GMP library and performance comparison are
also described.

**Published:** Preprint N.632 Centro
Interdipartimentale "Vito Volterra" - Università di Roma "Tor
Vergata" (January 2010)

**Download:** ~~DVI-paper (28 kB)~~, PDF-paper (187 kB), ~~BibTex-entry~~, software.

**Abstract:** We consider the multiplication of long
integers when one factor is much bigger than the other one. We
describe an iterative approach using Toom-Cook unbalanced methods, by
evaluating the smaller factor just once. The particular case of
Toom-2.5 is considered in full detail, and a further optimization
depending on the parity of shortest operand evaluation in 1 is
described. A comparison with GMP library is also presented.

**Published:** Preprint Centro
Interdipartimentale "Vito Volterra" - Università di Roma "Tor Vergata"
(to appear)

**Download:** ~~DVI-paper (28 kB), PDF-paper (208 kB), BibTex-entry~~, software.

**Abstract:** We present a new approach to evaluation and interpolation phases of
some (balanced and unbalanced) Toom-Cook multiplication methods for
long integers when at least one factor is even. Some other
optimization are also indicated.

**Published:** Preprint N.623 Centro
Interdipartimentale "Vito Volterra" - Università di Roma "Tor Vergata"
(February 2009)

**Download:** DVI-paper (28 kB), PDF-paper (208 kB), BibTex-entry, ~~software~~.

**Abstract:** This work deals with Karatsuba method
for multivariate polynomials, not recursing on variables number, but
using an iterative scheme, with an eye to a better parallelism
exploitation. Integers base 2 and 3 expansions are used in order to
access the needed data.

**Published:** Preprint N.624 Centro
Interdipartimentale "Vito Volterra" - Università di Roma "Tor Vergata"
(February 2009)

**Download:** ~~DVI-paper (. kB),~~ PDF-paper (151 kB), BibTex-entry, software.

**Abstract:** Toom-Cook algorithms are subquadratic
polynomial multiplication methods that are efficiently used also for
long integers. Generally speaking, only the degree 2 (Karatsuba), 3
and 4 version are used in practice. In this paper we analyze a high
(8-way -- degree 7) version, showing that it can be effective for long
integers whose digits number lies in a certain range. Comparison with
GMP 4.3.0 library shows that the gain can be quite considerable, both
for multiplication and squaring.

**Presented:** at SYNASC 2009 - Timisoara, Romania

**Benchmarks:**
Comparison with GMP: x = n. of limbs ; y = time percentage

Graphic 1: Product - Threshold for Toom-8 = 1200

Graphic 2: Square - Threshold for Toom-8 = 900

**Download:** ~~DVI-paper (. kB), PDF-paper (. kB), BibTex-entry~~, software.

**Abstract:**
In this paper the problem of univariate polynomial evaluation
is considered. When both polynomial coefficients and
the evaluation point

are integers, unbalanced multiplications (one
factor having many more digits than the other one) in classical
Ruffini-Horner rule do not let computations completely benefit of
subquadratic methods, like Karatsuba, Toom-Cook and
Schönhage-Strassen's.

We face this problem by applying an approach originally proposed by
Estrin to augment parallelism exploitation in computation. We show
that it is also effective in the sequential case, whenever data dimensions
grow, e.g. in the long integer case.
We add some adjustments to Estrin's proposal obtaining a smoother
behaviour around corner cases, and to avoid performance degradation when
most of the coefficients are zero.

This way, a new general algorithm is obtained, improving both
theoretical complexity and actual performance. The algorithm itself is
very simple, and its use can be usefully extended to evaluation of
polynomials on rationals or on polynomials (polynomial composition).

Some tests, results and comparisons obtained with PARI/GP are also presented,
for both dense and ``sparse'' polynomials.

**Published:** *Long Integers and Polynomial
Evaluation with Estrin's Scheme* in Proceedings of the
13^{th} SYNASC Symposium, Timişoara,
Romania, September 26-29, 2011

**Download:**~~ PDF-paper (309 kB), DjVu-paper (- kB)~~, PDF-slides (610kB)~~, BibTex-entry, software~~.

**Abstract:**
Karatsuba and Toom-Cook are well-known methods used to multiply
efficiently two long integers. There have been different proposal
about the interpolating values used to determine the matrix to be
inverted and the sequence of operations to invert it. A definitive
word about which is the optimal matrix (values) and the (number of)
basic operations to invert it seems still not to have been said. In
this paper we present some particular examples of useful matrices
and a method to generate automatically, by means of optimised
exhaustive searches on a graph, the best sequence of basic
operations to invert them.

**Published:** Preprint N.605 Centro
Interdipartimentale "Vito Volterra" - Università di Roma "Tor Vergata"
(2006)

**Published (full revised version):**
*Integer and Polynomial Multiplication: Towards Optimal Toom-Cook Matrices*
in Proceedings of the ISSAC 2007 conference, Ontario, Canada, July
29-August 1, 2007, ACM press.

**Download:** PDF-preprint (263 kB), DjVu-preprint (104 kB), PDF-paper (287 kB), PDF-slides (475kB), BibTex-entry, software.

**Abstract:**
In Gröbner bases computation, as in other algorithms in commutative algebra, a
general open question is how to guide the calculations coping with
numerical coefficients and/or not exact input data. It often happens
that, due to error accumulation and/or insufficient working
precision, the obtained result is not one expects from a theoretical
derivation. The resulting basis may have more or less polynomials, a
different number of solution, roots with different multiplicity,
another Hilbert function, and so on. Augmenting precision we may
overcome algorithmic errors, but one does not know in advance how
much this precision should be, and a trial-and-error approach is
often the only way to follow. Coping with initial errors is an even
more difficult task. In this experimental work we propose the
combined use of syzygies and interval arithmetic to decide what to
do at each critical point of the algorithm.

**Published:** Proceedings workshop CASC
2006. V.G. Ganzha, E.W. Mayr, E.V. Vorozhtsov ed. Springer-Verlag
LNCS
4194. Chişinau, Moldova 2006, pp. 64-76, ISBN: 3-540-45182-X

**Download:** PDF-paper (250 kB), DjVu-paper (87 kB), PDF-slides (538K), BibTex-entry,
~~software~~.

**Abstract:**
In Gröbner bases computation a general open question is how
to guide calculations coping with numerical coefficients and/or not exact
input data. It may happen that, due to error accumulation or insufficient
working precision, the result is not one theoretically expects. The basis
may have more or less polynomials, a different number of solutions, a
zero set with wrong multiplicity, and so on. Augmenting precision we
may overcome algorithmic errors, but we don't know in advance how
much it should be, and a trial-and-error approach is often the only way.
Coping with initial errors is an even more difficult task. In this work
the combined use of syzygies and interval arithmetic is proposed as a
technique to decide at each critical point of the algorithm what to do.

**Published: (reduced version)** Proceedings of the
6^{th} SYNASC Symposium. D. Petcu,
D. Zaharie, V. Negru, T. Jebelean ed. MIRTON, Timişoara, Romania 2004,
pp. 77 - 89, ISBN 973-661-441-7

**Published: (full version)** Analele
Universitatii din Timisoara, Vol. XLII, Fasc.special 2,
T. Jebelean, V. Negru, A. Popovici ed., Timişoara, Romania 2004,
pp. 13 - 30, ISSN 1224-970X

**Download:** PDF-paper, BibTex-entry, ~~software~~.

Marco Bodrato - 4 novembre 2011