Tutorial on FFT/NTT — The tough made simple. ( Part 2 )

Правка en4, от sidhant, 2016-12-14 13:51:17

Okay so firstly, in hindsight I now see the drawbacks there were in my explanation of the roots of unity and how the divide and conquer works in FFT. So in this blog I would be aiming to give you an intuition of what really FFT exploits over the trivial classical DFT. Also I would be covering up NTT.

Firstly, I am assuming that you have been through the Part 1 (URL).

Okay so the intution for FFT, the part where most of the people find FFT weird or magical is where we convert the polynomial from coefficient form to point value form in N * logN instead of the trivial N2. Okay so here is the broad idea

In the notation below I have referred to n complex nth roots of unity as powers of wn1 = e2π * i / n

Assume that you have a 8 terms (7 degree) polynomial you need to convert from coefficient form to point value form. So firstly you choose the powers of the 8th complex root of unity as the xi's that you will be plugging in the polynomial. Initially this might seem random but hopefully by the end of this topic it would be clear to you. Okay so now we can reduce our polynomial A(x) as Aeven(x2) + x * Aodd(x2) where Aeven() is a 4 terms (3 degree) polynomial and Aodd() is also a 4 terms (3 degree) polynomial. Now solving the original problem of converting A(x) from coefficient form to point value form for each of the power of the 8th root of unity is exactly equivalent to solving this new problem of converting Aeven(x2) and Aodd(x2) for powers the 8th root of unity. So really this doesn't help us much BUT THE TRICK is that when we square (because x2) these powers of the 8th root of unity, they come out to be same pairwise, ie. the 0th and 4th powers of the 8th root of unity when squared give the same result, similarly, the 1st and 5th powers of 8th root of unity when squared give the same result and so on. Also note that these results actually turn out to be the powers of the 4th root of unity. Okay, So I gave the dry mathematical proof for this in the previous part, but that time I did not have a visual understanding of it. Well now I do so refer to the animations and diagrams below to get the idea but first read through the below subtopic of Rotation in Imaginary Plane.

Rotation in Imaginary Plane — Okay so as a rule of thumb remember that if you have a complex number lets say Z and you multiply it with eiθ then it basically rotates it by θ angle in counter — clockwise direction with respect to the origin. So lets say you have 3rd power of 8th root of unity, ie. wn3 = ei * 2π * 3 / 8 and you wish to exponentiate it. Then currently the θ is . So if you square it you are actually multiplying the θ by 2 so you are basically rotating it by theta degree in counter — clockwise direction with respect to the origin. Formally raising it by x is (wn3)x = ei * 2π * 3 / 8 * x = ei * 2π * 3 / 8 * ei * 2π * 3 / 8 * (x - 1) =  rotating e^{i*2\pi*3/8) by (x — 1) * \theta \deg in counter clockwise direction with respect to x axis.

Diagram here.

So given this understanding we can now easily exponentiate roots of unity. So here is the key, when you mark the 8th roots of unity on a graph it is regular octagon whose vertices are making angle 0, 45, 90, 135, 180, 225, 270, 315 degree with respect to positive x axis. Now when you square each of these, the angles double as shown above, so they become 0*2, 45*2, 90*2, 135 * 2, 180 * 2, 225 * 2, 270 * 2, 315 * 2 = 0, 90, 180, 270, 360, 450, 540, 630 = 0, 90, 180, 270, 0, 90, 180, 270 which are basically the points of the 4th root of unity. Below is a beautiful animation showing the same.

de tunak tunak

Here you can clearly grasp the complexity of T(n) = T(n / 2) (For Aeven()) + T(n / 2) (For Aodd()) + O(2 * n)(For combining the results as Aeven(x2) + x * Aodd(x2))

NTT (Number Theoretic Transform) — The objective of NTT is to multiply 2 polynomials such that the coefficient of the resultant polynomials are calculated under a particular modulo. The benefit of NTT is that there are no precision errors as all the calculations are done in integers. A major drawback of NTT is that generally we are only able to do NTT with a prime modulo of the form 2k * c + 1, where k and c are arbitrary constants. So for doing it for a random mod we would need to use CRT (Chinese Remainder Theorem).

Firstly, nth roots of unity under a primitve field, ie.  ± od P are defined as zn = 1 ± od P, where P is only considered as prime for simplicity.

Okay so using Fermat's Little Theorem we know that , where gcd(a, P) = 1, which will be true always when P is prime and a < P.

Here we are assuming that our prime mod P = 2k * c + 1, where c, k are positive integers.

Note — All the calculation done below are done under modulo P including the operations in the power ex. rP + 5 = r5. I have skipped the modulo sometimes as it makes the notation way too ugly.

So we first find a r such that goes through all the numbers from 1 to P - 1 when x goes from 1 to P - 1. Note that is already a fact. After finding one such r, our (2k)th root of unity under the modulo field of P will be rc. The powers will be as

Lemma 1 — Here (rc)x, 1 ≤ x < 2k is not equal to because when x < 2k, this is because r is itself defined as the (P - 1)th root of unity, ie. any power of r less than P - 1 will not be equal to , and as P - 1 = 2k * c, therefore any power of r where c is multiplied by anything less than 2k wont give .

So, rc is now the (2k)th root of unity under the modulo field of P. Now the only difference between NTT and FFT will be that the Nth root of unity changes from w to rc, where r is found by hit and trial method.

Lemma 2 — Another key observation here is that no two (rc)α = (rc)βwhere\alpha \neq \beta$ and both lie between [1, 2k]. This observation can be proven by contradiction, assuming that rc * α = rc * β under then , and which can be generalised to (rc)α + γ = (r^c)^{\beta + \gamma}where\gamma$ is an integer, but we know for a fact that , so lets put γ such that α + γ = 2k, so now . Meaning that if (rc)α = (rc)β then where β + γ ≠ 2k}. This is contradictory to the result mentioned in Lemma 1, hence proved.

Теги fft, ntt, tutorial, polynomials

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en15 Английский sidhant 2016-12-15 15:33:46 24
en14 Английский sidhant 2016-12-14 23:07:59 17 Tiny change: 'mments or as a PM.' -> 'mments or in PM.' (published)
en13 Английский sidhant 2016-12-14 23:06:10 18 Tiny change: 'alculator/vdoozwpsr5)\n\nSo ba' -> 'alculator/obuu9kn9m0)\n\nSo ba'
en12 Английский sidhant 2016-12-14 23:04:18 1 Tiny change: 'rightarrow </h2>\nTo' -> 'rightarrow$ </h2>\nTo'
en11 Английский sidhant 2016-12-14 23:01:06 994 Tiny change: ',2016-12-14] for rect' -
en10 Английский sidhant 2016-12-14 17:40:36 732 Tiny change: 'lp us much BUT THE TRICK is that wh' -i/i
en9 Английский sidhant 2016-12-14 17:02:53 109
en8 Английский sidhant 2016-12-14 16:59:32 373 Tiny change: '/), [LOL](www.apfloat.or' -
en7 Английский sidhant 2016-12-14 16:28:19 7082 Tiny change: ' + \gamma}$ = (r^c)^' -
en6 Английский sidhant 2016-12-14 15:25:04 234
en5 Английский sidhant 2016-12-14 15:16:21 1160 Tiny change: 'Plane.\n\nRotati' -
en4 Английский sidhant 2016-12-14 13:51:17 190
en3 Английский sidhant 2016-12-03 17:52:46 77 Tiny change: 'ame.\n\n![ ](http://c' -
en2 Английский sidhant 2016-12-03 15:01:34 7252
en1 Английский sidhant 2016-12-03 10:29:07 192 Initial revision (saved to drafts)