Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

A Bitwise Convolution Tutorial

Revision en6, by Anai, 2019-02-12 16:33:52

Here's a bit of shameless self advertising!

I created my own website instead of posting directly on codeforces because I find it much more flexible and adapted for the other articles I intend to write (sorry for the trouble). I have another almost finished article on abstract algebra in competitive programming (mostly number theoretical applications of group theory and some interesting theoretical CS aspects) and I mention it hoping someone will keep nagging me to finish it, as it lays almost done for almost four months.

Also, about this article specifically, you may skip the throwback to the FFT paragraph as it doesn't have much to do with the rest of the article, but reveal some interesting linear algebraic things related to "the classical FFT" and shows the almost ubiquity of kroneker products in linear transform related convolutions. Just keep in mind that you need to know what the kroneker product is.

Feel free to ask questions, make suggestions or tell me I'm stupid! :)

Note: I'd like to thank Pascal Sommer and pleasant for helping me correct some grammar and small calculation mistakes.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English Anai 2019-06-02 12:24:15 6
en6 English Anai 2019-02-12 16:33:52 8 Tiny change: 'mmar and short calculati' -> 'mmar and small calculati'
en5 English Anai 2019-02-12 16:33:22 140
en4 English Anai 2019-02-11 10:05:09 5 Tiny change: 'ns, make some suggesti' -> 'ns, make suggesti'
en3 English Anai 2019-02-11 03:52:07 23 Tiny change: ' questions or' -> ' questions, make some suggestions or'
en2 English Anai 2019-02-11 03:06:57 3 Tiny change: ''m stupid!' -> ''m stupid! :)'
en1 English Anai 2019-02-11 03:05:41 1094 Initial revision (published)