0

I've been working on code to multiply polynomials using NTT (FFT), and I made 2 different implementations, and used existing ones to validate, for example: https://www.nayuki.io/page/number-theoretic-transform-integer-dft, https://github.com/iblue/ntt.

The problem is that all results seem to be shifted once to the left (multiplied by x) like this:

0 0 1 1 (x + 1)
*
0 0 1 1 (x + 1)
=
1 2 1 0 (1x^3 + 2x^2 + x) // Should be 0 1 2 1

Also, the trivial case 1*1 is wrong the same way:

0 0 0 1 (1)
*
0 0 0 1 (1)
=
0 0 1 0 (x) // Should be 0 0 0 1 (1)

I have no clue why this is happening, and it is not mentioned in any of the articles I've read so far.

What am I missing?

Robert Bräutigam
  • 7,514
  • 1
  • 20
  • 38
  • 3
    It seems like that example code which you provided (from github) assumes that data is provided in reverse order from yours - power's coefficients go from left to right for lowest to highest. For example (1, 2, 0, 0) will be 2*x + 1. – Yevgeniy.Chernobrivets Apr 05 '18 at 18:42
  • Hm.. you're right, I didn't see it. I was sure the higher coefficients get the low exponent twiddle factors, I didn't even look there. Thanks. – Robert Bräutigam Apr 05 '18 at 21:15
  • I agree with @Yevgeniy.Chernobrivets's answer. When using my NTT implementation, you should put the coefficient for x^0 at index 0, in other words, the left side of the vector. – Nayuki Apr 06 '18 at 06:28

0 Answers0