### lixolas's blog

By lixolas, history, 8 months ago, ,

Hello everyone!

•
• +29
•

 » 8 months ago, # |   +25
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 Is there any generalized way to find 2x2 Walsh-Hadamard Matrix (for any other boolean operation or other kind operation) ?
•  » » 8 months ago, # ^ |   +5 Really thanks!! Did not found this before. I will try solving the problem again later. Thanks again =)
 » 8 months ago, # |   +5 As that link above suggests it is a well known transformation, I solved it that way as well. That being said, could you explain how you figured out the way to get the exact transformation? Just out of curiosity :P
•  » » 8 months ago, # ^ |   +10 Sure! :P First, I supposed that the problem asked for the greatest sum, and how many pairs have that sum. It is a really simple problem, we just have to get the two higher values and count how many times they apear in the original array. However, it can also be solved using FFT: we call the array a polynomial, then we take the square of it. Now, if there was some transformation that the final polynomial stored at the coefficient of x^n how many values had OR n (instead of sum n), it would be great, since the value we want would be index of the last coefficient greater than 0, and the number of pairs that have this OR is exactly this coefficient (or it divided by 2, not really sure :P). So, since FFT solved the first problem, I thought that by some changes it could also solve the other one (since I've heard before about XOR FFT).