Given a ring of size $n = 2^m$, starting with element $0$ to element $n-1$, what general formula gives the distance between two arbitrary elements $i$ and $j$? Note that the distance between the elements $0$ and $n-1$ is $1$.

There are a few cases...

  • Assume for instance that $i>j$ and $|i-j|\leq\frac{n}{2}=2^{m-1}$, we then have $distance_{n}(i,j) = |i-j|$

  • But for $\frac{n}{2} < |i-j| \leq n-1$, we need another formula. For e.g. let $n = 8$, then the distance between $1$ and $7$ is $1$, not $|7-1|=6$

What is the general, one-line formula for this problem?

Thank you!

  • 2
    $\begingroup$ Would $\min ( |i-j|,n+1-|i-j|)$ work? $\endgroup$ – coffeemath Feb 15 '15 at 11:34
  • $\begingroup$ @coffemath Yes, this is what I needed. Actually it is $\min ( |i-j|,n-|i-j|)$. You added 1 because I incorrectly gave you the distance between 1 and 7 as 2 while it is 1; you took it into account. Thank you! $\endgroup$ – Symeof Feb 15 '15 at 14:36

Answer: $distance_{n}(i,j) = \min ( |i-j|,n-|i-j|)$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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