Compute the XOR of all the elements in the upper left triangular of a square matrix

Question

Given a dimension \$D\$. We generate a \$D\times D\$ matrix with elements that start from \$0\$. For example, if we're given a dimension \$4\$ this is what our matrix looks like: $$ \begin{bmatrix} 0 & 1 & 2 & 3 \\ 4 & 5 & 6 & 7 \\ 8 & 9 & 10& 11\\ 12& 13& 14& 15\\ \end{bmatrix} $$

Now compute the XOR all of the elements in the upper triangular of the square matrix

0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 8 ^ 9 ^ 12 gives us 10

def computeXOR(dimension):
    XOR = 0
    begin = 0
    for i in range(dimension):
        for j in range(dimension-i):
            XOR ^= begin + (j + i*dimension )
    return XOR

#computeXOR(4) returns 10

I'm trying to think of a faster algorithm to XOR all of the elements in the upper triangular of a square matrix. My current solution is \$O(n^2)\$.

Answer 1

You will need to look at \$O(n^2)\$ elements, therefore there is no algorithm that runs faster than \$O(n^2)\$.

That is, unless you have an explicit formula for the solution which abuses the fact that the elements are all consecutive.

Notice what these XOR to:

      cumulative XOR
0 000 000
1 001 001 |
2 010 011 |
3 011 000 |
4 100 100 |
5 101 001
6 110 111
7 111 000

We'll notice a few patterns. The cumulative XOR of all elements \$\lt 2^k\$ for any k is 0.

Here's another, more useful pattern: for any run of \$2^k\$ consecutive elements (e.g. see markers above), all binary digits except the most significant bit will repeat. Therefore we can explicitly compute the XOR of an arbitrarily large sequence \$a \ldots b\$ of length \$2^k\$ in one step (it's all 0s except the most significant digit is b - max(a, largestPowerOf2LessThanB) % 2, I think, where \$\mathrm{largestPowerOf2LessThanB} = 2^{\lfloor\log_2(b)\rfloor}\$).

Therefore we can calculate the sum of any arbitrarily large sequence in roughly \$O(\log(k))\$ steps.

Thus you can make an algorithm with running time \$O(n\log(n))\$ using this explicit formula.

You can maybe make it even faster if you can calculate contiguous blocks of the matrix?

Answer 2

Consider a pair of consecutive integers of the form (2K+0, 2K+1). When XOR'd these values will demonstrate destructive interference in every bit but the 1's bit. Examples:

010 (2)    110 (6)
011 (3)    111 (7)
-------   --------
001 (1)    001 (1)

Consider a given row ranging from:

L = [S+0, S+1, ... S+(W-1)]

The XOR operation is commutative and associative, meaning that we can resolve the XOR operation upon this row in any order we would like and can move the last and first elements anywhere else in the ordering as convenient while preserving the result.

If the head element of S+0 is odd then the destructive partner to its left is out of range. If this proves true then let us temporarily remove the head from the list for convenience.

If the tail element of S+(W-1) is even then the destructive partner to its right is out of range. If this proves true then let us temporarily remove the tail from the list for convenience.

We now may guarantee a list of the following form:

L' = [ 2k+0, 2k+1, ... 2k+(w'-2), 2k+(w'-1) ]

Consider now how this list will look after processing each destructive pair with XOR operation:

[ 1, ... 1] //total length of w' / 2

By inspecting the parity of the length of the sublist (w') we may resolve the result of the entire arbitrarily sized sublist with a single operation. if 4 divides w' then the sublist resolves 0, otherwise it will resolve 1 as the size of the list is even but the count of destructive pairs is odd.

Lastly we will XOR the head and tail items with the retrieved result from the rest of the list. For calculating the XOR over a range interval this will allow processing in \$O(1)\$ time complexity.

The next step in addressing the problem is the specific instance of calculating the upper left partition of the matrix to calculate:

XOR(M[i,j]) for all (i,j) such that i + j < w

The simplest means to achieve this is now to calculate the range-based XOR for each row partition of the matrix and take the result. Below is a simple C++ program achieving this in \$O(W)\$ time which may easily be converted to Python:

#include <iostream>
#include <bitset>

//#calculates XOR of range interval in O(1) time
unsigned fastXOR(unsigned x, unsigned N) {
    //trivial cases
    switch (N) {
        case 0:
            return 0;
        break;
        case 1:
            return x;
        break;
        case 2:
            return x ^ (x + 1);
        break;
        default:
            //#at least 3 items to XOR
        break;
    }

    //#if head odd then decrement count and pop head out
    unsigned head = (x & 1) ? (N--, x++) : 0;

    //#if tail even then decrement count and pop tail off
    unsigned tail = (N & 1) ? (x + (--N)) : 0;

    //#if remaining list divides by 2 but not 4 then odd parity added
    unsigned parity = (N % 4) ? 1 : 0;

    return parity ^ head ^ tail;
}

//#calculates XOR of upperleft of NxN range interval matrix in O(N) time
unsigned upperLeft(unsigned x, unsigned N) {
    unsigned rv = 0;
    for (unsigned i = 0; i < N; i++) {
        //#for each row calculate with only valid
        //#member portion of length N
        rv = rv ^ fastXOR(x + i * N, N - i);
    }
    return rv;
}

//# x notes starting position of range, N notes matrix WIDTH (full size is Width squared)
void performTest(unsigned x, unsigned N) {
    constexpr unsigned uSize = sizeof(unsigned) * 8;
    typedef std::bitset<uSize> bits;
    auto R = upperLeft(x,N);
    bits xb(x);
    bits Nb(N);
    bits Rb(R);
    std::cout << "F(" << xb << ", " << Nb << ") -> " << Rb << " = " << R << std::endl;
}

int main() {

    performTest(0, 100);
    performTest(132, 400000);

    return 0;
}