Recent Fast Multiplication Algorithms for Large Integers

Question

The STOC 2008 paper "Fast Integer Multiplication using Modular Arithmetic" by De et al http://arxiv.org/abs/0801.1416 shows how to use $p$-adic numbers instead of $\mathbb C$ used in Furer's multiplication algorithm. Given that Furer's algorithm is not practical for less than a few thousand bits (is there a good estimate of its breakeven point vs Toom-Cook and other algorithms?), I wonder if the De et al algorithm has a lower breakeven point, is easier to implement, and is more practical in general.

Pointers to follow-up work and/or attempts at implementing the STOC 2008 algorithm would be appreciated.

Igor

Answer 1

For new results, in integer multiplication, check the breakthrough paper by: David Harvey, and Joris Van Der Hoeven, et al . Integer multiplicaion in $O(n*(log$ $n))$. This proves Schonhage Strassens' conjecture from the 1970s that integer multiplication is really possible in $O(n*(log$ $n))$. From, straightforward (school) integer multiplication which is $O( n^{2}) $, to karatsubas' algorithm which is $O(n^{1.58})$, to $O(n*(log$ $n))$, by above authors. The authors use the property of specific multivariate polynomial rings that admit efficient multiplication.

The authors show that integer multiplication (which is one dimensional) could be represented in a setting of a specific multivariate polynomial ring. Starting with a binary representation of integers, begin with the fixed point coordinate vectors(to a precision), and then go on to utilize them in coefficient rings for that polynomial representation. One could select parameters, and reduce the integer multiplication problem to one of convolution over a ring with a specific structure, reaching the bound.

The bound is a significant improvement over earlier algorithms, and with many digits the efficiencies are apparent, for a large number of digits billions, and larger scales as author(s) claim its unknown, but good performance is possible.