MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
    
Is any FFT base algorithm practical for less than a few thousand bits? – Igor Rivin Aug 4 '12 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 – Igor Markov Aug 5 '12 at 1:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.