On 01/04/2016 18:46, Warren D Smith wrote:
On 4/1/16, Warren D Smith <warren.wds@gmail.com> wrote:
Be nice if one could create an NxN bit-matrix (for example N=machine's wordsize) and then multiply it (mod 2) by an N-element bit vector (e.g machine word) in 1 instruction.
This would help with cryptography, error correcting codes, and probably a lot of other stuff.
--such as permuting bits in a word, would be another application.
Also, if the XORs that were used to add up the sums mod 2, were replaced by plain ORs, then that other kind of matrix-vector "multiply" would be excellent for graph connectivity calculations.
As Henry Baker says, Knuth has proposed something very much along these lines: see http://mmix.cs.hm.edu/doc/instructions-en.html#Bit_Operations and look in the section headed "Mix and Match". His MXOR operation is an 8x8 matrix multiplication over GF(2), and his MOR operation is the same with OR instead of XOR for the addition. It's matrix * matrix rather than matrix * vector, and the size is chosen so that the whole matrix (rather than just one row or column) fits in a (64-bit) machine word. -- g