FFT enables us to perform multiplication of polynomials in O(nlogn), where "multiplication" is the standard multiplication over the complex numbers. Is there a general procedure to extend this use of FFT for cases where the "multiplication" is any arbitrary commutative binary operator? for example, for the case where we define ab = a+b (mod n) for an arbitrary n (assuming, in this case, the coefficients of the polynomials are integers)?


  • $\begingroup$ No. What you need for making sense to the DFT of size $N$ is a primitive $N$th root of unity (replacing $e^{2i \pi / N}$). And see the number theoretic transform. $\endgroup$ – reuns Dec 18 '16 at 21:44
  • $\begingroup$ That's true, yet there is a way, for example, to use FFT for string matching, where we define a*b = 1 iff a=b, else 0. The multiplication itself is still the standard multiplication, but there is a way to use it to calculate the desired operator, which differs from the standard multiplication: cs.stackexchange.com/questions/52775/… $\endgroup$ – user1767774 Dec 18 '16 at 21:48
  • 1
    $\begingroup$ Not at all. The FFT string matching algorithm does nothing more than computing the correlation between shifts of two binary vectors $a(n),b(n) \in \{0,1\}^N$, and it reduces to computing the convolution $c(n) = a \ast b(n)$ seen as sequences of complex numbers, i.e. it is based on the complex multiplication. $\endgroup$ – reuns Dec 18 '16 at 22:11
  • $\begingroup$ I understand, thanks. $\endgroup$ – user1767774 Dec 19 '16 at 16:36

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.