Розрахунок кута за допомогою таблиць Брадіса

[radioman]

У темі про розрахунок кута за алгоритмом CORDIC pawa запропонував функцію з обчисленням кута за допомогою таблиць Брадіса. Так як в тесті його алгоритм виявився швидшим, а функція частково вдосконалилася, вирішив відкрити окрему тему.
Первинна функція обраховувала кут у 5 градусів за 13-15 мікросекунд, а 85 за 2-3 мікросекунди (проти "стабільних" 19-21 мікросекунди у CORDIC).

Для розрахунку кута, від 90 віднімається значення, котре "повертає" функція:

Код: Виділити все

intAngle = 90 - atang (lngSX, lngSY);                           // розрахунок кута за таблицею Брадіса

Так як у функції використовується "перебір" значень від меншого до більшого, стає зрозумілим такий діапазон затраченого часу на розрахунок кута. Дещо оптимізувати алгоритм можна умовним "поділом" масиву на дві частини з серединою у 45 градусів.
Для початку задаємо значення початкового індексу "0"

Код: Виділити все

 int intStart = 0;                                             // починаємо з нуля

але одразу перевіряємо, чи розраховане значення тангенсу

Код: Виділити все

x = tmpX / y;                                                 // розрахунок тангенса кута "помноженого" на 1024

не більше, ніж значення у масиві з 45 індексом; якщо так - встановлюємо початкове значення у 45:

Код: Виділити все

if (x > BradisTable[45]) intStart = 45;                       // якщо тангенса кута "помноженого" на 1024 більше значення з індексом 45, починаємо з 45

і продовжуємо розрахунок за алгоритмом, запропонованим pawa.
Можна попробувати "розбити" масив не на дві частини, а більше і порівняти час виконання. На даний час, маємо функцію з максимальним часом виконання 7-8 мікросекунд :

Код: Виділити все

/*   https://radioman.com.ua/viewtopic.php?f=13&t=26   */
const int intBradisTableLength = 90;    // розмір масиву з таблицею Брадіса
/* Масив з таблицею тангенсів Брадіса домножених на 1024 (2 в 10 ступені)для цілочисельних розрахунків */
int BradisTable[intBradisTableLength] =
{
  17, 35, 53, 71, 89, 107, 125, 143, 161, 180, 198, 217, 235, 254, 273,
  293, 312, 332, 352, 372, 392, 413, 434, 455, 477, 498, 521, 543, 567, 590,
  614, 639, 664, 690, 716, 743, 771, 899, 828, 858, 889, 921, 954, 988, 1024,
  1060, 1098, 1137, 1178, 1220, 1265, 1311, 1359, 1409, 1462, 1518, 1577, 1639, 1704, 1774,
  1847, 1926, 2010, 2100, 2196, 2300, 2412, 2534, 2668, 2813, 2974, 3152, 3349, 3571, 3822,
  4107, 4435, 4818, 5268, 5807, 6465, 7286, 8340, 9743, 11704, 14644, 19539, 29291, 58654, 90165
};

/* ... */

/****функція визначення кута за таблицею Брадіса (pawa_mod)****/
int  atang (long x, long y)
{
  if (x < 0) x = -1 * x;                                          // якщо x< 0 інвертуємо знак
  if (y > 0)                                                      // "У" завжди повинен бути позитивним
  {
    long tmpX = x;
    tmpX = tmpX << 10;                                            // множимо "Х" на 1024=2 в 10 ступені (у таблиці домножено) - зсув виконується швидше
    x = tmpX / y;                                                 // розрахунок тангенса кута "помноженого" на 1024
    int intStart = 0;                                             // починаємо з нуля
    if (x > BradisTable[45]) intStart = 45;                       // якщо тангенса кута "помноженого" на 1024 більше значення з індексом 45, починаємо з 45
    for (int i = intStart; i < intBradisTableLength; i++)         // "перебігаємо" по таблиці від меншого кута до більшого
    {
      if (x < (*(BradisTable + i))) return i;                     // якщо тангенс вимірюваного кута менший табличного - рухаємось далі
    }
  }
  return 90;                                                      // якщо "У" від'ємний (помилка аналогової частини) - виводимо 90 (0)градусів
}

[pawa]

Гарно вийшло.
BradisTable[45] можна замінити на (*(BradisTable + 45)) раніше це прискорювало програму, що до вашого компілятора не можу стверджувати.

[radioman]

На продовження теми швидкодії алгоритму.
1. Запропонований pawa код (*(BradisTable + 45)) працює швидше ніж (x > BradisTable[45]), тому провів заміну.
2. В швидкодії варіантів if (x < 0) x = 0 - x; та if (x < 0) x = -1* x; різниці не замітив, так що можна використовувати обидва варіанти.
3. Зміна знаку із відніманням від нуля працює значно швидше ніж перетворення типів unsigned long tmpX = (unsigned) x;.
4. Розділив масив на 3 "підмасиви", що нам ще зменшило максимальний час виконання функції до 5-6 мікросекунд, поділ на 4 не доцільний (?).

В результаті функція отримала такий вигляд:

Код: Виділити все

/*
***функція визначення кута за таблицею Брадіса (pawa_mod)***
      https://radioman.com.ua/viewtopic.php?f=9&t=20
*/
int  atang (long x, long y)
{
  if (x < 0) x = 0 - x;                                           // якщо x< 0 інвертуємо знак
  if (y > 0)                                                      // "У" завжди повинен бути позитивним
  {
    unsigned long tmpX = x;
    tmpX = tmpX << 10;                                            // множимо "Х" на 1024=2 в 10 ступені (у таблиці домножено) - зсув виконується швидше
    x = tmpX / y;                                                 // розрахунок тангенса кута "помноженого" на 1024

    int intStart = 0;                                             // починаємо з нуля
    if (x > (*(BradisTable + 29))) intStart = 30;                 // якщо тангенса кута "помноженого" на 1024 більше значення з індексом 29, починаємо з 30
    if (x > (*(BradisTable + 59))) intStart = 60;                 // якщо тангенса кута "помноженого" на 1024 більше значення з індексом 59, починаємо з 60

    for (int i = intStart; i < intBradisTableLength; i++)         // "перебігаємо" по таблиці від меншого кута до більшого
    {
      if (x < (*(BradisTable + i))) return i;                     // якщо тангенс вимірюваного кута менший табличного - рухаємось далі
    }
  }
  return 90;                                                      // якщо "У" від'ємний (помилка аналогової частини) - виводимо 90 (0)градусів
}

[pawa]

Провели гарну роботу з оптимізацією коду - дуже добре.