| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
Hello Codeforces !
I invite all of you to read my first article. It is about Fast Fourier Transform and other two linear transformations. Feel free to comment and ask any question that comes into your mind. Any positive or negative feedback is welcome, too.
Link : https://csacademy.com/blog/fast-fourier-transform-and-variations-of-it
Thank you for this article. How can the bitwise xor formula be proved for Walsh-Hadamard transform?
Hi Nikita, I added some information about that in the article. (in section "How to determine the Walsh-Hadamard Matrix (my approach)"). Thank you!
You got two things slightly wrong. Fast Walsh–Hadamard transform is very quite like FFT. Walsh-Hadamard transformation is just N-dimensional version of Fourier Transform. You do not xor the powers of x, you multiply monoms of N variables (by modulo x2-1 for each variable of course).
There are multiple ways to calculate N-dimensional Fourier Transform. The trivial one is to make Fourier Transform along each dimension. If you use "slow" version of transform, you will need O((N1+N2+...+Nk)N1N2...Nk) time for N1×N2×...×Nk k-dimensional hypercube. If you use FFT for each transform, you will need O((log(N1)+log(N2)+...+log(Nk))N1N2...Nk) time. There are other algorithms, some of which even work for O(N1N2...Nk) time for some hypercubes.
The second thing, you can create N-dimensional version of any linear transformation. There is no need "to do some math". Just choose any invertible matrix and create N-dimensional version of the matrix and its inverse just like in N-dimensional Fourier Transform. In practice, I have never seen anything other than three ones and one zero 2×2 matrices or their inverses though.
Hi Andrey, I would like to thank you for reading my article. I tried to do my best reproducing what helped me to understand FFT better. I know that "using xor at power" is not the best mathematical explanation, but i found it useful. However, I wish you enjoyed the article. Any other suggestion is welcome, too :)
Now that you know a better mathematical model, use it! You should probably also mention how to do FFT over whole numbers by choosing a good modulo. It is very common technique.
As a side note, the Walsh transform is used a lot in cryptography. It allows to measure "linearity" of a boolean function. Just apply FWHT to the truth table with 0s replaced by -1. The resulting values tell how "good" is each mask m as a linear approximation < m, x > (scalar product over
) of the original boolean function .
Also quite often the notation
is used, so the atatomir's "xor at power" is ok. Maybe the multidimensional view of it allows to explain it better, but I still don't get it. Mainly, how each dimension's FFT is connected with others?
The fact that we can do "binary AND at powers" really surprised me, as I don't see what exactly is linear here. What are the limitations of FFT? In what cases the desired transformation will be nonlinear?
I guess the "math" here is to find the right matrix (for example for binary AND). Is there a simple way?
Hi hellman1908, Thank you for your appreciation. I did't know this use of FWHT (in cryptography). I was really surprised when i found the matrix for
and, too. I can guess that the matrix fororcan be also determined. The method that i used to find it is similar to the one presented in the article (section "How to determine the Walsh-Hadamard Matrix (my approach)"). Just change the result of convolution. This lack of limitations of FFT fascinated me. You can use (+, -, xor, and, or). Another interesting approach of FFT is to replacecomplex rootswithroots of unit in modulo(halyavin suggestion).I don't really get how to do N-dimensional Fourier Transform. What would be the Point-value Representation for a N-variable polynomial?
Instead of
we have
So which point values would we choose to evaluate? All n-tuples of roots of unities?
Exactly!
When we calculate the inverse FFT instead we divide by n, so if we want to calculate inverse for n-dimensional FFT we will divide by n1n2...nk?
Yes.
Who is the target audience for your article? It looks like a person should already know about polynomials, polynomial interpolation (as you assume that two representations of polynomials are obviously correct), and have a pretty solid understanding of everything except FFT in order to understand it.
I find the article to be very brief and sketchy, for me it looks more like a "memo for those who already know FFT" rather than a full-blown educational article which tells you how and why it works. There is an idea and after three lines it suddenly becomes recursive implementation, and in the next paragraph you go right to the non-recursive implementation, without any comments or thought about how it was done. I personally think that code is fine for demonstrating implementation details of an algorithm, but not for describing the algorithm itself.
Hi Egor, All I wanted to do is to make an introduction to FFT and present two other linear transformations that can run in O(n*log(n)). I still have a lot to learn in order to present a more complex article. That's what i could write for the moment. Thank you for your feedback.
Seems related to these two TC editorials (D1-1000):
https://apps.topcoder.com/wiki/display/tc/SRM+518 https://apps.topcoder.com/wiki/display/tc/TCO+2012+Round+2A
You are right. I used the solution of task
Nimfrom SRM 518 as starting point to find the last matrix. ;)Thanks for that article. Excuse but I wonder that can we use a fast tranform for the min-max operator ? sorry for my poor english !
Thank you for your question :) You do not need to use FFT in this case. Some simple partial sums are enough. I will present the solution for the MAX operator. Let a[i] = coefficient of x^i; s[i] = sum of coefficient of x^j (where j <= i); If you want to compute the resulting coefficient of x^i you can apply the following formula: ans[i] = 2 * a[i] * s[i-1] + a[i] * a[i]. (only if you "multiply" one polynomial with itself, otherwise use a1, s1, a2, s2) If you want to compute the number of subsets of a set that have their max equal to i then the following formula should work : ans[i] = (2^(a[i]) — 1) * (2^(s[i — 1])). Please let me know if you have other questions or if anything above seems unclear :)
Great article!
I think the correct H matrix for XOR in Fast Walsh–Hadamard transform is
for n > 2 and 
where n is number of polynomial elements (degree(polynomial) + 1). Because if it was 
for n > 2 and 
, The appropriate steps to be taken for multiplication without using the 
would be:
But since we are dividing only by n at the end regardless of the multiplications done in step 3, the correct H should be as I mentioned in the beginning, and so its inverse would be
for n > 2 and 
. And this explains why division by n at the end is enough, as 
.
Is this correct or did I miss something?
Hi. So I am very new to these convolutions stuff. I have learnt how the FFT DnC algorithm works. However I am not able to correlate a similar fast walsh-hadamard transform algorithm from the H matrices itself. Could someone give some resource/ explain how we exactly formulate the algorithm from this recursively defined matrix...
(PS: It would be nice if you could also give an intuition as to how the vandermonde matrix is related to FFT, as its not immediately clear for me from the algorithm.) Thanks for any help.
Hello,
I came across this post while trying to solve Winning Ways (MDSWIN) from November Challenge 2019 on CodeChef. I tried
probably not enoughto derive 3x3 transformation matrix for "3-xor" using the method from article but failed. Can anyone show the fast derivation? Editorial is hereThank you very much
UPD: the discussion was really helpful