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

CC BY-SA 4.0
2023-03-23T10:24:11.553Z
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.
Emil Jeřábek
CC BY-SA 4.0
2023-03-26T16:27:24.110Z
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](https://members.loria.fr/PZimmermann/mca/mca-cup-0.5.9.pdf).
Bruno
<ds.algorithms><comp-number-theory><recursion><analysis-of-algorithms><fft>
Why does splitting $n$ bit integers into chunks of size $\log(n)$ specifically, help in multiplying them
Vighnesh Iyer
# Why does splitting $n$ bit integers into chunks of size $\log(n)$ specifically, help in multiplying them

(Asked by: username_0 on 2023-03-23)

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?

**Tags:** ds.algorithms, comp-number-theory, recursion, analysis-of-algorithms, fft

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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](https://members.loria.fr/PZimmermann/mca/mca-cup-0.5.9.pdf).  

---

## 0 answers

