  Ranking bit patterns -- finding the index of a given pattern in an ordered
sequence -- is a major bottleneck scaling up numerical quantum many-body
calculations, as fermionic and hard-core bosonic states translate naturally to
bit patterns. Traditionally, ranking is done by bisectioning search, which has
poor cache performance on modern machines. We instead propose to use tries
(prefix trees), thereby achieving a two- to ten-fold speed-up in numerical
experiments with only moderate memory overhead. For the important problem of
ranking permutations, the corresponding tries can be compressed. These
compressed "staggered" lookups allow for a considerable speed-up while
retaining the memory requirements of prior algorithms based on the
combinatorial number system.
