popcount

In the original MFFT post the polynomials were written down to single binary digits. The point of that choice was not aesthetics: once every coefficient is \(0\) or \(1\), a pointwise matrix product

\[ C_{ij} = \sum_k A_{ik}\,B_{kj} \]

stops being a general multiply–add. It is the count of positions where both factors are one:

\[ C_{ij} = \#{k : A_{ik}=B_{kj}=1} = \operatorname{popcount}!\bigl(\mathrm{row}_i(A)\ \mathrm{AND}\ \mathrm{col}_j(B)\bigr). \]

No scalar multiply in the leaf. Only bitwise AND and a population count along the contraction index \(k\).

mfft-bench now has that leaf on CPU and GPU. This note is the report: how we got there, what the complexity claim actually means, and the numbers on an RTX 5070 Ti.