-1

The fastest known algorithm for polynomial multiplication is using Fast Fourier Transformation (FFT).

In a special case of multiplying a polynomial with itself, I am interested in knowing if any squaring algorithm performs better than FFT. I couldn't find any resource which deals with this aspect.

ChocoLite
  • 111
  • 5
  • 3
    Why does this feel like homework? – gnasher729 Nov 18 '19 at 18:38
  • 1
    When asking about homework (1) **Be aware of your school policy**: asking here for help may constitute cheating. (2) Specify that the question is homework. (3) **Make a good faith attempt** to solve the problem yourself first (include your code in your question). (4) **Ask about a specific problem** with your existing implementation; see [Minimal, complete, verifiable example](https://stackoverflow.com/help/minimal-reproducible-example). Also, [here](https://meta.stackoverflow.com/questions/334822/how-do-i-ask-and-answer-homework-questions) is guidance on asking homework questions. – Prune Nov 18 '19 at 22:02
  • @Prune This question is a part of a practice paper. I couldn't find any other resource which describes an algorithm faster than FFT. I have edited the question now. – ChocoLite Nov 19 '19 at 08:21
  • I see no Stack Overflow question here. [On topic](https://stackoverflow.com/help/on-topic), [how to ask](https://stackoverflow.com/help/how-to-ask), and ... [the perfect question](https://codeblog.jonskeet.uk/2010/08/29/writing-the-perfect-question/) apply here. – Prune Nov 19 '19 at 16:57
  • Squaring polynomials can't be asymptotically faster than multiplying them, for the same reason for which that is true for integers: a fast square could be used to do a fast multiply using the quarter-square multiplication algorithm. Practically there is a difference. – harold Nov 19 '19 at 21:23
  • @harold in the FFT based squaring you ignore computing one of the FFT because its the same ... on non FFT approaches squaring is around half of computatitons in comparison to multiplication but yes you're right the complexity is in both cases the same ... just the constant time changes – Spektre Nov 19 '19 at 21:27

1 Answers1

1

  1. Number Theoretic Transform (NTT) is faster than FFT

    Why? Because you using just integer modular arithmetics on some ring instead of floating point complex numbers while the properties stays the same (as NTT is sort of form of DFT ...). So if your polynomials are integer use NTT which is faster... if they are float you need to use FFT

  2. FFT based squaring is faster than FFT based multiplying by itself

    Why? Because you need just 1x NTT/FFT and 1x iNTT/iFFT while multiplying needs 2xNTT/FFT and 1x iNTT/iFFT so you spare one transformation ... the rest is the same

  3. for small enough polynomials is squaring without FFT fastest

For more info see:

its not the same problem but very similar ... as bignum data words are similar to your polynomial coefficients. So most of it applies to your problem too

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • @kaya3 thx for the NTT link edit ... Look at this [Modular arithmetics and NTT (finite field DFT) optimizations](https://stackoverflow.com/q/18577076/2521214) it might interest you ... – Spektre Nov 19 '19 at 21:15