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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
0

Your Answer

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

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