Boolean Multiplication

[Peter Schäfer]

Hello,

I have extended M4RI to multiplication over the Boolean semiring. To put it short, XOR addition is replaced by OR. Cubic and M4R multiplication is available (but not Strassen).

I would like to contribute my code. Can I create a pull request ?

Regards, Peter

[Martin Albrecht]

Sure, I see no reason why not in principle.

[Peter Schäfer]

Looks like I'm missing some privileges. Could you please grant me rights to create a pull request ?

My code for Boolean matrix multiplication is mostly identical to the original code. The differences are not large:

(1) addition is done using bitwise OR (instead of XOR)

(2) in cubic multiplication, there's no need to calculate parity. Instead I look for the first entry != 0, and leave the loop early.

(3) M4R lookup tables are calculated in different order. Your elegant loop over Gray codes doesn't work for me, because I can't subtract rows. Instead, table rows are summed in order of increasing Hamming weights (number of set bits). The resulting tables are still indexed by Gray codes, so everything else remains the same. Also, complexity does not increase.

Regards, Peter

[Martin Albrecht]

Strange, doesn't everybody have the right to create a PR? I can't find an option to specifically enable it.

[Peter Schäfer]

Can't push to the repository. I have attached my sources.

[Martin Albrecht]

Sorry if I'm misunderstanding but you should fork this repository, then push to that and then finally send a PR from your fork to this repository.

[Egor Basharin]

Hello,

I forked the repository and merged aforementioned sources with it. Also I created a pull request.

[Egor Basharin]

@hrimfaxi , I added you as user of forked repository