# Recent Fast Multiplication Algorithms for Large Integers

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

• Is any FFT base algorithm practical for less than a few thousand bits? Aug 4, 2012 at 22:02
• Apparently not - the Toom-Cook family of algorithms rules in a large range. This old paper lyle.smu.edu/~seidel/courses/cse8351/papers/ZurasMult.pdf evaluates Schonhage-Strassen and claims that it does not win at least until 37M bits Aug 5, 2012 at 1:33

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.
• While of theoretical interest, the method is staggeringly not practical in its current form. According to GLL 'they note that their estimates take effect for $n\geq 2^{d^{12}}$ where they use $d=1729$'. The appearance of the number $1729$ is not coincidental. Apr 8, 2019 at 5:50