Efficient Counting

Dana Jansens

In order to count from 0 to 2d-1, we require a bit string of dimension at least d. Consider a sequence of bit strings of dimension d, where each string differs from the next in a constant number of bits, and the same holds for the first and last strings in the sequence. We call this sequence a cyclic quasi-Gray code. In order to count using this sequence of bit strings, we must generate each bit string using the previous string as the input.

We examine the problem of efficiently generating quasi-Gray codes, by considering the number of bits read and written at each generating step, the average number of bits read while generating the entire code, and the number of strings generated in the code. Our results give a trade-off between these four constraints, and present algorithms which do less work on average than previous results, while also increasing the number of strings generated.

First we will examine a novel algorithm for generating sequences of length 2d using d bits, while keeping the average bits read to O(log d). Then we will use this to build algorithms that lead to a method for generating sequences of length arbitrarily close to 2d using d bits, while reducing the worst case number of bits read to O(log d), and keeping the number of bits written to a constant. Finally, we improve our algorithm to read on average no more than O(log(2c) d) bits, while writing at most 2c+1 bits, for any non-negative integer c.