src/conv/trans/fft_r3/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../math/ds/eint/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | template <class T> | ||
| 8 | class fft_r3 { | ||
| 9 | using EI = eint<T>; | ||
| 10 | u32 s = 1; | ||
| 11 | vec<EI> tmp; | ||
| 12 | |||
| 13 | public: | ||
| 14 | using data_t = eint<T>; | ||
| 15 | |||
| 16 | 26 | ND CEXP u32 size() CNE { return s; } | |
| 17 | 26 | CEXP void bzr(u32 len) NE { | |
| 18 |
2/2✓ Branch 0 taken 297 times.
✓ Branch 1 taken 26 times.
|
323 | for (; 2 * s < len; s *= 3); |
| 19 | 26 | tmp.resize(s * 3); | |
| 20 | 26 | } | |
| 21 | |||
| 22 | // Calculate the product of polynomial {@code f} and $x^t$ in $T[x]/(x^m - \omega)$ | ||
| 23 | // result is in {@code to} | ||
| 24 | 15403284 | CEXP void twiddle(data_t* p, u32 m, u32 t, data_t* to) CNE { | |
| 25 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 15403284 times.
|
15403284 | assert(t <= 3 * m); |
| 26 |
4/4✓ Branch 0 taken 12016836 times.
✓ Branch 1 taken 3386448 times.
✓ Branch 2 taken 1693224 times.
✓ Branch 3 taken 10323612 times.
|
15403284 | if (!t || t == 3 * m) { |
| 27 | 5079672 | copy_n(p, m, to); | |
| 28 | 5079672 | return; | |
| 29 | } | ||
| 30 | u32 n; | ||
| 31 | 10323612 | data_t _0, _1; | |
| 32 |
2/2✓ Branch 0 taken 5161806 times.
✓ Branch 1 taken 5161806 times.
|
10323612 | if (t < m) n = t, _0 = 1, _1 = EI::w; |
| 33 |
2/2✓ Branch 0 taken 2580903 times.
✓ Branch 1 taken 2580903 times.
|
5161806 | else if (t < 2 * m) n = t - m, _0 = EI::w, _1 = EI::w2; |
| 34 | 2580903 | else n = t - 2 * m, _0 = EI::w2, _1 = 1; | |
| 35 |
2/2✓ Branch 1 taken 267098310 times.
✓ Branch 2 taken 10323612 times.
|
277421922 | flt_ (u32, j, 0, n) to[j] = p[m - n + j] * _1; |
| 36 |
2/2✓ Branch 1 taken 267098310 times.
✓ Branch 2 taken 10323612 times.
|
277421922 | flt_ (u32, j, n, m) to[j] = p[j - n] * _0; |
| 37 | } | ||
| 38 | // @param p A polynomial from $(T[x]/(x^m - \omega))[y]/(y^r - 1)$ | ||
| 39 | // result: Fourier transform (w.r.t. y) in 3-reversed order, inplace. | ||
| 40 | 124520 | CEXP void dif(data_t* p, u32 m, u32 r) NE { | |
| 41 |
2/2✓ Branch 0 taken 371892 times.
✓ Branch 1 taken 124520 times.
|
496412 | for (u32 rr = r / 3; rr >= 1; rr /= 3) |
| 42 |
2/2✓ Branch 0 taken 1630964 times.
✓ Branch 1 taken 371892 times.
|
2002856 | for (u32 k = 0; k < r; k += rr * 3) |
| 43 |
2/2✓ Branch 0 taken 3441204 times.
✓ Branch 1 taken 1630964 times.
|
5072168 | flt_ (u32, i, k, k + rr) { |
| 44 |
2/2✓ Branch 0 taken 178065540 times.
✓ Branch 1 taken 3441204 times.
|
181506744 | flt_ (u32, j, 0, m) { |
| 45 | 178065540 | tmp[j] = p[i * m + j] + p[(i + rr) * m + j] + p[(i + 2 * rr) * m + j]; | |
| 46 | 178065540 | tmp[m + j] = p[i * m + j] + EI::w * p[(i + rr) * m + j] + EI::w2 * p[(i + 2 * rr) * m + j]; | |
| 47 | 178065540 | tmp[2 * m + j] = p[i * m + j] + EI::w2 * p[(i + rr) * m + j] + EI::w * p[(i + 2 * rr) * m + j]; | |
| 48 | 178065540 | p[i * m + j] = tmp[j]; | |
| 49 | } | ||
| 50 | 3441204 | twiddle(tmp.data() + m, m, 3 * (i - k) * m / (rr * 3), p + m * rr + i * m); | |
| 51 | 3441204 | twiddle(tmp.data() + 2 * m, m, 6 * (i - k) * m / (rr * 3), p + 2 * m * rr + i * m); | |
| 52 | } | ||
| 53 | 124520 | } | |
| 54 | // @param p A polynomial in $(T[x]/(x^m - \omega))[y]/(y^r - 1)$ with coefficients in 3-reversed order. | ||
| 55 | // result: inverse Fourier transform in normal order, inplace. | ||
| 56 | 62260 | CEXP void dit(data_t* p, u32 m, u32 r) NE { | |
| 57 |
2/2✓ Branch 0 taken 185946 times.
✓ Branch 1 taken 62260 times.
|
248206 | for (u32 rr = 1; rr < r; rr *= 3) |
| 58 |
2/2✓ Branch 0 taken 815482 times.
✓ Branch 1 taken 185946 times.
|
1001428 | for (u32 k = 0; k < r; k += rr * 3) |
| 59 |
2/2✓ Branch 0 taken 1720602 times.
✓ Branch 1 taken 815482 times.
|
2536084 | flt_ (u32, i, k, k + rr) { |
| 60 | 1720602 | twiddle(p + m * rr + i * m, m, 3 * m - 3 * (i - k) * m / (rr * 3), tmp.data() + m); | |
| 61 | 1720602 | twiddle(p + 2 * m * rr + i * m, m, 3 * m - 6 * (i - k) * m / (rr * 3), tmp.data() + 2 * m); | |
| 62 |
2/2✓ Branch 0 taken 89032770 times.
✓ Branch 1 taken 1720602 times.
|
90753372 | flt_ (u32, j, 0, m) { |
| 63 | 89032770 | tmp[j] = p[i * m + j]; | |
| 64 | 89032770 | p[i * m + j] = tmp[j] + tmp[m + j] + tmp[2 * m + j]; | |
| 65 | 89032770 | p[(i + rr) * m + j] = tmp[j] + EI::w2 * tmp[m + j] + EI::w * tmp[2 * m + j]; | |
| 66 | 89032770 | p[(i + 2 * rr) * m + j] = tmp[j] + EI::w * tmp[m + j] + EI::w2 * tmp[2 * m + j]; | |
| 67 | } | ||
| 68 | } | ||
| 69 | 62260 | } | |
| 70 | }; | ||
| 71 | |||
| 72 | } // namespace tifa_libs | ||
| 73 |