5
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,...).
user3646557
Posted 2019-06-20T13:25:38.357
Reputation: 51
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,
– Kevin Cruijssen – 2019-06-20T15:28:52.070[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.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. – Kevin Cruijssen – 2019-06-20T15:30:02.737As 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? – Kevin Cruijssen – 2019-06-20T15:31:16.993
The integer widths don't work. Shouldn't i and j be 64-bit values? – Peter Taylor – 2019-06-20T15:46:45.040
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)$$. – user3646557 – 2019-06-20T17:24:59.753
@user3646557 Ah ok, that makes sense. And now that Peter has edited the formulas further I can also see the $(i_q+l_q),(i_z+l_z),(i_y+l_y),(i_x+l_x)$ grouped together, making it more readable. I personally still don't really grasp how I could calculate this, since mathematics isn't my strongest suite tbh, but I've voted to re-open since regardless of my own lack of skill, the challenge is clear and it has a win-condition tag now. If 5 open-votes are cast and it's re-opened, perhaps someone is able to answer your question (with an efficient algorithm). :) – Kevin Cruijssen – 2019-06-21T06:30:55.197
@Kevin, it's a mixed base conversion. – Peter Taylor – 2019-06-21T13:07:47.777