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?

  • $\begingroup$ 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. $\endgroup$
    – Laakeri
    Nov 23, 2020 at 10:29
  • $\begingroup$ 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? $\endgroup$ Nov 23, 2020 at 10:36
  • 7
    $\begingroup$ 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)$. $\endgroup$ Nov 23, 2020 at 10:38
  • 3
    $\begingroup$ Thank you, this is very clear! Maybe consider posting this as an answer. $\endgroup$ Nov 23, 2020 at 10:43
  • $\begingroup$ I also mention that the (not yet published) O(n log n) integer multiplication algorithm 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. $\endgroup$
    – Bruno
    Nov 25, 2020 at 10:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.