manjunath1996's blog

Doubt Regarding NTT
By manjunath1996, history, 9 years ago, In English

I have a doubt about how devide polynomial in NTT.Specifically in this problem link :https://www.codechef.com/JULY16/problems/POLYEVAL/ In editorial and many solution,they are deviding polynomial into 3 polynomials as A(x^3)+xA(x^3)+x^2A(x^3). I didn't understand why it is needed to devide the polynomial into 3 polynomial first and then apply NTT. Can we take whole polynomial into single array and do it's NTT.Please Clarify my doubt.

  • Vote: I like it
  • +21
  • Vote: I do not like it

»
9 years ago, hide # |
 
Vote: I like it +86 Vote: I do not like it

Only LiTi understood FFT and NTT. Ask him.

→ Reply
»
9 years ago, hide # |
← Rev. 2  
Vote: I like it +53 Vote: I do not like it

LiTi Can you please explain it??

→ Reply
»
9 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

mod = 3*2^18+1 . its convenient to divide it into three portions so that size of each portion is a power of 2 . you can even initially form three polynomials each of size 2^18 and perform NTT on all three of them so that they finally produce values for 3*2^18 distinct points.

→ Reply
»
9 years ago, hide # |
 
Vote: I like it +46 Vote: I do not like it

So maybe on his birthday, LiTi will be willing to explain NTT? Happy birthday, LiTi :)

PS: We are waiting for you :D

→ Reply