Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
add comment

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.