zera/bitsquares — pull request #2 by hwv (2014-04-12 18:51:41+00:00)
Title: Computing max square strings with bit tricks

Enumerates binary strings (represented as 64bit unsigned ints) of
length 2^N to find the strings with most distinct squares. Squares are
computed with bit tricks, and only computed for one string from each
equivalence class (reversals+flips preserves equiv.), resulting in
roughly a 4x speedup over considering all strings of length 2^N. The
symmetry is eliminated such that the strings considered are roughly
“uniformly” distributed, which should make it easy to efficiently batch
and parallelize the computation.