0
$\begingroup$

I'm trying to speed up the following function in c++:

void num_to_xy(int num, int *x, int *y):
    *x = (cl & 0x03) | ((cl & 0x10) >> 2) | ((cl & 0x40) >> 3) | ((cl & 0x100) >> 4) | ((cl & 0x400) >> 5) | ((cl & 0x1000) >> 6) | ((cl & 0x4000) >> 7);
    *y = ((cl & 0x0c) >> 2) | ((cl & 0x20) >> 3) | ((cl & 0x80) >> 4) | ((cl & 0x0200) >> 5) | ((cl & 0x0800) >> 6) | ((cl & 0x2000) >> 7) | ((cl & 0x8000) >> 8);

which basically converts num to an x,y coordinate. This is equivalent to getting the x,y position of num in the following array

$\left| \begin{array}{ccc} 0 &1 &4 &5 &16 &17 &20 &21 &...\\ 2 &3 &6 &7 &18 &19 &22 &23 &...\\ 8 &9 &12 &13 &24 &25 &28 &29 &...\\ 10 &11 &14 &15 &26 &27 &30 &31 &...\\ 32 &33 &36 &37 &48 &49 &52 &53 &...\\ 34 &35 &38 &39 &50 &51 &54 &55 &...\\ 40 &41 &44 &45 &56 &57 &60 &61 &...\\ 42 &43 &46 &47 &58 &59 &62 &63 &...\\ \vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\ddots & \end{array} \right|$

The array above follows a pattern where for all $k,n$, all numbers between $k4^n$ and $(k+1)4^n-1$ form a perfect square.

Can the code above be sped up without generating a ginormous list and storing all the values? Or is there a completely different, faster method?

$\endgroup$
1
$\begingroup$

I think that the fastest approach with modern CPUs is

i = num & 255
j = num >> 8
*x = x1[i] + x2[j]
*y = y1[i] + y2[j]

That is 4 arithmetic ops plus 4 loads

| 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.