This is a question that came up in the context of sorting points with integer coordinates into clockwise order, but this question is not about how to do that sorting.

This question is about the observation that 2-d vectors have a natural cyclic ordering. Unsigned integers with usual overflow behavior (or signed integers using twos-complement) also have a natural cyclic ordering. Can you easily map from the first ordering to the second?

So, the exact question is whether there is a map from pairs of twos-complement signed 32-bit integers to unsigned (or twos-complement signed) 64-bit integers such that any list of vectors that is in clockwise order maps to integers that are in decreasing (modulo overflow) order?

Some technical cases that people will likely ask about:

- Yes, vectors that are multiples of each other should map to the same thing
- No, I don't care which vector (if any) maps to 0
- No, the images of antipodal vectors don't have to differ by 2^63 (although that
*is*a nice-to-have)

The obvious answer is that since there are only around 0.6*2^64 distinct slopes, the answer is yes, such a map exists, but I'm looking for one that is easily computable. I understand that "easily" is subjective, but I'm really looking for something reasonably efficient and not terrible to implement. So, in particular, no counting every lattice point between the ray and the positive x-axis (unless you know a clever way to do that without enumerating them all).

An important thing to note is that it can be done by mapping to 6*5*-bit integers. Simply project the vector out to where it hits the box bounded by x,y=+/-2^62 and round toward negative infinity. You need 63 bits to represent that integer and two more to encode which side of the box you hit. The implementation needs a little care to make sure you don't overflow, but only has one branch and two divides and is otherwise quite cheap. It doesn't work if you project out to 2^61 because you don't get enough resolution to separate some slopes.

Also, before you suggest "just use atan2", compute `atan2(1073741821,2147483643)`

and `atan2(1073741820,2147483641)`

EDIT: Expansion on the "atan2" comment:

Given two values x_1 and x_2 that are coprime and just less than 2^31 (I used 2^31-5 and 2^31-7 in my example), we can use the extended Euclidean algorithm to find y_1 and y_2 such that y_1/x_1-y_2/x_2 = 1/(x_1*x_2) ~= 2^-62. Since the derivative of arctan is bounded by 1, the difference of the outputs of atan2 on these values is not going to be bigger than that. So, there are *lots* of pairs of vectors that won't be distinguishable by atan2 as vanilla IEEE 754 doubles.

*If* you have 80-bit extended registers *and* you are sure you can retain residency in those registers throughout the computation (and don't get kicked out by a context switch or just plain running out of extended registers), then you're fine. But, I really don't like the correctness of my code relying on staying resident in extended registers.

`pdep (x, 0x5555555555555555) | pdep (y, 0xaaaaaaaaaaaaaaaa)`

?`atan2()`

? Using 64-bit IEEE-754 double precision, I get`atan2 (1073741821,2147483643)`

=`0x1.dac67052e881cp-2`

and`atan2 (1073741820,2147483642)`

=`0x1.dac6704fb54e9p-2`

. These two values are easily distinguished even assuming an error of a couple of ulps. There are probably vectors whose respective`atan2`

is much closer than this, but I assume the examples were picked for a reason.easily computable".`atan2`

is that you don't really gain anything compared to just using the slope directly - in fact, you lose some precision for angles closer to odd multiples of 45 degrees, because there are more distinct angles in that part of the range due to the domain being a square rather than a disc.7more comments