Различные способы (и самые быстрые) для вычисления синусов (и косинусов) в Arduino

Я использую плату Arduino Uno для вычисления углов моей системы (роботизированная рука). Углы на самом деле являются 10-битными значениями (от 0 до 1023) от АЦП, используя полный диапазон АЦП. Я буду работать только в первом квадранте (от 0 до 90 градусов), где оба синуса и косинуса положительны, поэтому проблем с отрицательными номерами нет. Мои сомнения могут быть выражены в 3-х вопросах:

  1. Каковы различные способы вычисления этих тригонометрических функций на Arduino?

  2. Каков самый быстрый способ сделать то же самое?

  3. В Arduino IDE есть функции sin () и cos (), но как Arduino действительно их вычисляет (как в них используются справочные таблицы, или приближения и т. д.)? Они кажутся очевидным решением, но я хотел бы узнать их фактическую реализацию, прежде чем я их попробую.

PS: Я открыт как для стандартного кодирования на Arduino IDE, так и для сборки, а также для любых других опций, не упомянутых. Также у меня нет проблем с ошибками и приближениями, которые неизбежны для цифровой системы; однако, если возможно, было бы неплохо упомянуть о степени возможных ошибок

8 голосов | спросил Transistor Overlord 29 PMpSat, 29 Apr 2017 12:09:35 +030009Saturday 2017, 12:09:35

8 ответов


8

Двумя основными методами являются математический расчет (с полиномами) и таблицы поиска.

В математической библиотеке Arduino (libm, часть avr-libc) используется первая. Он оптимизирован для AVR тем, что он написан на 100% языке ассемблера, и поэтому почти невозможно следить за тем, что он делает (также есть нулевые комментарии). Будьте уверены, хотя это будет самый оптимизированный мозг реализации с чистым поплавком, намного превосходящий наш, может возникнуть.

Однако существует ключ float . Все, что связано с Arduino с использованием плавающей запятой, будет иметь тяжелый вес по сравнению с чистым целым числом, и поскольку вы запрашиваете целые числа от 0 до 90 градусов, простая таблица поиска является самым простым и эффективным методом.

Таблица из 91 значений даст вам все от 0 до 90 включительно. Однако, если вы сделаете таблицу значений с плавающей запятой между 0.0 и 1.0, вы по-прежнему будете иметь неэффективность работы с поплавками (предоставляемый не так неэффективно, как вычисление sin с поплавками), поэтому сохранение значения фиксированной точки вместо этого было бы гораздо более эффективным.

Это может быть так же просто, как хранить значение, умноженное на 1000, поэтому между 0 и 1000 вместо 0.0 и 1.0 (например, sin (30) будет храниться как 500 вместо 0,5). Более эффективным было бы сохранение значений как, например, значения Q16, где каждое значение (бит) представляет 1 /65536th из 1.0. Эти значения Q16 (и связанные с ними Q15, Q1.15 и т. Д.) Более эффективны для работы, поскольку у вас есть полномочия двух, с которыми компьютеры любят работать, а не с полномочиями, из которых они ненавидят работу.

Не забывайте также, что функция sin() ожидает радианы, поэтому сначала вам нужно преобразовать ваши значения в градусы по шкале с плавающей запятой, используя sin() еще более неэффективен по сравнению с таблицей поиска, которая может работать непосредственно с целым числом градусов.

Возможно сочетание двух сценариев. Линейная интерполяция позволит вам получить приближение угла с плавающей точкой между двумя целыми числами. Это так же просто, как определить, насколько далеко между двумя точками в таблице поиска вы создаете средневзвешенное значение, основанное на этом расстоянии двух значений. Например, если вы находитесь на 23,6 градуса, вы берете (sintable[23] * (1-0.6)) + (sintable[24] * 0.6). В основном ваша синусоидальная волна становится серией дискретных точек, соединенных прямыми линиями. Вы торгуете точностью для скорости.

ответил Majenko 29 PMpSat, 29 Apr 2017 14:34:03 +030034Saturday 2017, 14:34:03
5

Здесь есть несколько хороших ответов, но я хотел добавить метод, который еще не упоминался, который очень хорошо подходит для вычисления тригонометрических функций на встроенных системах, и это метод CORDIC Wiki Entry Here Он может вычислять триггерные функции, используя только сдвиги и добавления и небольшую таблицу поиска.

Вот грубый пример в C. На самом деле он реализует функцию atan2 () библиотеки C, используя CORDIC (т. е. находит угол, заданный двумя ортогональными компонентами). Он использует с плавающей запятой, но может быть адаптирован для использования с фиксированными функциями, точечная арифметика.

/*
 * Simple example of using the CORDIC algorithm.
 */

#include <stdio.h>
#include <math.h>

#define CORDIC_TABLE_SIZE  16

double cordic_table[CORDIC_TABLE_SIZE];

void init_table(void);
double angle(double I, double Q);

/*
 * Given a sine and cosine component of an
 * angle, compute the angle using the CORIDC
 * algoritm.
 */
double angle(double I, double Q)
{
    int L;
    double K = 1;
    double angle_acc = 0;
    double tmp_I;

    if (I < 0) {
        /* rotate by an initial +/- 90 degrees */
        tmp_I = I;
        if (Q > 0.0) {
            I = Q;           /* subtract 90 degrees */
            Q = -tmp_I;
            angle_acc = -90;
        } else {
            I = -Q;          /* add 90 degrees */
            Q = tmp_I;
            angle_acc = 90;
        }
    } else {
        angle_acc = 0;
    }

    /* rotate using "1 + jK" factors */
    for (L = 0, K = 1; L <= CORDIC_TABLE_SIZE; L++) {
        tmp_I = I;
        if (Q >= 0.0) {
            /* angle is positive: do negative roation */
            I += Q * K;
            Q -= tmp_I * K;
            angle_acc -= cordic_table[L];
        } else {
            /* angle is negative: do positive rotation */
            I -= Q * K;
            Q += tmp_I * K;
            angle_acc += cordic_table[L];
        }
        K /= 2.0;
    }
    return -angle_acc;
}

void init_table(void)
{
    int i;
    double K = 1;

    for (i = 0; i < CORDIC_TABLE_SIZE; i++) {
        cordic_table[i] = 180 * atan(K) / M_PI;
        K /= 2.0;
    }
}
int main(int argc, char **argv)
{
    double I, Q, A, Ar, R, Ac;

    init_table();

    printf("# Angle,    CORDIC Angle,  Error\n");
    for (A = 0; A < 90.0; A += 0.5) {

        Ar = A * M_PI / 180; /* convert to radians for C's sin & cos fn's */

        R = 5;  // Arbitrary radius

        I = R * cos(Ar);
        Q = R * sin(Ar);

        Ac = angle(I, Q);
        printf("%9f, %9f,   %12.4e\n", A, Ac, Ac-A);
    }
    return 0;
}

Но сначала попробуйте собственные триггеры Arduino - они могут быть достаточно быстрыми.

ответил Halzephron 29 PMpSat, 29 Apr 2017 21:07:15 +030007Saturday 2017, 21:07:15
5

Я немного играл с вычислениями синусов и косинусов на Ардуино с использованием полиномиальных приближений с фиксированной точкой. Вот мои измерения среднего времени выполнения и ошибки наихудшего случая, сравниваются со стандартным cos() и sin() от avr-libc:

function    max error   cycles   time
-----------------------------------------
cos_fix()   9.53e-5     108.25    6.77 µs
sin_fix()   9.53e-5     110.25    6.89 µs
cos()       2.98e-8     1720.8   107.5 µs
sin()       2.98e-8     1725.1   107.8 µs

Он основан на полиноме 6-й степени, рассчитанном только 4a умножений. Само собой размножение выполняется в когда я обнаружил, что gcc реализовал их неэффективно. Углы выражаются как uint16_t в единицах 1/65536 оборота, который делает арифметику углов естественным образом по модулю одного оборота.

Если вы считаете, что это может удовлетворить ваш счет, вот код: Fixed-point тригонометрия . Извините, я до сих пор не перевел эту страницу, что на французском, но вы могут понимать уравнения и код (имена переменных, комментарии ...) находится на английском языке.


Изменить . Поскольку сервер, похоже, исчез, вот некоторая информация о найденные нами приближения.

Я хотел написать углы в бинарной фиксированной точке, в единицах квадрантов (или, что то же самое, по очереди). И я также хотел использовать четное полином, поскольку они более эффективны для вычисления, чем произвольные многочлены. Другими словами, мне нужен многочлен P () такой, что

cos (Ï € /2 x) â P (x 2 ) для x â [0,1]

Я также потребовал, чтобы аппроксимация была точной на обоих концах интервал, чтобы обеспечить, что cos (0) Â = Â 1 и cos (Ï € /2) Â = Â 0. Эти ограничения привели к виду

P (u) = (1 â 'u) (1 + uQ (u))

, где Q () - произвольный многочлен.

Затем я искал наилучшее решение в зависимости от степени Q () и нашел это:

        Q(u)             │ degree of P(x²) │ max error
─────────────────────────┼─────────────────┼──────────
          0              │         2       │  5.60e-2
       −0.224            │         4       │  9.20e-4
−0.2335216 + 0.0190963 u │         6       │  9.20e-6

Выбор среди решений выше - это компромисс скорости /точности. третье решение дает больше точности, чем достижимо с 16-битами, и это тот, который я выбрал для 16-битной реализации.

ответил Edgar Bonet 29 PMpSat, 29 Apr 2017 22:21:00 +030021Saturday 2017, 22:21:00
2

Вы можете создать пару функций, которые используют линейную аппроксимацию для определения sin () и cos () определенного угла.

Я думаю что-то вроде этого:  линейное приближение
Для каждого я разбил графическое представление sin () и cos () на 3 раздела и выполнил линейную аппроксимацию этого раздела.

Ваша функция в идеале должна сначала проверить, что диапазон ангела находится между 0 и 90.
Затем он будет использовать оператор ifelse, чтобы определить, что из трех разделов он принадлежит, а затем выполняет соответствующий линейный расчет (т.е. output = mX + c)

ответил sa_leinad 29 PMpSat, 29 Apr 2017 14:44:59 +030044Saturday 2017, 14:44:59
2

Я искал других людей, которые аппроксимировали cos () и sin (), и я наткнулся на этот ответ:

ответ dtb на «Fast Sin /Cos с использованием предварительно вычисленного массива переводов»

В основном он вычислил, что функция math.sin () из математической библиотеки была быстрее, чем использование таблицы значений значений. Но из того, что я могу сказать, это было рассчитано на ПК.

Arduino содержит математическую библиотеку , которая может вычислять sin () и cos ( ).

ответил sa_leinad 29 PMpSat, 29 Apr 2017 14:49:45 +030049Saturday 2017, 14:49:45
2

Таблица поиска будет самым быстрым способом поиска синусов. И если вам удобнее вычислять номера с фиксированной точкой (целые числа, двоичная точка которых находится где-то иначе, чем справа от бит-0), ваши дальнейшие вычисления с синусами будут намного быстрее. Эта таблица может быть таблицей слов, возможно, во Flash для экономии места в оперативной памяти. Обратите внимание, что в вашей математике вам может понадобиться использовать длинные промежуточные результаты.

ответил JRobert 29 PMpSat, 29 Apr 2017 15:25:21 +030025Saturday 2017, 15:25:21
1

обычно, таблица поиска> аппроксимация -> расчет. ram> вспышка. целое> неподвижная точка> плавающая точка. предварительное прокаливание> расчет в реальном времени. зеркальное отображение (синус-косинус или косинус на синус) по сравнению с фактическим вычислением /поиском ....

у каждого есть свои плюсы и минусы.

вы можете сделать всевозможные комбинации, чтобы увидеть, что лучше всего подходит для вашего приложения.

edit: Я быстро проверил. используя 8-битный целочисленный вывод, вычисление 1024 значений sin с помощью справочной таблицы занимает 0,6 мс и 133 мс с помощью флоутеров или 200 раз медленнее.

ответил dannyf 29 PMpSat, 29 Apr 2017 14:34:02 +030034Saturday 2017, 14:34:02
1

У меня был подобный вопрос для OP. Я хотел сделать таблицу LUT, чтобы вычислить первый квадрант функции синуса как неподписанные 16-битные целые числа, начиная с 0x8000 до 0xffff. И я закончил писать это для удовольствия и прибыли. Примечание. Это будет работать более эффективно, если я использую операторы if. Также он не очень точен, но будет достаточно точным для синусоидальной волны в звуковом синтезаторе

void sin_lut_ctor(){

//Make a Look Up Table for 511 terms of the sine function.
//Plugin in some polynomials to do some magic
//and you get an aproximation for sines up to π/2.
//

//All sines yonder π/2 can be derived with math

const uint16_t uLut_d = 0x0200; //maximum LUT depth for π/2 terms. 
uint16_t uLut_0[uLut_d];        //The LUT itself.
//Put the 2 above before your void setup() as global variables.
//This coefficients will only work for uLut_d = 511.

uint16_t arna_poly_0 = 0x000a; // 11
uint16_t arna_poly_1 = 0x0001; // 1
uint16_t arna_poly_2 = 0x0007; // 7
uint16_t arna_poly_3 = 0x0001; // 1   Precalculated Polynomials
uint16_t arna_poly_4 = 0x0001; // 1   
uint16_t arna_poly_5 = 0x0007; // 7
uint16_t arna_poly_6 = 0x0002; // 2
uint16_t arna_poly_7 = 0x0001; // 1

uint16_t Imm_UI_0 = 0x0001;              //  Itterator
uint16_t Imm_UI_1 = 0x007c;              //  An incrementor that decreases in time

uint16_t Imm_UI_2 = 0x0000;              //  
uint16_t Imm_UI_3 = 0x0000;              //              
uint16_t Imm_UI_4 = 0x0000;              //
uint16_t Imm_UI_5 = 0x0000;              //
uint16_t Imm_UI_6 = 0x0000;              //  Temporary variables
uint16_t Imm_UI_7 = 0x0000;              //
uint16_t Imm_UI_8 = 0x0000;              //
uint16_t Imm_UI_9 = 0x0000;              //
uint16_t Imm_UI_A = 0x0000;
uint16_t Imm_UI_B = 0x0000;

uint16_t Imm_UI_A = uLut_d - 0x0001;     //  510

uLut_0[0x0000] = 0x8000;        //Assume that the middle point is 32768 (0x8000 hex)
while (Imm_UI_0 < Imm_UI_A) //Construct a quarter of the sine table
  {
Imm_UI_2++;                                   //Increase temporary variable by 1

Imm_UI_B = Imm_UI_2 / arna_coeff_0;           //Divide it with the first coefficient (note: integer division)
Imm_UI_3 += Imm_UI_B;                         //Increase the next temporary value if the first one has increased up to the 1st coefficient
Imm_UI_1 -= Imm_UI_B;                         //Decrease the incrementor if this is the case
Imm_UI_2 *= 0x001 - Imm_UI_B;                 //Set the first temporary variable back to 0

Imm_UI_B = Imm_UI_3 / arna_poly_1;           //Do the same thing as before with the next set of temporary variables
Imm_UI_4 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_3 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_4 / arna_poly_2;           //And again... and again... you get the idea.
Imm_UI_5 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_4 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_5 / arna_poly_3;
Imm_UI_6 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_5 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_6 / arna_poly_4;
Imm_UI_7 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_6 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_7 / arna_poly_5;
Imm_UI_8 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_7 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_8 / arna_poly_6;
Imm_UI_9 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_8 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_9 / arna_poly_7          //the last set won't need to increment a next variable so skip the step where you would increase it.
Imm_UI_1 -= Imm_UI_B;
Imm_UI_9 *= 1 - Imm_UI_B;

uLut_0[Imm_UI_0] = (uLut_0[Imm_UI_0 - 0x0001] + Imm_UI_1); //Set the current value as the previous one increased by our incrementor
Imm_UI_0++;              //Increase the itterator
  }   
  uLut_0[Imm_UI_A] = 0xffff; //Lastly, set the last value to 0xffff

  //And there you have it. A sine table with only one if statement (a while loop)
}

Теперь, чтобы вернуть значения, используйте эту функцию. Он принимает значение от 0x0000 до 0x0800 и возвращает соответствующее значение из LUT

uint16_t lu_sin(uint16_t lu_val0)
{
  //Get a value from 0x0000 to 0x0800. Return an appropriate sin(value)
  Imm_UI_0 = lu_val0/0x0200; //determine quadrant
  Imm_UI_1 = lu_val0%0x0200; //Get which value
  if (Imm_UI_0 == 0x0000)
  {
    return uLut_0[Imm_UI_1];
  }
  if (Imm_UI_0 == 0x0001)
  {
    return uLut_0[0x01ff - Imm_UI_1];
  }
  if (Imm_UI_0 == 0x0002)
  {
    return 0xffff - uLut_0[Imm_UI_1];
  }
  if (Imm_UI_0 == 0x0003)
  {
    return 0xffff - uLut_0[0x01ff - Imm_UI_1];
  }
}// I'm using if statements here but similarly to the above code block, 
 //you can do without. just with integer divisions and modulos

Помните, что это не самый эффективный подход к этой задаче, я просто не мог понять, как сделать серии Тейлора для выдачи результатов в соответствующем диапазоне.

ответил Arnadath 30 +03002017-10-30T00:50:49+03:00312017bEurope/MoscowMon, 30 Oct 2017 00:50:49 +0300 2017, 00:50:49

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132