We're given two positive integers $t$ and $s$ of length $n$ in binary representation.

Suppose we divide the numbers into ${n \over k}$ blocks of size $k=\lg n$ using FFT algorithm.

Suppose that the multiplications that occur during recursive calls do not increase the length of the resulting numbers (not necessarily true in reality but can be supposed for the sake of the algorithm) therefore the multiplications can be performed in $Θ(k^2)$ bit operations.

How can we complete the computation is $O(n\lg^2n)$?

We can represent $x$ and $y$ as a sum. For example: $$ t = t_0\cdot 2^0+t_1\cdot 2^1 +...+ t_{{n \over k} -1}\cdot 2^{{n \over k} -1} $$

Essentially powers of two are analogous to $x$'s in a polynomial $a_n\cdot x^n+...+a_1\cdot x^1+a_0\cdot x^0$.

Therefore we can use FFT on the coefficients vector of $t$.

Let $\bar t, \bar s$ be the coefficients vectors of their corresponding sum representation.

Then: $$ q = \operatorname{FFT}(\bar t) \cdot \operatorname{FFT}(\bar s)\\ p= \operatorname{iFFT}(\bar q) $$ where $\operatorname{iFFT}$ is the inverse FFT algorithm and $q$ is the point-wise result of $\bar t\cdot \bar s$. FFT operations run time is $O({n \over k}\lg{{n \over k}})$ but we know that the length of the result of bit multiplication of $x_i\cdot y_i$ is still $k$ so the run time is really $O(k^2\cdot {n \over k}\lg{{n \over k}}) = O({nk}\lg{{n \over k}})$.

I'm not sure how I can complete the algorithm in $O(n\lg^2 n)$ time from this step though.

  • $\begingroup$ I don't really see what's missing. If you plug in $k = \lg n$ then you get $O(n\lg^2 n)$. $\endgroup$ – Yuval Filmus Dec 7 '17 at 21:43
  • $\begingroup$ You don't mention the propagation step following the convolution : $11 \ast 11 = 121 = 201 = 1001$, nor the size needed to store the complex numbers. $\endgroup$ – reuns Dec 8 '17 at 3:27
  • 1
    $\begingroup$ The answer really depends on the computation model, but usually multiplying by powers of 2 is easy (in the bit complexity model, free). $\endgroup$ – Yuval Filmus Dec 8 '17 at 9:05
  • 1
    $\begingroup$ No. Shifting is for free in the bit complexity model, since you're just renaming bits. If you're using a different model then it depends on the allowed operations, but shifting shouldn't be the computation-intensive part of the algorithm. $\endgroup$ – Yuval Filmus Dec 8 '17 at 9:19
  • 1
    $\begingroup$ Unfortunately I cannot help you further. If you have any more questions, I suggest contacting a TA. $\endgroup$ – Yuval Filmus Dec 8 '17 at 10:18

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.