Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm sorry, if I got the wrong expressions, I'm gonna describe it:

I got bit-strings of n bits with k ones and want to minimize "collision" The collision count of two strings $a=(a_1,...,a_n), b=(b_1,...,b_n)$ is defined by $$Coll(a,b):=\sum_{i=1}^n a_i b_i$$ and $a,b$ are said to "collide", if $Coll(a,b)>0$. Of course this can be generalized to higher number of strings.

Now I'm looking for a "shift" $s$ (depending on $a$), that minimizes the shifted self-collision $$\sum_{i=1}^n a_{i+s}a_i $$ and (if possible) the $m$-fold shifted self-collision $$\sum_{i=1}^n\prod_{j=1}^m a_{i+js} $$ ($i+s>n$ may be replaced by $i^\prime\in\{1,...,n\}$ with $i^\prime\equiv i+s$ (mod n))

Now my questions are:

  1. Is this solvable faster than $O(n²)$? (computing the collision count for a shift needs $O(n)$ and there are at most $n$ shifts
  2. I'm coding my bit-strings by length of consecutive 0s between two 1s $(10011 \rightsquigarrow 200 )$. Does this help to compute the collision count without translating back to the bit-string?
  3. Is there already any theory on that?
share|cite|improve this question
On 2.: Yes, it helps if the bit strings are sparse; you can just keep track of the numbers of zeros left in the current run in both strings, and when they reach $0$ simultaneously you have a collision. If they're not sparse, this will be inefficient compared to just ANDing them a word at a time and looking up the bit counts in a table. – joriki Aug 10 '12 at 13:12
up vote 1 down vote accepted

For the first question: Your "shifted self collision" is the same as a circular autocorrelation, so it can be computed using Fourier transform, which is $O(n \log(n))$

For example (Matlab/Octave)

 x=[1, 1, 0, 1, 0 ,0  ,0 ,0 ];
 y =
     3   1   1   1   0   1   1   1
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.