EEVblog Electronics Community Forum
Products => Computers => Programming => Topic started by: Infraviolet on April 27, 2024, 09:14:35 pm
-
Is this always guaranteed to work for integers:
int16_t Clamp360(int16_t value){
value= value % 360;
if(value >= 0){
return value;
}else{
return 360 - (0 - value);
}
}
By extension is this:
int16_t Clamp180(int16_t value){
value= (value+180) % 360;
if(value >= 0){
return value -180;
}else{
return 180 - (0 - value);
}
}
In languages like C and C++ where % is modulo, not truly a remainder and therefore returns negative results when negativeNum % positiveNum is done.
I'd rather avoid resorting to sin, cos and atan2 because this needs to run fast on a microcontroller in the end, so I'm trying to avoid trig functions or proper dot and cross products. And I'd also like not to have a while loop which may go on for a very long time if it subtracts 360 each time.
I've tested for all integers -1080 to +1080 and it plots out the right graphs for input vs output, but I've had nasty experiences with angle wrapping code before. I want to make sure this is right before I continue with any further code built around it.
Is this a guaranteed solution for signed integer variables? Will it also be one if floating point variables are used instead?
Thanks
P.S. any tips on angle-wrap-respecting code to determine if a supplied angle is inbetween (on the short side) another two supplied angles? Imagine "spinning a bottle" and then checking if the resulting angle is within a certain sector, the sectors not all being equally sized or spaced, so it needs to be a genuine check of "is it between these sector limit angles". It becomes fairly simple with trig or dot/cross products, but I need to avoid those for speed/memory/code space reasons. Thanks
-
In languages like C and C++ where % is modulo, not truly a remainder and therefore returns negative results when negativeNum % positiveNum is done.
The C C++ way is generally called remainder, the sensible way is called modulo.
Your code looks right, although (360 - (0 -x)) can just be "x + 360" and it will do the same thing.
-
For floating point the % operator isn't defined and you need to use fmodf and friends. They broadly work the same way. One trap is that negative zero is an allowed result which may need to be special cased if you want to ensure that the result is always non negative and strictly less than 360.
-
To avoid branching with 16-bit integer inputs, you may shift the input so the lowest input value congruent to 0 is actually 0, and % that:
int16_t truncate360(int_fast32_t value) {
constexpr int_fast32_t lowestZero = INT32_C(360) * 91;
return (value + lowestZero) % 360;
}If you want to cover the very end at the bottom (below 32760), just shift it by another 360 (that is: 92 steps, not 91).
The above isn’t going to work nicely with arbitrary floats, because it relies on calculations being done in a type with a range at least twice the input. And even if the value fits, it may lose a bit of precision.
As for the “true” value: in both C or C++ word “modulo” is never used in reference to the % operator. The behavior of / and % is defined by this single identity: (a/b)*b + a%b == a. So the language isn’t even making a claim of supporting such operation. But, if it did, “mathematical” modular arithmetic is not inherently positive either. Some languages simply choose to use positive remainders, but it’s an arbitrary choice, not truth. It may be useful to limit operations to integers ring modulo N, but it’s not truth.
-
mathematical” modular arithmetic is not inherently positive either
Obviously it's a matter of terminology and the only 100% unambiguous thing is to do is show the formula, but most sources use the word "remainder" to mean the thing that C and C++ does (share the sign of the dividend) and "modulo" mean the version where the result takes the sign of the divisor. This includes the C standard which does call the result of the % operator the "remainder." If you do "integer arithmetic modulo N" there are only N distinct values. in C and C++, x % N can take on 2*N-1 possible values, which means that most of the distinct values have two possible representations. Yes, it's a choice, but pretty inconvenient if you are doing anything you call modular arithmetic.
The behavior of / and % is defined by this single identity: (a/b)*b + a%b == a
That is rather missing the point. Everyone agrees that that the above formula has to be true for any sensible definition of %, and was required even in C89. What C since C99 specify is that integer division truncates to zero rather than floor towards -infinity. Once you specify division that way, in order to satisfy this formula you need to have negative numbers produce a negative remainder. The other possible convention (and the one I would argue is far more commonly what you want) is where integer division is floor division, and the % operator acts like modulo.
-
For angles that need to wrap, I'd suggest, instead of degrees, use 65536/360 deg (~ 0.005deg) as your base unit. (Or 2^32/360 if you need more resolution, or 256/360 if that suffices!). This way, wrap around always Just Works implicitly - and efficiently, in CPU registers directly (either with zero cost, or in worst case, requiring a single instruction to mask out bits):
uint16_t angle = ...;
uint16_t angle_plus_90deg = angle + 16384; // implicit correct wrapping guaranteed by C standard
...
You can further just choose to cast into signed type (int16_t) to interpret the angle between -180 .. +180 deg.
Only convert to degrees when interfacing with human, in UI.
In C, this is all standard; unsigned arithmetics are guaranteed to provide modulus operation when the result overflows, so if you ever came across with an oddball CPU architecture which does not do this on machine level, then the C compiler for that machine would still emit the correct instructions, and as such, the solution is portable.
-
Don't have much to add, but +1 to using the implicit modularity of fixed-size (and known size; use inttypes!) unsigneds.
Put another way, it's fixed point 0.16 (or whatever), fractional cycles.
Most anything you would do with degrees, can be done in any other unit. sin/cos implementations can be adjusted, it's just a matter of changing coefficients and bit shifts, etc.
There's also a... maybe more esoteric route? Which, I've thought about here and there, but which probably isn't worthwhile for most applications. In any case, consider the argument of a complex number, which we store as a tuple z = [a, b], which might be char, int, whatever. If |z| is normalized, we can simply multiply it by any other (complex) number to change the angle -- the basis of the CORDIC algorithm for example. We trivially extend it into a direction vector, if we're doing something spacial or geometrical -- this can be useful in video games, and I used such a scheme for a raycaster (WOLF3D style) engine way back when* -- but the fact that you're handling ~double the information, that normalization is awkward, etc., means it probably isn't going to be your first pick when you just need an angle.
*The maybe most interesting part here is, the screen vector is automatically scaled for perspective correction -- that is, the vectors cast from camera origin to view plane (well, line), automatically scale the rays cast to walls, giving perspective-correct lengths returned from the "cast" function. I've seen tons of trig corrections (both preparing the vectors, and correcting the ray lengths), and hackery around singularities (axis aligned vectors), in others' implementations of raycasters, so I felt pretty proud of the general, direction-invariant solution I came up with. :P
Tim
-
P.S. any tips on angle-wrap-respecting code to determine if a supplied angle is inbetween (on the short side) another two supplied angles? Imagine "spinning a bottle" and then checking if the resulting angle is within a certain sector, the sectors not all being equally sized or spaced, so it needs to be a genuine check of "is it between these sector limit angles".
This problem is trickier than simple comparison due to wrapping issue, but still easily solvable by splitting circle in two regions.
Lets say full circle has possible angles from \$0..360\$ (360 being same as 0).
Input is angle \$X\$ and sector from angle \$A\$ to angle \$B\$ (\$A>B\$ or \$A<B\$, i.e. \$10..350\$ (340 degree sector) is different from \$350..10\$ (20 degree sector))
Split circle in to two regions - \$0..180\$ and \$180..360\$. Based on \$X\$, select \$0..180\$ or \$180..360\$ region. Recalculate \$A..B\$ sector coverage in this region, to get \$A'..B'\$ sector with condition \$A'<B'\$. Then comparison \$A'<X<B'\$ gives the answer.
-
. any tips on angle-wrap-respecting code to determine if a supplied angle is inbetween (on the short side) another two supplied angles
If possible I would avoid this. Specifically the "on the short side." Instead, define this in terms of " counterclockwise from the first angle, before reaching the second." This gives a unique representation, allows you to define an arbitrary interval rather than restricting to things less than 180 degrees. Then "x is within the interval [a, b)" becomes:
(x - a) mod 360 < (x - b) mod 360.
If you still need the behavior you asked for then handle that as an input transformation: if (( b - a) mod 360) > 180) then swap(a, b)
As usual, watch out for the edge cases, I have chosen a convention that includes the first point but not the second. You might choose differently.
-
For angles that need to wrap, I'd suggest, instead of degrees, use 65536/360 deg (~ 0.005deg) as your base unit. (Or 2^32/360 if you need more resolution, or 256/360 if that suffices!). This way, wrap around always Just Works implicitly - and efficiently, in CPU registers directly (either with zero cost, or in worst case, requiring a single instruction to mask out bits):
uint16_t angle = ...;
uint16_t angle_plus_90deg = angle + 16384; // implicit correct wrapping guaranteed by C standard
...
You can further just choose to cast into signed type (int16_t) to interpret the angle between -180 .. +180 deg.
it even has a name, https://en.wikipedia.org/wiki/Binary_angular_measurement
-
There are additional benefits of using uintN_t type and value 2B for a full circle, B <= N:
- Cosine(x) = Sine(x + 2B-2)
- Normalizing x to positive range:
(uintN_t)x & ((1 << B) - 1)
(which should optimize to a no-op if B == N)
- Normalizing x to intN_t:
(intN_t)((uintN_t)x << (N - B)) / (1 << (N - B))
(which should optimize to a binary left shift followed by an arithmetic right shift, or to copying the most significant bit (sign bit) to N-B most significant bit positions)
- Quadrant of angle x:
((x >> (B-2)) & 3)
- Octant for angle x:
((x >> (B-3)) & 7)
which also tells the major semiaxis:
0:+x, 1:+y, 2:+y, 3:-x, 4:-x, 5:-y, 6:-y, 7:+x
or equivalently, the major axis is
if ((x + (1<<(B-3))) & (1 << (B-2))) "y" else "x";
and the direction is
if ((x + (1<<(B-3))) & (1 << (B-1))) "-" else "+";
This means that your sine/cosine functions only need to handle the first sine quadrant, values from 0 to 1, for which there are many different ways from approximations to look-up tables.
One approach I really like is to approximate function \$y(x) = \sin(\pi x/2)\$, such that \$y(0) = 0\$, \$y(1) = 1\$, \$y(-1) = -1\$, \$y(1/2) = \sqrt{1/2}\$, \$y(-1/2) = -\sqrt{1/2}\$, \$y(1/3) = 1/2\$, and \$y(-1/3) = -1/2\$. The series definition involves only odd powers of \$x\$, $$y(x) = \sum_{i=0}^{\infty} \frac{(-1)^i \pi^{2 i + 1}}{2^{2 i + 1} (2 i + 1)!} x^{2 i + 1} \approx 1.5707964 x - 0.6459641 x^3 + 0.079692625 x^5 - 0.004681754 x^7 + \dots$$ which converges slowly like \$\sin\$ does, so one would need many terms. With floating-point numbers, you can get a better result if you do the sum from right to left, i.e. in increasing order of magnitude. However, piecewise cubic interpolation works better; and you can use importance sampling and a binary search to find the correct piece in \$N\$ iterations, when there are less than \$2^N\$ pieces (entries in the lookup table).
-
+1 for using 2^n = 360 degrees. Also if you need a sine, this is trivially easy to do with a lookup table + linear interpolation - just use some bits for the table lookup and the rest as the interpolation fraction - just 1 integer multiply and a couple of add/subs
-
+1 for using 2^n = 360 degrees. Also if you need a sine, this is trivially easy to do with a lookup table + linear interpolation - just use some bits for the table lookup and the rest as the interpolation fraction - just 1 integer multiply and a couple of add/subs
yep, in twos-complements it makes lots of thing easy:
MSB set means 3. or 4. qudrant so output is the same as 1./2. quadrant but negated
MSB-1 set means 2. or 4. quadrant so output is the same as 1. quadrant but in "reverse", which is easily done by negating the angle and masking
so the lookup table / approximation only needs one quadrant