likecs's blog

By likecs, history, 4 years ago, In English,

I was learning the topic FFT from e-maxx.ru (translated version). The english translation for this part "The discrete Fourier transform in a modular arithmetic" is not very clear on google chrome. Also, I am not able to understand clearly the math behind it. Please someone explain it.

Also, I have one doubt regarding the generators in number theoretic transforms. I was going through this solution of this problem. I understood the editorial and how to solve it using fft. But in the NTT solution (given in link) the author discusses about generators for certain prime numbers in comments. Can you please elaborate what are generators and how to calculate them?

Thanks in advance.

**EDIT: ** Understood the concept.

Tags ntt, fft
 
 
 
 
  • Vote: I like it
  • +18
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why so many downvotes?

»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

You cannot expect to understand NTT if FFT is not clear to you. If you want to learn about FFT, here's what helped me learn and understand it: http://web.cecs.pdx.edu/~maier/cs584/Lectures/lect07b-11-MG.pdf

Remember that you need the basic knowledge of complex roots of unity, or else the whole topic might seem a bit overwhelming. Good luck!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hello, retrograd. I am able to understand FFT and how it works using divide and conquer (I read it from here ). I also have a basic understanding of complex roots of unity.

    But I am not able to interpret the complex roots of unity in Modular Arithmetic terms.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      An "n-th root of unity" is an element w which satisfies the equation w n = 1. For a fact we know that in the complex field, we have solutions of form . You can use Moivre's formula to conclude that the roots are of form w 1 0, w 1 1, ..., w 1 n - 1. This is under the complex field, and it's what you should have been familiar with. However, there are other fields that have "n-th roots of unity", more or less similar to what we have discussed. For example, take Z 7 and 2. We have that 23 = 1 in Z 7, so 2 is a 3-rd root of unity. In fact, 20, 21, 22 are all 3-rd roots of unity in Z 7. See the similarity here?

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        Thanks you retrograd, I understood your analogy. Please confirm whether I am right or not. In the example in e-maxx.ru site with P = 7340033, the author uses a generator of 5, and 5^(2^20) = 1 (mod P), meaning that with this generator, 5^0, 5^1.. etc. can be considered as complex root of unity in field of P. This also means we can cover a maximum of 2^20 values as well.

        Thus, does it mean finding the generator depends both on modulo and N given? Please correct me if I am wrong.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          You are correct :). There is an article that covers finding the generator, but I can't seem to find it. In essence, every finite field K incorporates a multiplicative group K  *  (the non-zero elements). In order to find the generator w, you have to find an element of order n in , which is a goup of order p - 1, so it automatically implies that n divides p - 1. If that happens, you can check elements' order sequentially, and one generator will pop out pretty fast (among the first  100 remainders or so).

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          So isnt it like we have a general prime p=(2^k)*c+1

          So we need to find a root of p of order 2^k.So first we find a root of order p-1 (lets say r and order x means r^x = 1 for firsttime for x ).And now we need to find root of order 2^k of p Can we say it is (r^c)???? .Lets say h

          And ((h)^2) is root of order 2^(k-1) of p. So if we are doing ntt and we have a polynomial of size of 2^l. then we take root in first step as ((h)^(2^(k-l))

          And for further steps should be exponentiation of it.

          Am I right??

          And now using a prime p=(2^k)*c+1. we can only multiply two polynomials whose size is less than 2^(k-1) What abt this??

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

sorry for really a bad question but why do we use modulo c*2^k+1 in FFT? Why don't use modulo 10^9+7 like in other questions? Also how is taking modulo 7340033 going to help us in having powers till 2^20 while we take modulo of coefficients of powers and coefficients can be anything(coefficients are not related to powers)?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    We want to have root of unity such that w 2 k = 1. We can't find such value with 109 + 7 mod.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why do we want root of unity such that w^(2^k) = 1? Can you share a resource which can help me understand NTT for competitive programming? I don't find any such explanation of this in e-maxx.ru site.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Because in D&C on each step we go from 2 k roots to 2 k - 1 roots. This is the very basics of FFT...

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          ok, i got what you are saying. But when do we use FFT with modulo instead of normal FFT?

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            When this modulo has 2 k root of unity. Then every statement about usual FFT goes to the modulo FFT.

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              no, i mean why did we require to solve the question that is there in this post using modulo FFT when it can be solved using normal FFT(one without modulo)?

              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Some precision issues. If we want to have exact values when the inputs are integers we should better use NTT.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  How does precision issues come? We only need to check if coefficient is zero or not zero. And when do we know that precision issues are more, so we should do it using NTT?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  We only need to check if coefficient is zero or not zero

                  ???

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I mean in the question we only need to know whether that power has non zero coefficient or not. So how does precision issues come? And when do we know that precision issues are more, so we should do it using NTT?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  You can also consider using NTT when in the question answer is required some modulo. For example, you figured out that the answer to the problem can be found out by checking whether the coefficients are zero or non-zero, but the solution is something like polynomial^k, where k is some large exponent. So here overflow issues may come in the coefficients of the polynomial, So NTT may be a better choice. Also sometimes, it is also required to find the coefficients of the polynomial some modulo. Thus NTT is the only choice instead of FFT.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you provide some materials for learning NTT ?

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I have written an Illustrated Guide for the Iterative Number Theoretic Transform Multiplication Algorithm.