Anai's blog

A Bitwise Convolution Tutorial
By Anai, history, 5 years ago, In English

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.

  • Vote: I like it
  • +120
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Wiki Link for Kronecker Product for those (like me) who didn't know what it meant.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I mean, there's also a link on the page (the red-brownish strings are links).

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Oh, I didn't read your post properly and thought the article was yet to come out.

      I really like your writing style and website design. Also, it's the sort of stuff that I want to study. Thanks for sharing.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh, thank you. That's a very cute thing to say ^^

        → Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

This is a cool way of thinking about these transformations :)

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice article. This StackExchange comment is useful in understanding how to convert the matrix into code.

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hey Anai one of my friend referred me to this link,but it's not working now, can you please provide some source to your blog or may be you can post content somewhere else.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is also fft and variants topic where bit convolution is explained, on csacademy

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    So, it took me a month to finally admit to myself that I don't have the time, the need or the skills to deploy a react/flask app (indeed, an overkill), so I've uploaded the old PHP version and it should take a while for the domain name to update. Till then, you can find the website here.

    → Reply