Fast integer matrix multiplication with bit-twiddling hacks
<p>I am asking if it is possible to improve <em>considerably</em> integer matrix multiplication with <a href="https://stackoverflow.com/questions/276706/what-are-bitwise-operators">bitwise operations</a>. The matrices are small, and the elements are small nonnegative integers (small means at most 20).</p>

<p>To keep us focused, let's be extremely specific, and say that I have two 3x3 matrices, with integer entries 0&lt;=x&lt;15.</p>

<p>The following naive C++ implementation executed a million times performs around 1s, measured with linux <code>time</code>.</p>

<pre><code>#include &lt;random&gt;

int main() {
//Random number generator
std::random_device rd;
std::mt19937 eng(rd());
std::uniform_int_distribution&lt;&gt; distr(0, 15);

int A[3][3];
int B[3][3];
int C[3][3];
for (int trials = 0; trials &lt;= 1000000; trials++) {
    //Set up A[] and B[]
    for (int i = 0; i &lt; 3; ++i) {
        for (int j = 0; j &lt; 3; ++j) {
            A[i][j] = distr(eng);
            B[i][j] = distr(eng);
            C[i][j] = 0;
        }
    }
    //Compute C[]=A[]*B[]
    for (int i = 0; i &lt; 3; ++i) {
        for (int j = 0; j &lt; 3; ++j) {
            for (int k = 0; k &lt; 3; ++k) {
                C[i][j] = C[i][j] + A[i][k] * B[k][j];
            }
        }
    }
}
return 0;
}
</code></pre>

<p>Notes:</p>

<ol>
<li>The matrices are not necessarily sparse. </li>
<li><a href="https://stackoverflow.com/questions/1920031/strassens-algorithm-for-matrix-multiplication">Strassen-like</a> comments does not help here.</li>
<li>Let's try not to use the <em>circumstantial</em> observation, that in this <em>specific problem</em> the matrices <code>A[]</code> and <code>B[]</code> can be encoded as a <strong>single</strong> 64 bit integer. Think of what would happen for just a bit larger matrices.</li>
<li>Computation is single-threaded.

<hr></li>
</ol>

<p>Related: <a href="https://stackoverflow.com/questions/18447321/binary-matrix-multiplication-bit-twiddling-hack">Binary matrix multiplication bit twiddling hack</a> and <a href="https://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048">What is the optimal algorithm for the game 2048?</a></p>