9
\$\begingroup\$

I need to construct a functor that iterates over the linear representation of a sub-lattice of size \$d_x,d_y,d_z,d_q\$ embedded in a lattice of size \$n_x,n_y,n_z,n_q\$. The sub-lattice corner is shifted by \$(l_x,l_y,l_z,l_q)\$. Since the functor can be called million of times, the goal is to produce the most efficient code with the least integer pressure on the CPU.

That is, given ten 16-bit unsigned integers \$d_x,d_y,d_z, n_x,n_y,n_z, l_x,l_y,l_z,l_q\$ with \$d_x\leq n_x\$, \$d_y\leq n_y\$, and \$d_z\leq n_z\$, construct the most efficient function that takes a 64-bit unsigned integer \$0\leq i\lt d_x*d_y*d_z\$ and returns a 64-bit unsigned integer \$j\$ such that if

$$i=i_q (d_z d_y d_x) + i_z (d_y d_x) + i_y d_x + i_x$$

then

$$j=(i_q+l_q)(n_z n_y n_x) + (i_z+l_z)(n_y n_x) + (i_y+l_y)n_x + (i_x+l_x)$$

Winner solution is the one that achieves the stated goal using the least amount of cycles. Solution preferred in x86_64 assembly (pseudo-code is ok). It is ok to use any instruction that belongs to the instruction set available on Intel/AMD cpus of latest generation (SSE4,SSE3,...).

Improve this question
\$\endgroup\$
7
  • \$\begingroup\$ Hi, welcome to PPCG! I saw you've edited your post after it was closed for lacking a win condition. All challenges also need a win-condition tag. Since you've mentioned least amount of cycles, [fastest-algorithm] seems to be the most appropriate. I've added the tag, as well as a few other relevant tags. I've also formatted your post a bit with MathJax. If you see anything incorrect due to my edit, feel free to fix/change it again. \$\endgroup\$
    – Kevin Cruijssen
    Commented Jun 20, 2019 at 15:28
  • \$\begingroup\$ PS: Solutions for a specific language are discouraged, although you can always state you would like to see an answer in a specific language. I've edited your description accordingly, but left the relevant [assembly] tag just in case. \$\endgroup\$
    – Kevin Cruijssen
    Commented Jun 20, 2019 at 15:30
  • \$\begingroup\$ As for the challenge itself. I think you've made some typos in the formulas? I see some \$i_z,i_q,i_y\$, but shouldn't those be \$l_z,l_q,l_y\$ instead? \$\endgroup\$
    – Kevin Cruijssen
    Commented Jun 20, 2019 at 15:31
  • \$\begingroup\$ The integer widths don't work. Shouldn't i and j be 64-bit values? \$\endgroup\$
    – Peter Taylor
    Commented Jun 20, 2019 at 15:46
  • \$\begingroup\$ Thank you Kevin and Peter for cleaning up my original post. Peter is right, i and j should be 64-bit values. I double checked the formulas and they are correct. Essentially, if $$(i_x,i_y,i_z,i_q)$$ are the relative coordinates in the sublattice, the coordinates in the lattice are $$(i_x+l_x,i_y+l_y, i_z+l_z, i_q+l_q)$$. \$\endgroup\$
    – user3646557
    Commented Jun 20, 2019 at 17:24

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.