1
$\begingroup$

In integer multiplication algorithms such as the Schonhage-Strassen algorithm (and the recently described Harvey and van der Hoeven algorithm), integers of size $n$ are reduced to polynomials with coefficients that have $\log(n)$ bits. Is there any particular motivation behind $\log(n)$ being the size of the coefficients?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ If I recall correctly: in principle, for divide-and-conquer algorithms like FFT, you want to split the input into as many chunks as possible in order to make the advantage of the algorithm most pronounced. But even if you split it to chunks of $O(1)$ bits, you will still need to work with $O(\log n)$-bit numbers as intermediate results during the computation. Since you already pay the price of arithmetic operations on $O(\log n)$-bit numbers, you can as well use $O(\log n)$-bit chunks, as this will not increase the cost of these operations further, but will reduce the size of the FFT. $\endgroup$
    – Emil Jeřábek
    Mar 23 at 10:24
  • $\begingroup$ In the first step of Schönage-Strassen algorithm, the inputs are split as (roughly) $\sqrt n$ chunks of size $\sqrt n$, not $\log n$. Cf. for instance I'm Modern Computer Arithmetic. $\endgroup$
    – Bruno
    Mar 26 at 16:27

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.