Signed Char ATAN2 and ATAN approximations

Question

Basically, I've been trying to make two approximation functions. In both cases I input the "x" and the "y" components (to deal with those nasty n/0 and 0/0 conditions), and need to get a Signed Char output. In ATAN2's case, it should provide a range of +/-PI, and in ATAN's case, the range should be +/- PI/2.

I spent the entire of yesterday trying to wrap my head around it. After playing around in excel to find an overall good algorithm based on the approximation:

    X * (PI/4 + 0.273 * (1 - |X|)) * 128/PI // Scale factor at end to switch to char format

I came up with the following code:

signed char nabsSC(signed char x)
{
    if(x > 0)
        return -x;
    return x;
}

signed char signSC(signed char input, signed char ifZero = 0, signed char scaleFactor = 1)
{
    if(input > 0)
    {return scaleFactor;}

    else if(input < 0)
    {return -scaleFactor;}

    else
    {return ifZero;}
}

signed char divisionSC(signed char numerator, signed char denominator)
{
    if(denominator == 0)                // Error Condition
    {return 0;}
    else
    {return numerator/denominator;}
}

//#######################################################################################

signed char atan2SC(signed char y, signed char x)
{
    // @todo make clearer : the code was deduced through trial and error in excel with brute force... not the best reasoning in the world but hey ho
    if((x == y) && (x == 0))                            // Error Condition
    {return 0;}

                                    // Prepare for algorithm Choice
    const signed char X = abs(x);
    signed char Y = abs(y);
    if(Y > 2)
    {Y = (Y << 1) + 4;}

    const signed char alpha1 = 43;
    const signed char alpha2 = 11;
                                    // Make Choice
    if(X <= Y)                          // x/y Path
    {
        const signed char beta = 64;
        const signed char a = divisionSC(x,y);          // x/y
        const signed char A = nabsSC(a);                // -|x/y|

        const signed char temp = a * (alpha1 + alpha2 * A);     // (x/y) * (32 + ((0.273 * 128) / PI) * (1 - |x/y|)))
                                                        // Small angle approximation of ARCTAN(X)
        if(y < 0)                   // Determine Quadrant
        {return -(temp + beta);}
        else
        {return -(temp - beta);}
    }
    else                                // y/x Path
    {
        const signed char a = divisionSC(y,x);          // y/x
        const signed char A = nabsSC(a);                // -|y/x|

        const signed char temp = a * (alpha1 + alpha2 * A);     // (y/x) * (32 + ((0.273 * 128) / PI) * (1 - |y/x|)))
                                                        // Small angle approximation of ARCTAN(X)

        if(x < 0)                   // Determine Quadrant
        {
            Y = signSC(y, -127, 127);                       // Sign(y)*127, if undefined: use -127
            return temp + Y;
        }
        else
        {return temp;}
    }
}

Much to my despair, the implementation has errors as large as 180 degrees, and pretty much everywhere in between as well. (I compared it to the ATAN2F from the library after converting to signed char format.)

I got the general gist from this website: http://geekshavefeelings.com/posts/fixed-point-atan2

Can anybody tell me where I'm going wrong? And how I should approach the ATAN variant (which should be more precise as it's looking over half the range) without all this craziness.

I'm currently using QT creator 4.8.1 on windows. The end platform for this specific bit of code will eventually be a micro-controller without an FPU, and the ATAN functions will be one of the primary functions used. As such, efficiency with reasonable error (+/-2 degrees for ATAN2 and +/-1 degree for ATAN. These are guesstimates for now, so I might increase the range, however, 90 degrees is definitely not acceptable!) is the aim of the game.

Thanks in advance for any and all help!

EDIT: Just to clarify, the outputs of ATAN2 and ATAN output to a signed char value, but the ranges of the two types are different ranges.

ATAN2 shall have a range from -128 (-PI) to 127 (+PI - PI/128).

ATAN will have a range from -128 (-PI/2) to 127 (+PI/2 - PI/256).

As such the output values from the two can be considered to be two different data types.

Sorry for any confusion.

EDIT2: Converted implicit int numbers explicitly into signed char constants.

Answer 1

An outline follows. Below is additional information.

1. The result angle (a Binary Angle Measure) exactly mathematically divides the unit circle into 8 wedges. Assuming -128 to 127 char, for atan2SC() the result of each octant is 33 integers: 0 to 32 + an offset. (0 to 32, rather than 0 to 31 due to rounding.) For atan2SC(), the result is 0 to 64. So just focus on calculating the result of 1 primary octant with x,y inputs and 0 to 64 result. atan2SC() and atan2SC() can both use this helper function at2(). For atan2SC(), to find the intermediate angle a, use a = at2(x,y)/2. For atanSC(), use a = at2(-128, y).

2. Finding the integer quotient with a = divisionSC(x,y) and then a * (43 + 11 * A) loses too much information in the division. Need to find the atan2 approximation with an equation that uses x,y maybe in the form at2 = (a*y*y + b*y)/(c*x*x + d*x).

3. Good to use negative absolute value as with nabsSC(). The negative range of integers meets or exceed the positive range. e.g. -128 to -1 vs 1 to 127. Use negative numbers and 0, when calling the at2().

---

[Edit]

4. Below is code with a simplified octant selection algorithm. It is carefully constructed to insure any negation of x,y will result in the SCHAR_MIN,SCHAR_MAX range - assuming 2's complelment. All octants call the iat2() and here is where improvements can be made to improve precision. Note: iat2() division by x==0 is prevented as x is not 0 at this point. Depending on rounding mode and if this helper function is shared with atanSC() will dictate its details. Suggest a 2 piece wise linear table is wide integer math is not available, else a a linear (ay+b)/(cx+d). I may play with this more.

5. The weight of precision vs. performance is a crucial one for OP's code, but not pass along well enough for me to derive an optimal answer. So I've posted a test driver below that assesses the precision of what ever detail of iat2() OP comes up with.

6. 3 pitfalls exist. 1) When answer is to be +180 degree, OP appears to want -128 BAM. But atan2(-1, 0.0) comes up with +pi. This sign reversal may be an issue. Note: atan2(-1, -0.0) --> -pi. Ref. 2) When an answer is just slightly less than +180 degrees, depending on iat2() details, the integer BAM result is +128, which tends to wrap to -128. The atan2() result is just less than +pi or +128 BAM. This edge condition needs review inOP's final code. 3) The (x=0,y=0) case needs special handling. The octant selection code finds it.

7. Code for a signed char atanSC(signed char x), if it needs to be fast, could use a few if()s and a 64 byte look-up table. (Assuming a 8 bit signed char). This same table could be used in iat2().

.

#include <stdio.h>
#include <stdlib.h>

// -x > -y >= 0, so divide by 0 not possible
static signed char iat2(signed char y, signed char x) {
  // printf("x=%4d y=%4d\n", x, y); fflush(stdout);
  return ((y*32+(x/2))/x)*2;  // 3.39 mxdiff
  // return ((y*64+(x/2))/x);    // 3.65 mxdiff
  // return (y*64)/x;            // 3.88 mxdiff
}

signed char iatan2sc(signed char y, signed char x) {
  // determine octant
  if (y >= 0) { // oct 0,1,2,3
    if (x >= 0) { // oct 0,1
      if (x > y) {
        return iat2(-y, -x)/2 + 0*32;
      } else {
        if (y == 0) return 0; // (x=0,y=0)
        return -iat2(-x, -y)/2 + 2*32;
      }
    } else { // oct 2,3
      // if (-x <= y) {
      if (x >= -y) {
        return iat2(x, -y)/2 + 2*32;
      } else {
        return -iat2(-y, x)/2 + 4*32;
      }
    }
  } else { // oct 4,5,6,7
    if (x < 0) { // oct 4,5
      // if (-x > -y) {
      if (x < y) {
        return iat2(y, x)/2 + -4*32;
      } else {
        return -iat2(x, y)/2 + -2*32;
      }
    } else { // oct 6,7
      // if (x <= -y) {
      if (-x >= y) {
        return iat2(-x, y)/2 + -2*32;
      } else {
        return -iat2(y, -x)/2 + -0*32;
      }
    }
  }
}

#include <math.h>

static void test_iatan2sc(signed char y, signed char x) {
  static int mn=INT_MAX;
  static int mx=INT_MIN;
  static double mxdiff = 0;

  signed char i = iatan2sc(y,x);
  static const double Pi = 3.1415926535897932384626433832795;
  double a = atan2(y ? y : -0.0, x) * 256/(2*Pi);

  if (i < mn) {
    mn = i;
    printf ("x=%4d,y=%4d  --> %4d   %f, mn %d mx %d mxdiff %f\n", 
        x,y,i,a,mn,mx,mxdiff);
  }
  if (i > mx) {
    mx = i;
    printf ("x=%4d,y=%4d  --> %4d   %f, mn %d mx %d mxdiff %f\n", 
        x,y,i,a,mn,mx,mxdiff);
  }

  double diff = fabs(i - a);
  if (diff > 128) diff = fabs(diff - 256);

  if (diff > mxdiff) {
    mxdiff = diff;
    printf ("x=%4d,y=%4d  --> %4d   %f, mn %d mx %d mxdiff %f\n", 
        x,y,i,a,mn,mx,mxdiff);
  }
}


int main(void) {
  int x,y;
  int n = 127;
  for (y = -n-1; y <= n; y++) {
    for (x = -n-1; x <= n; x++) {
      test_iatan2sc(y,x);
    }
  }
  puts("Done");
  return 0;
}

BTW: a fun problem.