项目作者: Stamaks

项目描述 :
The code implements Four Russians Algorithm for boolean matrices multiplication
高级语言: Python
项目地址: git://github.com/Stamaks/FourRussiansImplementation.git
创建时间: 2021-03-20T14:26:26Z
项目社区:https://github.com/Stamaks/FourRussiansImplementation

开源协议:

下载


Implementation of Four Russian’s Algorithm for boolean square matrices multiplication

Quick start

Clone the repository, open the project folder in your terminal and run:

  1. python3 src/main.py

Here is the example of the main scenario:

  1. four_russians_impl$ python3 src/main.py
  2. Welcome to the 4 Russians algorithm implementation!
  3. NOTE: The algorithm works only with boolean square matrices!
  4. Each matrix size is n x n, enter n (just one integer number):
  5. 3
  6. Please, enter the first boolean matrix, size 3 x 3:
  7. 1 0 1
  8. 0 0 1
  9. 1 1 1
  10. The first matrix is:
  11. 1 0 1
  12. 0 0 1
  13. 1 1 1
  14. Enter the second boolean matrix, size 3 x 3:
  15. 1 0 0
  16. 1 1 1
  17. 1 1 0
  18. The second matrix is:
  19. 1 0 0
  20. 1 1 1
  21. 1 1 0
  22. The final matrix is:
  23. 0 1 0
  24. 1 1 0
  25. 1 0 1
  26. Want to run the algorithm again? Enter y/n
  27. n

At first you will be asked to enter matrix size. Enter just one integer number.
Then enter your matrices one by one in the following format:

  1. 1 0 1
  2. 0 1 1
  3. 1 1 1

This is what 3 x 3 matrix should like (regardless spaces). If you enter a number that is less than 0 or more than one, or any other format mistake, you will be asked to re-enter the matrix.
Finally, the program will perform the multiplication and the result will be shown.

How does it work?

Main logic can be found here: src/lib/matrices_multiplication.py

At first, the binary log of matrices size is calculated, let’s call it k. For each pair of numbers from range (0, 2^k - 1) we calculate bitwise AND and see if the number of bits equal to 1 is odd. If it is, the bitwise AND is put into the set. We’ll need it later. This operation takes O(2^(k*2*k)) time. Precalculated set is dumped into the .data/k file just to minimize the furher runs’ calculations.
Then each matrix is being compressed. If the matrix is the first one, each row is divided into vectors of size k (otherwise - each col). Each binary vector represents a decimal number. We calculate the number and put it elementwise to the compressed matrix. It takes us O(2*n^2) time for both matrices.
After that, we “multiply” two compressed matrices. Though, instead of element wise multiplication, we do bitewise AND and then lookup the result in the precalculated set. If it is there, we put 1 in the result matrix. Otherwise, put 0.

The algorithm asymptotics is O(n^3/logn). Actually, in this implemntation it should be multiplied by a constant of bitwise AND, which depends on one’s processor (yet, it still remains a constant).