8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is any FFT base algorithm practical for less than a few thousand bits? $\endgroup$ – Igor Rivin Aug 4 '12 at 22:02
  • $\begingroup$ 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 $\endgroup$ – Igor Markov Aug 5 '12 at 1:33
3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Josiah Park Apr 8 at 5:50
  • $\begingroup$ This does not answer the question as stated in the body of the question, which is about practicality and implementations of fast multiplication algorithms. $\endgroup$ – Wojowu Apr 8 at 8:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.