We consider the bit matrix (nxm) as regular integer arrays of size m containing n rows.
I looked in Hacker Delight, and in other sources the algorithms that I found for this were quite specialized: square matrices of two, 8x8, 32x32, 64x64 in size (which is normal, because the machine is constructed in this way).
I was thinking of a more general algorithm (for any n and m), which, in the worst case, is expected complexity (I think), but for matrices containing mostly similar columns or more zeros than the algorithms, the algorithm seems a little more interesting (in as a last resort, it is linear if the matrix contains the same row again and again). This follows a form of binary decision manipulation.
The output is not a transposed matrix, but a compressed transposed matrix: a list of pairs (V, L), where L is int_m, which indicates the lines of the transposed matrix (by setting the bits of the corresponding position), which should contain int_n V. The lines of the transposed matrix that are neither into one of the pairs, 0 is filled.
For example, for a matrix
1010111 1111000 0001010
with transposed
110 010 110 011 100 101 100
algorithm outputs (010,0100000) (011,0001000) (100,0000101) (101,0000010) (110,1010000) and one reads a pair (100,0000101) as the value "value 100 is placed in the 5th and 7th rows of the transposed matrix. "
This is an algorithm (written in pseudo-OCaml / C) and an image of the progress of the algorithm in the above example.
We will run according to triples (index_of_current_line, V, L), which is of type (int, int_n, int_m) , where int_n is the type of n-bit wide integers, and int is just a machine integer wide enough to hold n. The function takes a list of these triples, a matrix, the number of rows and a battery for output (a list of pairs (int_m, int_n)) and returns this battery at some point.
list of (int_n, int_m) transpose(list of triple t, int_m[n] mat, int n, list of (int_n, int_m) acc)
The first call to the transpose function
transpose([(0, 0, 2^m-1)], mat, n, []).
take "&", "|" "xor" - ordinary bitwise operations
transpose(t, mat, n, acc) = match t with | [] -> (* the list is empty, we're done *) return acc | (i, v, l)::tt -> let colIn = mat[i] & l in (* colIn contains the positions that were set in the parent mask "l" and that are also set in the line "i" *) match colIn with |0 -> (* None of the positions are set in both, do not branch *) if (i<n) then (* not done with the matrix, simply move to next line *) transpose((i+1,v,l)::tt,mat,n,acc) else (* we reached the end of the matrix, we're at a leaf *) if (v>0) then transpose(tt,mat,n,(v,l)::acc) else (* We ignore the null values and continue *) transpose(tt,mat,n,acc) |_ -> (* colIn is non null, ie some of the positions set at the parent mask "l" are also set in this line. If ALL the positions are, we do not branch either. If only some of them are and some of them are not, we branch *) (* First, update v *) let vv = v | (2^(ni-1)) in (* Then get the mask for the other branch *) let colOut = colIn xor l in, match colOut with | 0 -> (* All are in, none are out, no need to branch *) if (i<n) then transpose((i+1,vv,colIn)::tt,mat,n,acc) else (* we reached the end of the matrix, we're at a leaf *) transpose(tt,mat,n,(vv,colIn)::acc) | _ -> (* Some in, some out : now we branch *) if (i<n) then transpose((i+1,vv,colIn)::(i+1,v,colOut)::tt,mat,n,acc) else if (v>0) then transpose(tt,mat,n,(vv,colIn)::(v,colOut)::acc) else transpose(tt,mat,n,(vv,colIn)::acc)
Note that if the matrix is wider than high, it is even faster (if n = 3 and m = 64, for example)
My questions: Is it interesting and / or useful? Am I reinventing the wheel? Are almost-zero matrices or “small differentiated lines” common enough for this to be interesting?
PS: If something does not seem clear, tell me, I will rewrite everything that should be!