<p>I am trying to understand how Schönhage-Strassen works for integers by studying von zur Gathen and Gerhard's <em>Modern computer algebra</em>. However they only talk about multiplication of polynomials.</p>
<p>In the book they use fast Fourier transform over a specifically crafted ring such that it has a certain primitive root of unity, but since we are working with integers, isn't it possible to just work over <span class="math-container">$\mathbb{C}$</span>?</p>
<p>What are the disadvantages of doing this?</p>

CC BY-SA 4.0
2020-11-23T10:29:06.907Z
I'm not familiar with the book, but isn't a natural reason for this that there are no suitable discrete representations of roots of unity in ℂ? In particular, I guess that they want to avoid working with floating point numbers.
Laakeri
CC BY-SA 4.0
2020-11-23T10:36:08.693Z
I understand that this would indeed be a practical issue. Does this also have an effect on the bit complexity for the algorithm? For example, if we want a correct result, we would need enough precision for the floating point numbers so that a multiplication of complex numbers increases the complexity?
Jarne Renders
CC BY-SA 4.0
2020-11-23T10:38:18.923Z
Complex numbers can’t be represented exactly in a computer, you need to use approximations, and doing it right so that the end-result is not invalidated by rounding errors is quite a hassle. But more importantly, it is slower. One needs about $O(\log n)$ bits of precision, and the resulting multiplication algorithm has time complexity $O(n(\log n)^2)$, whereas the other Schönhage–Strassen algorithm has time complexity $O(n\log n\log\log n)$.
Emil Jeřábek
CC BY-SA 4.0
2020-11-23T10:43:28.360Z
Thank you, this is very clear! Maybe consider posting this as an answer.
Jarne Renders
CC BY-SA 4.0
2020-11-25T10:27:35.793Z
I also mention that the (not yet published) [O(n log n) integer multiplication algorithm](https://hal.archives-ouvertes.fr/hal-02070778) uses fixpoint arithmetic over ℂ, among other techniques. But of course it is not a direct use of roots of unity over ℂ, since this would yield the complexity given by Emil Jeřábek.
Bruno
CC BY-SA 4.0
2020-12-02T14:30:41.897Z
Schönhage and Strassen actually describe two algorithms in their paper. The first one is based on working over ℂ, and the complexity is $O(n \log^{1 + \varepsilon} n)$ for any $\varepsilon$. The second one is now commonly known as the Schönhage-Strassen algorithm.
Vladimir Lysikov
<time-complexity>
Schönhage-Strassen algorithm: why don't we work over $\mathbb{C}$
Jarne Renders
# Schönhage-Strassen algorithm: why don't we work over $\mathbb{C}$

(Asked by: username_0 on 2020-11-23)

I am trying to understand how Schönhage-Strassen works for integers by studying von zur Gathen and Gerhard's *Modern computer algebra*. However they only talk about multiplication of polynomials.

In the book they use fast Fourier transform over a specifically crafted ring such that it has a certain primitive root of unity, but since we are working with integers, isn't it possible to just work over $\mathbb{C}$?

What are the disadvantages of doing this?

**Tags:** time-complexity
> **Comments:**
> **username_1**: I'm not familiar with the book, but isn't a natural reason for this that there are no suitable discrete representations of roots of unity in ℂ? In particular, I guess that they want to avoid working with floating point numbers.  
> **username_0**: I understand that this would indeed be a practical issue. Does this also have an effect on the bit complexity for the algorithm? For example, if we want a correct result, we would need enough precision for the floating point numbers so that a multiplication of complex numbers increases the complexity?  
> **username_2**: Complex numbers can’t be represented exactly in a computer, you need to use approximations, and doing it right so that the end-result is not invalidated by rounding errors is quite a hassle. But more importantly, it is slower. One needs about $O(\log n)$ bits of precision, and the resulting multiplication algorithm has time complexity $O(n(\log n)^2)$, whereas the other Schönhage–Strassen algorithm has time complexity $O(n\log n\log\log n)$.  
> **username_0**: Thank you, this is very clear! Maybe consider posting this as an answer.  
> **username_3**: I also mention that the (not yet published) [O(n log n) integer multiplication algorithm](https://hal.archives-ouvertes.fr/hal-02070778) uses fixpoint arithmetic over ℂ, among other techniques. But of course it is not a direct use of roots of unity over ℂ, since this would yield the complexity given by Emil Jeřábek.  
> **username_4**: Schönhage and Strassen actually describe two algorithms in their paper. The first one is based on working over ℂ, and the complexity is $O(n \log^{1 + \varepsilon} n)$ for any $\varepsilon$. The second one is now commonly known as the Schönhage-Strassen algorithm.  

---

## 0 answers

