3
$\begingroup$

I am working on an program to compute the structure factor of a given configuration of particles, and I need an efficient algorithm to generate all the possible vectors with integer coordinates and magnitude between $n-\delta$ and $n+\delta$, where $\delta$ is small compared to $n$. This is equivalent to finding all the solutions to

$$(n-\delta)^2<\| \vec v \|^2<(n+\delta)^2$$

with $\vec v \in \mathbf{Z}^3$.

Of course, I only need to find half of the solutions because the other half will be given by

$$\vec v'=-\vec v$$

What is the best algorithm to solve this problem?

PS This is my first time posting here so any help with the tags would be really appreciated.

$\endgroup$
  • $\begingroup$ Welcome to SciComp.SE! Your question isn't off-topic here, but might actually get better answers at the Computer Science SE. (After all, Knuth's Art of Computer Programming has a whole volume (4) devoted to such combinatorial generation problems.) $\endgroup$ – Christian Clason Jun 28 '16 at 13:45
  • $\begingroup$ @ChristianClason Thank you, I didn't know of the existence of this SE. I will post this question on Computer Science SE too. $\endgroup$ – valerio Jun 28 '16 at 13:53
  • 1
    $\begingroup$ You might wish to wait for a bit first, and at least mention (i.e., link to) the other version of the question. Cross-posting is discouraged on the StackExchange network in general. $\endgroup$ – Christian Clason Jun 28 '16 at 13:57
  • $\begingroup$ @ChristianClason Ok, then I will wait. Thank you. $\endgroup$ – valerio Jun 28 '16 at 14:08
  • 2
    $\begingroup$ You have an eight-fold symmetry, not just two-fold. Also: there are $O(n^2\delta)$ solutions, so if $\delta=\Omega(1)$, you can't do asymptotically better than just the straightforward iteration as in Jannis's answer. $\endgroup$ – Kirill Jun 28 '16 at 23:11
3
$\begingroup$

What about a simple nested loop to give you one octant of the solution, which can then be copied due to symmetry:

$i$ from 0 to $d+n$

$j$ from 0 to $\sqrt{(d+n)^2-i^2}$

$k$ from $\sqrt{(d-n)^2-i^2-j^2}$ to $\sqrt{(d+n)^2-i^2-j^2}$, where the minimum bound is 0 if $i^2+j^2 > (d-n)^2$.

You have to round off to the 'smallest' integer range.

| cite | improve this answer | |
$\endgroup$

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.