Comments 100
Согласен, формула простая и красивая.
Не сравнивал.
С первого взгляда, подпрограмма на её основе должна работать быстрее.
С другой стороны:
- хотелось получить три точных знака, получаемые простым отбрасыванием лишних разрядов, без округления;
- изложенный метод позволяет получить больше точных знака через отбрасывание лишних разрядов без потери производительности, но с расходом памяти под статические данные;
- вероятная перспектива других тригонометрических функций диктует единообразие применяемого мат. аппарата.
Там ведь деление используется?
Я вижу только деления на константы, что компилятор сведет к умножению.
Мы понимаем, что деление, это самая медленная операция из простых арифметических.
Однако, вопрос в другом.
Гарантированная точность в 3-м и далее знаках после десятичной запятой, получаемая простым отбрасыванием лишних разрядов без лишних затрат на округление.
Может я что-то путаю, но мне всегда казалось что тригонометрические функции - периодические с периодом 2 пи. И считать углы нужно в интервале от 0 до пи/2 ?
Вы абсолютно правы,
если рассматривать тригонометрические функции обособленно и раздельно.
Если рассматривать совместно, включая аппроксимирующую функцию, то общим оказывается только квадрант.
Тогда, значения за диапазоном квадранта вычисляются методами осевой симметрии и сдвигом фаз (смена математического знака, сложение с константой).
Да, существенна-ли разница, как считать, если результат счёта удовлетворительный.
Тут на половине графиков все цифры точно такие-же непонятные.
Синус имеет период 2 пи. Четверть от периода с уникальными значениями пи/2.
Вы тут какую-то свою функцию вычисляете судя по всему.
(скорее всего sin(2x))
На графиках:
- на оси абсцисс отложена уголовая величина, измеренная в градусах угловой дуги;
- на оси ординат показаны время срабатывания функции, измеренное в тактах CPU, или ошибка вычисления, как разница между значением, возвращённым библиотечной функцией sinf, и результатом, возвращённым функцией приближённого вычисления sint.
Поясните почему важно использование постоянно вычисляемых значений для синуса или косинуса. Почему нельзя один раз не спеша вычислить все нужные значения и занести в таблицу. И больше не тратить время на вычисление?
Память. Для микроконтроллеров особенно чувствительно. Для "взрослых" процессоров, к тому же, не имеет смысла и по скорости. А раньше считали, да. Lookup таблицы это техника из тех времён, когда не у всех процессоров был FPU.
Я признаться думал что у современных МК с памятью уже получше дела обстоят. Тогда все понятно.
Таблицы - это техника из тех времен, когда ещё процессоров не было.
Весь вопрос в объёме используемой памяти. Оперативной памяти не так много, а в ПЗУ время доступа большое.
На частототах до 100 МГЦ доступ(чтение) к памяти одинаковый. Это же микроконтроллеры, там вся суть прогу во Флеш залить, иначе смысл программы в ПЗУ.
Практика показывает, что на бюджетных микроконтроллерах частота тактирования достаточно ощутимо влияет на время выполнения программы, измеренное в тактах.
Влияние частоты тактироания на скорость выполнения программ зафиксировано здесь: https://habr.com/ru/post/599727/
на одном изделии делали быструю память пзу на базе озу, которые при старте загружались и в дальнейшем шло обращение к зописанным константам в в "постоянном" озу, где были в том числе табличные значения, которые при необходимости уточнялись
Зачем вы делаете игру на stm32?
Если с аппроксимацией сплайнами (как в статье), то можно получить очень большую точность, на не очень большом количестве точек (тех же 45 — более чем хватит), но это медленно.
А если хочется быстро, просто выбором из памяти без каких-либо вычислений (кроме отбрасывания двоичных разрядов), то для игры 256 на пипопалам хватит за глаза. А для более серьёзных применений — там будут килобайты и, может, даже, мегабайты (для особых «эстетов»)
Зачем вы делаете игру на stm32?
Я делал, как пэт-проект. На основе старого поломанного тетриса.
Для мелких 8-битных контроллеров обычно так и делали. Но у контроллеров на ARM Cortex поход во флэшку уже не всегда бесплатный, зато более прокачанное АЛУ, и вообще 32 бита.
Он не бесплатный с определённой частоты тпм 100 МГЦ, например, думаю в большинстве случаев он бесплатный.
под "не бесплатностью" надо полагать понимается время доступа к flash которые зависит от частоты, напряжения питания ядра. первое что под рукой было (stm32l4):
как видно, уже с частоты 40 МГц в большинстве случаем имеем 2 такта. правда есть ещё кеш и ускоритель для доступа к памяти.
mctMaks, Вы правы.
Изменение тактовой частоты MCU существенно влияет на производительность.
Разброс скорости выполнения (в тактах MCU) даже маленьких участков бинарного кода может достигать 100%.
Такое замедление слабо заметно при измерении производительности во времени, но оно оказывает существенное влияние на энергопотребление, если каждый такт MCU ассоциативно приводить к кванту энергетического потребления.
Другими словами, повышение тактовой часты пропорционально увеличивает энергозатраты на один и тот же вычислительный процесс.
На графике зависимость производительности кода от частоты MCU, полученная экспериментально.
Больше информации здесь: ARM Cortex M* — «сколько вешать в граммах».
Бюджетные микроконтроллеры имеют малый размер оперативной памяти, измеряемый в килобайтах.
Когда "на борту" всего 4096 байт (4KB), расходовать ОЗУ на баласт статических данных - это сомнительный путь, если можно быстро посчитать.
С другой стороны, представьте задачу на неустойчивое равновесие, например, балансирование вертикальным шестом или управление двух колёсным велосипедом и т.п. Слабо представляю, как заранее предусмотреть все нужные для решения подобных задач значения.
Исходный код без интеллектуального балласта третьих лиц;
Я понимаю этот тот самый пресловутый фатальный недостаток? (просто есть на Хабре хорошая статья https://habr.com/ru/post/577256/)
Для чего вам вообще быстрое вычисление синуса? Вы заметили, что невязка у вас смещенная? В реальном мире это практически всегда не есть хорошо.
Статья, действительно, интересная. Прочел её вдумчиво и внимательно дважды. Изучил авторский исходный код. Автору плюс.
Автор статьи, Викор Агарков, предлагает всеобъемлющий подход на замечательной теоретической базе, под вполне демократичной лицензией - ссылаться на автора оригинала, создавая производный продукт. В этом проблемы нет.
Думаю, что его решение оптимально для вычислителей среднего и премиального класса.
Здесь же требовалось получить законченное решение, ориентированное на узко-специализированную область, с технологической сложностью на уровне коде-снипета - самодостаточный модуль. Подключил в проект - заработало. Без ассемблерных вставок, статических массивов и внешних генераторов кода.
Для чего вам вообще быстрое вычисление синуса?
Вы заметили, что невязка у вас смещенная?
Поясните, пожалуйста, вопросы.
Невязка - разница между точной функцией и приближением. Вот, по-моему, она у вас не смещённая.
Чтобы "два раза не вставать" - у вас опечатка в "на соответствие функцие синус" - должно быть "функции". И спасибо за статью.
Про невязку уже сказали, а про смещенность - это то, что ее среднее не ноль. Это плохо, т.к. в ходе вычислений ошибка начинает накапливаться. У полиномов Чебышева такой проблемы нет. Вот код из еще одной статьи:
double Sin7(double x)
{
x *= 0.63661977236758134308; // 2/Pi
int sign = x < 0.0;
x = sign ? -x : x;
int xf = (int)x;
x -= xf;
if ((xf & 1) == 1)
x = 1 - x;
int per = ((xf >> 1) & 1) == 1;
double xx = x * x;
double y = x * (1.5707903005870776 + xx * (-0.6458858977085938 +
xx*(0.07941798513358536 - 0.0043223880120647346 * xx)));
return sign ^ per ? -y : y;
}В вашем случае не надо считать в double, а нужно перейти на float и остановится на 3-ей степени полинома.
Согласен. Вы правы в общем и целом.
В частности, на практических задачах существуют иные ситуации, где исключается влияние накопленной ошибки уже на алгоритмическом уровне: "сигнал получен" -> "сигнал обработан" -> "полёт продолжается".
Более того, ошибка слабо влияет на решение задачи, если скорость вычисления выше инертности системы.
В качестве наглядного примера представим процесс парковки длинного фургона к разгрузочному пандусу:
1) Исполнитель сидит за рулём и слабо различает пространственные границы заднего бампера и разгрузочного пандуса в кривые зеркала заднего вида.
2) Руководитель находится сзади фургона, хорошо различает границы, быстро оценивает допустимые пределы, но лишён возможности управления фургоном и точной оценки ситуации "в цифре".
3) Заметим, эта "парочка" легко решает задачу безаварийной паковки к пандусу без измерений и расчётов на калькуляторе.
4) "Назад","Стоп", "Вперёд", "Право", "Правее", "Лево", "Левее" - необходимый и достаточный набор команд Руководителя, понятных Исполнителю, чтобы совершить парковку без аварии за конечное число "шагов" или тактов управления. Ибо погрешность "вычислений" выше инертности системы, а жизненный цикл ошибки "вычислений" ограничен одним шагом.
Вероятно, существует возможность оценивать численную ошибку на каждом шаге управления, оценивать степень её накопления. Но, ускорится ли решение практической задачи парковки, если Руководитель и Исполнитель начнут общаться формально, точно и без ошибок?
- Поверни рулевое колесо на -15 градусов 34 минуты 12 секунд.
- Подай импульс (надави) на педаль акселератора с усилием 2 ньютона в течение 3-х секунд.
- Стоп! Пауза! Оцениваем пространственное положение. А подайте-ка лазерные дальномер и угломер. И калькулятор принесите. Программируемый.
:-)
Статистические методы оценки ошибок интересны и увлекательны, как и вся математика в целом. Практика диктует иные подходы. Например, в алгоритме Брезенхема оценка ошибки редуцируется до проверки только знака ошибки. И, это работает.
(imho)
Вариант с накоплением это один лишь из. Допустим, что функция рассогласования это как есть разница между синусом вычисленным и синусом истинным. Казалось бы, абсолютная величина ошибки это 1E-3, а значит и контур у нас жесткий, но смещенность оценки это как добавление к сигналу постоянной величины, и в АЧХ у вас появятся частоты (пусть и с малой амплитудой), в герцовых областях, со ввсеми вытекающими.
Согласен. В общем и целом Вы правы.
Прошу пояснить. О каких частотах "со всеми вытекаюшими" Вы предупреждаете?
Если рассуждать в общем и целом с точки зрения механики, то асимметрия - это источник люфта.
Механизм теряет способность к движению, если из него убрать люфт.
Механический люфт - источник вибрации. Вибрация - разрушает механизм, если попадает в его резонанс.
Механизмы служат надёжно и долго, если собственная частота резонанса отличается от рабочей частоты.
Дополнительное страхование рисков преждевременного разрушения механизмов обеспечивают виброгасители и виброопоры.
(imho)
Механизм теряет способность к движению, если из него убрать люфт.
Это кто вам такую глупость сказал. Самый простой пример - колесо. И кто сказал, что только люфт является источником вибраций? Из какой практики вы это почерпнули?
Механизмы служат надёжно и долго, если собственная частота резонанса отличается от рабочей частоты.
Справедливо только в помещениях и то не во всех.
Самый простой пример - колесо. И кто сказал, что только люфт является источником вибраций?
Вы правы, но в моём комментарии нет утверждения, что вибрации вызывает только люфт.
Отсутствие баланса подвижных деталей - это ошибка проектирования и/или производства в любом механизме.
Из какой практики вы это почерпнули?
Допускаю, что могу ошибаться, но мы с Вами знаем, что успешное проектирование и производство надёжных и долговечных механизмов требует осилить "слоёный пирог", приблизительно, из 15-и технических дисциплин, плюс "вишенка" = "Допуски и Посадки".
ДиП - дисциплина о сочленении деталей. Посадки с натягом применяются для неподвижных соединений, для подвижных - посадки с зазором, в просторечии - с люфтом.
Величина люфта (зазора в посадке) подбирается индивидуально для каждой подвижной пары деталей. Дефицит люфта грозит заклиниванием механизма. Профицит люфта - ускоряет износ и снижает КПД в силу паразитных вибраций в подвижной паре во время работы.
Люфт подвижных пар может находится за границами органов чувств человека. Но, если механические детали подвижны, то значит люфт там есть.
Это если, как говорится, грубо, "крупными мазками", на грани с глупостью.
В реальности есть куча нюансов, например, переходные посадки, однако, мы и так уже слишком далеко отклонились от темы.
Справедливо только в помещениях и то не во всех.
В интернете много роликов, где механики запускают старый механизм через проведение регламентных работ без замены основных частей. Например, есть видео о "возвращение к жизни" паровоза, трактора на паровой тяге, простоявших на задворках под открытым небом много десятков лет.
--
Извиняюсь за отклонение от темы.
Странно что не модифицировали через Чебышева для 45 градусного блока, ограничение в 3-5 членов по операциям плюс минус то же самое даст. Плюс много логических лишних, например ограничение на вводные данные, чем вас не устраивали циклы с отбрасыванием периода? Обычно в таких условиях есть смысл ставить блок рафинирования данных к единому "чистому" входному диапазону значений [0-360), потом четверти получаются также делением на коснтанту.
При рафинировании входных данных не забудьте разрешить коллизию с границами интервала, часто исполнители кода про нее забывают и бывают забавные моменты, когда поворот от 1 градуса до 360 идет путем длинной в 359 градусов.
Странно что не модифицировали через Чебышева для 45 градусного блока, ограничение в 3-5 членов
Думал об этом методе. Но, в последний момент появились сомнения в его эффективности в данном конкретном случае. Проверять не стал, применив похожий, но несколько иной способ.
чем вас не устраивали циклы с отбрасыванием периода
Тем, что любой цикл увеличивает расходы, как минимум, на условный переход. А "погоня" за производительностью стала мотиватором для данной работы.
забавные моменты, когда поворот от 1 градуса до 360 идет путем
Согласен.
Но в данном алгоритме подобная ситуация исключена.
Буду признателен, если подскажите тест, который позволит проверить утверждение выше на опубликованном исходном коде.
В каких проектах на МК требуется вычислять синус, косинус? И разве последние жирные stm32 не могут делать это быстро? И были такие критические ситуации когда всё тормозилось на вычислении косинуса, синуса?
Как минимум, любое векторное управление моторами требует тригонометрических вычислений.
Существуют различные датчики, где тоже важны тригонометрические вычисления.
И разве последние жирные stm32 не могут делать это быстро?
Применительно к процессорам Интел и АМД этот алгоритм вообще теряет смысл.
Вопрос лишь в том, стоит ли "стрелять из пушки по воробъям, если есть возможонсть поправить прицел на 'мелкашке' " ?
Здесь про оптимизацию вычислений на бюджетных, сверх дещёвых MPU для тех ситуаций, когда дешевле забыть про дейвайс, чем искать или восстанавливать.
Здесь про оптимизацию вычислений на бюджетных, сверх дещёвых MPU для тех ситуаций, когда дешевле забыть про дейвайс, чем искать или восстанавливать.
Это называется технический прогресс - когда для решения каких-то задач используются всё более и более дешёвые средства. :-)
Согласен.
Задача технического прогресса - повышать доступность для ширнармас передовых достижений науки и техники.
Задача технического прогресса решается через продвижение передовых достижений в массовое производство, как следствие, снижению их себестоимости и цены.
:-)
Увы, мы отвыкли от настоящего прогресса в сфере ПО, когда программы становятся быстрее и менее требовательны, выполняя всё те же задачи.
Согласен, vkni.
Мы так же забыли, что компьютерные программы могут работать годами без переустановки и обновления. :-)
0,0003 это относительная ошибка или абсолютная? И почему ошибка как функция не симметрична относительно 0?
0,0003 - это относительная ошибка, разность ( sint() - sinf() ).
Согласно требованиям, указанным в статье, ожидаемая ошибка алгоритма +/- 0,005.
В свою очередь, требование к ошибке +/- 0,005 сформировано на основании точности вероятных исполнительных устройств. Например, у большинства доступных шаговых двигателей паспортная точность 1.8 ° с допуском +/- 0,9 °, т.е. на два порядка хуже алгоритмической.
Таким образом, демонстрация расчётной ошибки с меньшим модулем и разрядом, чем в требованиях [ +/- 0,0003 .vs. +/- 0,005 ], гарантирует удовлетворительную точность для вероятных исполнительных устройств, Гарантирует точность, достижимую простым отбрасыванием младших разрядов без издержек на округление.
В условиях многократного резервирования по точности "борьба" за симметрию расчётной ошибки просто теряет смысл.
В случае векторного управления моторами и во многих других можно сыграть на том, что вычислять требуется соседние значения. Но чтобы не копить ошибку, старое нельзя напрямую вводить в уравнения. Зато можно использовать его как старт для метода итераций, который в этом случае сходится очень быстро. На 32 битах не пробовал, а на AVR при работе с фиксированной точкой требовалось около 5 итераций при ~30 тактах на итерацию.
Согласен. Вы правы применительно к задаче управления электромотором, характеризующейся регулярностью и периодичностью вычислений по принципу от достигнутого.
Представим задачу, где периодичность вырождена. Потребность вычислений возникает спонтанно, время от времени, как импульсная функция от состояния внешней среды.
Но, если такая потребность возникла, то время реакции критично.
И ещё важные вводные. Погрешность измерителя, погрешность исполнителя на три порядка хуже ~|1.0|, чем погрешность вычислителя | =>0,0003 |.
В чём смысл "борьбы" за симметрию ошибки вычислителя в четвёртом порядке, если с "высот" измерителя и исполнителя таких малых порядков нет.
Я никак не могу понять ситуацию с библиотечными функциями, скорость работы которых драматически зависит от величины аргумента. Это получается, что авторы библиотеки не тестировали производительность и не воспользовались очевидными свойствами симметричности и периодичности? Это ведь не экзотические функции, и это происходит в языке, которому 50 лет.
Я далёк от мира микроконтроллеров, но мне это кажется ненормальным. Может быть, этому есть логичное объяснение?
Имеется ввиду "величина аргумента в первой четверти". То есть при 0 < x < \pi/2. Это довольно естественно, если вы вычисляете sin(x) в цикле - чем дальше вы отстоите от 0, тем больше тактов надо сделать, чтобы придти к той же относительной точности.
Авторы библиотек тестировали производительность, но в неявных требованиях у них производительность стоит после точности. А в данном случае автор жертвует точностью.
Я никак не могу понять ситуацию с библиотечными функциями, скорость работы которых драматически зависит от величины аргумента.
Разделяю драмматизм ситуации.
Более того, тестирование библиотечных функций показывает фантастическую производительность на регулярных данных.
for ( float s, a = 0.; a < 46.; a += 15. )
{
...
s = sinf( f );
...
}
+============= SINF test ==================
+-------------- # 1 ---------------------
+-- RLS at 21:20:46 by STM32 Cortex M0
+-- CPU:32 MHz, STC[e000e014]:32000
a, sinf, clocks
0.0000, 0.0000, 1
15.0000, 0.2588, 1
30.0000, 0.5000, 1
45.0000, 0.7071, 1
И картина драмматически меняется, когда регулярность нарушается слабым шумом.
for ( float s, a = 0.; a < 46.; a += 15. )
{
...
s = sinf( a + noise() );
...
}
+============= SINF test ==================
+-------------- # 1 ---------------------
+-- RLS at 21:20:46 by STM32 Cortex M0
+-- CPU:32 MHz, STC[e000e014]:32000
a, sinf, clocks
0.1900, 0.0033, 2841
15.0054, 0.2589, 2874
30.0915, 0.5014, 2874
45.0548, 0.7078, 4706
Тут был тег сарказм или нет?
Тут был тег сарказм или нет?
В сообщении данные, подтверждённые многократным экспериментом.
А если забенчить вызов noise(). По идее это очень тяжелая функция
Выше условный код, для понимания. В реальности код слегка отличается:
float rand_number( float min, float max )
{
float rnd = (float) ( rand() - ( RAND_MAX / 2 ) ) / RAND_MAX;
return min + rnd * ( max - min );
}
#define NOISE_ON
//#undef NOISE_ON
void DasIstFantastish()
{
STimeStamp fxs, fxe;
float a, b, s;
int32_t t;
PUT_FORMAT_MSG( "%7sf, %7s, %7s\n", "angle", "sinf", "clocks" );
for ( float f = 0.; f < 46.; f += 15. )
{
#ifdef NOISE_ON
b = f + rand_number(-.5, .5);
#else
b = f;
#endif
a = ( b ) * M_PI / 180.;
this_moment( &fxs );
s = sinf ( a );
this_moment( &fxe );
t = this_moment_gap( &fxs, &fxe );
PUT_FORMAT_MSG( "%7.4f, %7.4f, %7ld\n", b, s, t );
}
}
Результат выполнения кода в зависимости от директивы NOISE_ON.
Так ведь в первом случае расчёты в рантайме вообще не проводятся. Компилятор вычислил значения на этапе компиляции. Тут вопрос не в регулярности данных, а в том, что всё известно на этапе компиляции.
Согласен. Вы правы.
И в этом как раз засада.
Компилятор сделал то, о чём его не просили:
1. Зарезервировал (своровал) лишнюю память для вычисленных им констант;
2. Исключил вызов функции, которая теоретически может выполнять параллельную, другую работу по факту вызова;
3. Внёс искажения во временные характеристики кода в 2500(!) раз.
Как Вы думаете, программисты настолько тупы, что не знают как представить известную до выполнения программы последовательность в виде массива констант? Если им это надо.
Что ещё может генерировать компилятор в обход директив программиста?
Погоня за сомнительным повышением производительности через оптимизацию двоичного кода компилятором уже приводит к тому, что программы, собранные с запретом оптимизации работаю эффективнее, чем при её наличии. К сожалению ныне надо всегда помнить об этом.
Компилятор делает ровно то, что вы ему сказали. У сишного/плюсового компилятора куча флагов оптимизаций. К тому же есть способы не дать компилятору оптимизировать код. Например, сделать максимальный угол не константным, а зависящим от состояния одного из пинов. Так что тут скорее вопросы не к компилятору, а к тому что вы не очень умеете в бенчмаркинг.
Как функция может выполнять другую работу? Если бы она что-то ещё делала, то компилятор не смог бы её предрасчетать. Плюс компиляторы чаще всего действуют в рамках стандарта. Стандарт не запрещает рассчитывать константы заранее. Не запрещает разворачивать циклы. Вот вы скорее всего и получили просто загрузку значения в память.
Кстати, а вы сравнивали производительность кода на разных компиляторах(не заметил, написали ли вы в статье, чем компилировали)?
а вы сравнивали производительность кода на разных компиляторах
Могу, конечно, заблуждаться, но прикладной программист и тестировщик чужих программ - это несколько разные специальности. Это как слесарь-инструментальщик и слесарь-механик. Вроде как в одном цеху, а задачи разные. Заниматься чужим делом - сомнительный путь. (imho)
Языки программирования высокого уровня, такие как "C/C++", их стандарты созданы для снижения зависимости программиста от поставщика оборудования и средств разработки.
Соблюдение стандарта программистом - это просто установка в строчке запуска компилятора значения, определённого в технических требованиях. Например, регламент по сборке ядра линукс требует 11-й стандарт, если память не изменяет.
С другой стороны, стандарты и компиляторы делают люди, а не боги.
Людям свойственно ошибаться.
не заметил, написали ли вы в статье, чем компилировали
А внимательно-ли Вы читали статью? :-)
Зачем это всё? А просчитать таблицу, если нужна повышенная точность - воспользоваться апроксимацией из наиболее близких значний? По-моему, бред какой-то.
Согласен, это известный, проверенный подход.
Но, здесь суть в том, что точность требуется не повышенная, а гарантированная. И не в точках, а непрерывно с шагом 0,01 ° на всей области определения аргумента [ -5400 °.. +5400° ], применительно к бюджетным MSU с дефицитом памяти и производительности.
Где выигрыш в статических таблицах, если задача решается алгоритмически за несколько десятков слов бинарного кода?
Но истину тут может раскрыть только эксперимент. Да и принцип «лучшее — враг хорошего» здесь как нельзя лучше применяется. Так что смотрите сами.
Но я бы чисто из любопытства эксперимент провёл бы :)
Честно говоря, у вас как-то странно смещены значения, это может выплыть боком и привести к накоплению ошибки.
Вот что дало простое суммирование по 1 градусу:
[0] : 0.000000 - 0.000000 = 0.000000
[1] : 0.017456 - 0.017452 = 0.000004
[2] : 0.034790 - 0.034899 = -0.000109
[3] : 0.052216 - 0.052336 = -0.000120
[4] : 0.069580 - 0.069756 = -0.000176
[5] : 0.086975 - 0.087156 = -0.000181
[6] : 0.104309 - 0.104528 = -0.000219
[7] : 0.121643 - 0.121869 = -0.000226
[8] : 0.138947 - 0.139173 = -0.000227
[9] : 0.156219 - 0.156434 = -0.000215
[10] : 0.173431 - 0.173648 = -0.000217
[11] : 0.190643 - 0.190809 = -0.000166
[12] : 0.207764 - 0.207912 = -0.000148
[13] : 0.224823 - 0.224951 = -0.000128
[14] : 0.241791 - 0.241922 = -0.000131
[15] : 0.258759 - 0.258819 = -0.000061
[16] : 0.275574 - 0.275637 = -0.000064
[17] : 0.292358 - 0.292372 = -0.000013
[18] : 0.308990 - 0.309017 = -0.000027
[19] : 0.325562 - 0.325568 = -0.000007
[20] : 0.342072 - 0.342020 = 0.000051
[21] : 0.358429 - 0.358368 = 0.000061
[22] : 0.374695 - 0.374607 = 0.000088
[23] : 0.390869 - 0.390731 = 0.000138
[24] : 0.406921 - 0.406737 = 0.000185
[25] : 0.422791 - 0.422618 = 0.000172
[26] : 0.438568 - 0.438371 = 0.000197
[27] : 0.454193 - 0.453991 = 0.000203
[28] : 0.469696 - 0.469472 = 0.000224
[29] : 0.485046 - 0.484810 = 0.000237
[30] : 0.500244 - 0.500000 = 0.000244
[31] : 0.515289 - 0.515038 = 0.000251
[32] : 0.530151 - 0.529919 = 0.000232
[33] : 0.544891 - 0.544639 = 0.000252
[34] : 0.559479 - 0.559193 = 0.000286
[35] : 0.573853 - 0.573576 = 0.000276
[36] : 0.588043 - 0.587785 = 0.000258
[37] : 0.602081 - 0.601815 = 0.000266
[38] : 0.615906 - 0.615661 = 0.000244
[39] : 0.629547 - 0.629320 = 0.000227
[40] : 0.642975 - 0.642788 = 0.000187
[41] : 0.656250 - 0.656059 = 0.000191
[42] : 0.669312 - 0.669131 = 0.000181
[43] : 0.682159 - 0.681998 = 0.000161
[44] : 0.694794 - 0.694658 = 0.000135
[45] : 0.707245 - 0.707107 = 0.000138
[46] : 0.719482 - 0.719340 = 0.000143
[47] : 0.731445 - 0.731354 = 0.000092
[48] : 0.743225 - 0.743145 = 0.000080
[49] : 0.754761 - 0.754710 = 0.000051
[50] : 0.766083 - 0.766044 = 0.000038
[51] : 0.777161 - 0.777146 = 0.000015
[52] : 0.787994 - 0.788011 = -0.000016
[53] : 0.798584 - 0.798636 = -0.000052
[54] : 0.808960 - 0.809017 = -0.000057
[55] : 0.819061 - 0.819152 = -0.000091
[56] : 0.828949 - 0.829038 = -0.000089
[57] : 0.838593 - 0.838671 = -0.000078
[58] : 0.847961 - 0.848048 = -0.000087
[59] : 0.857056 - 0.857167 = -0.000112
[60] : 0.865875 - 0.866025 = -0.000150
[61] : 0.874481 - 0.874620 = -0.000139
[62] : 0.882782 - 0.882948 = -0.000166
[63] : 0.890839 - 0.891007 = -0.000168
[64] : 0.898590 - 0.898794 = -0.000204
[65] : 0.906128 - 0.906308 = -0.000180
[66] : 0.913361 - 0.913545 = -0.000185
[67] : 0.920319 - 0.920505 = -0.000186
[68] : 0.927002 - 0.927184 = -0.000182
[69] : 0.933380 - 0.933580 = -0.000200
[70] : 0.939514 - 0.939693 = -0.000178
[71] : 0.945343 - 0.945519 = -0.000176
[72] : 0.950897 - 0.951057 = -0.000159
[73] : 0.956146 - 0.956305 = -0.000159
[74] : 0.961090 - 0.961262 = -0.000172
[75] : 0.965790 - 0.965926 = -0.000136
[76] : 0.970184 - 0.970296 = -0.000111
[77] : 0.974243 - 0.974370 = -0.000127
[78] : 0.978027 - 0.978148 = -0.000120
[79] : 0.981567 - 0.981627 = -0.000060
[80] : 0.984741 - 0.984808 = -0.000067
[81] : 0.987640 - 0.987688 = -0.000048
[82] : 0.990234 - 0.990268 = -0.000034
[83] : 0.992523 - 0.992546 = -0.000023
[84] : 0.994507 - 0.994522 = -0.000015
[85] : 0.996216 - 0.996195 = 0.000021
[86] : 0.997589 - 0.997564 = 0.000025
[87] : 0.998657 - 0.998630 = 0.000028
[88] : 0.999420 - 0.999391 = 0.000029
[89] : 0.999908 - 0.999848 = 0.000061
SUM = 0.000685
Я так и не смог понять, к чему все эти сложности со сплайнами.
Сплайн - это просто форма. Это форма представления многочлена, оптимизированная для компьютера.
(imho)
С интересом прочёл Вашу статью "Как посчитать синус быстрее всех на хабре". Спасибо за статью. Поставил плюс.
К сожалению, Ваша статья оставляет за скобками вопрос "Как быстро посчитать синус на бюджетном микроконтроллере".
Допускаю, что программирование MCU - это частный, скучный случай. Но, это тот самый случай, где цель оправдывает средства: "Назвался груздём - полезай в кузов!".
сплайн — это инструмент
Цитируя Ваш комментарий, выражаю согласие Вашим подходом в целом.
А в частности, вижу ключевое слово - "инструмент".
Это как топор. Можно рубить, колоть, тесать, гвозди забивать. Можно гвозди выдёргивать топором. Слухами земля полнится, что умельцы из топора могут кашу варить. :-)
уровень гармоник и постоянной составляющей, которые вы через сплайны Безье минимизировать никак не сможете
Практика показывает, что прежде, чем совершить какое-либо действие, надо ответить всего на один вопрос: А оно нам надо?
- Расскажите о взятии интеграла на практике. - обратились первокурсники к бывалому инженеру-технологу.
- Ну-у-у... - задумался инженер, - Намедни гайка в цеху в направляющий паз закатилась. Взяли интеграл. Согнули из тонкого профиля. Гайку достали.
Правдивая история, имевшая место быть.
Считаю бесперспективными споры между теоретиками и практиками, которые подобны альпинистам, восходящими на одну и ту же гору с разных сторон.
Первые видят общее. Вторые видят частное. Первые видят правила. Вторые видят исключения. И все забывают в споре, что стремятся к одной и той же вершине.
"Теория - это когда все известно, но ничего не работает. Практика - это когда все работает, но никто не знает почему." А. Энштейн.
К сожалению, Ваша статья оставляет за скобками вопрос «Как быстро посчитать синус на бюджетном микроконтроллере»Наверно потому, что понятие «бюджетный» vs. «производительный» очень сильно варьируется, особенно если рассматривать их на протяжении последних 20 лет, равно как и доступный набор команд типа возможности оперировать числами с плавающей точкой. Равно как и есть разница между синтезом синусоиды в 1 герц и 1 кило/мега/гигагерц.
Правдивая история, имевшая место быть.Слышал эту «правдивую» историю в миллионе вариаций. Ну да, инженер скорее возьмёт «Таблицу объёмов красных резиновых мячей», чем будет считать его вручную. Но если такой таблицы в наличии нет — хочешь не хочешь, интегралы вспомнить придётся.
Считаю бесперспективными споры между теоретиками и практикамиСчитаю бесперспективным противопоставлять практику и теорию, да и в чистые теоретики вы меня рановато записали.
Практика — это когда все работает, но никто не знает почемуА также никто не знает, почему это «всё» ломается, работает не так, как хочется, и как его заставить работать так, как надо.
А оно нам надо?Контроль гармоник и постоянной составляющей? В некоторых случаях может быть фатальным для реального оборудования.
Что насчет CORDIC? Это по-моему вполне себе стандарт быстрого вычисления тригонометрии на микроконтроллерах. Вроде бы даже в DSP либе есть его быстрая реализация с использованием специальных команд процессора.
пример функции косинус на golang интервал 0...90 градусов
интервал разбит на 4 равных отрезка
максимальное отклонение от настоящего косинуса на 85 градусах =
0.08715574274765812 - 0.0876323 = -0,000476557
для расчета требуется всего 2 умножения и 2 сложения. Точность с моей точки зрения подходит для микроконтроллеров. Си не владею, попробовал на golang. на качество кода (работает) прошу не обращать внимания, все равно его надо переписывать под конкретные задачи. Смысл в том что коэффициенты a b c я могу рассчитывать в скайлабе. Нужную точность можно получить увеличением числа интервалов. Так при переходе от 4 до 5 интервалов точность увеличилась примерно в два раза. Надеюсь что это вам поможет в реальных разработках, т.к. для меня это просто хобби
// sin_cos project main.go
package main
import (
"fmt"
"math"
)
const pi32 float64 = math.Pi
func Cos4(ugol float32) float32 {
/// ugol от 0 до пи/2
var interval int8
var a float32
var b float32
var c float32
interval = int8((8 * float64(ugol)) / pi32)
switch interval {
case 0:
a = -0.4888191
b = -0.0018803
c = 1
case 1:
a = -0.4144009
b = -0.0638028
c = 1.0128406
case 2:
a = -0.2768938
b = -0.2824576
c = 1.0997504
case 3:
a = -0.0972322
b = -0.7072145
c = 1.3508006
default:
a = 0
b = 0
c = 0
}
return ugol*(a*ugol+b) + c
}
func main() {
var arg1 float64
for ii := 0; ii <= 90; ii++ {
arg1 = float64(ii) * pi32 / float64(180) ///, cos(1)
fmt.Print(ii, "\t", arg1, "\t", math.Cos(arg1))
fmt.Print("\t", Cos4(float32(arg1)))
fmt.Println("\t", 1000*(float32(math.Cos(arg1))-Cos4(float32(arg1))))
}
}
Сравнительно-интересный алгоритм. Спасибо.
Cos4 опережает по скорости библиотечную функцию cosf, но немного отстаёт от алгоритма cosint.
Провести "честное" сравнение производительности возможности нет, т.к. в алгоритме Cos4 отсутсвуют обязательные части:
- единица измерения аргумента угловой градус, 1.0 ° ;
- область определения аргумента [ -5400 ° .. 5400 ° ];
Добавление обязательных частей замедлит работу Cos4.
Сравнительный тест проведён на платформе Cortex M0 на интервале
[ 0 ° .. 90 ° ] с шагом 3 ° плюс малый шум.
Ошибка - разность с результатом библиотечной функции cosf().
приношу извинения, при переписывании алгоритма допущена опечатка, искажающая результат.
Сравнительные характеристики после устранения опечатки.
Замечание об отсутствии обязательных частей в алгоритме Cos4 актуально.
Ниже Cos4 на C.
В коде малые правки, ускоряющие работу на тестовой платформе Cortex M0:
-- отказ от типа float64 в пользу float32 ( ускорение более чем в два раза );
-- отказ от типа int8 в пользу int32 ( ускорение приблизительно на 15% ).
#ifndef M_PI
# define M_PI 3.14159265358979323846 /* pi */
#endif
typedef double float64;
typedef float float32;
#define pi32 (float32)M_PI
float32 cos4( float32 ugol )
{
/// ugol от 0 до пи/2
int32_t interval;
float32 a;
float32 b;
float32 c;
interval = (int32_t) ( ( 8 * (float32) ugol ) / pi32 );
switch ( interval )
{
case 0:
a = -0.4888191;
b = -0.0018803;
c = 1;
break;
case 1:
a = -0.4144009;
b = -0.0638028;
c = 1.0128406;
break;
case 2:
a = -0.2768938;
b = -0.2824576;
c = 1.0997504;
break;
case 3:
a = -0.0972322;
b = -0.7072145;
c = 1.3508006;
break;
default:
a = 0;
b = 0;
c = 0;
break;
}
return ugol * ( a * ugol + b ) + c;
}numeric
я легко считаю коэффициенты a b c в своем скрипте на скайлабе. попробовал рассчитать коэффициенты для 6 интервалов точность увеличилась . размер исполняемого кода чуть чуть. максимальное отклонение от настоящего косинуса на 85 градусах =
0,0523359562429439 - 0,05247843 = -0,000142477
на 4 интервалах максимальная ошибка была -0,000476557 т.е. рост точности примерно в 3 раза. Основной смысл в том что можно числом интервалов задаваемом в скайлабе регулировать точность вычислений косинуса ( и синуса другим скриптом). Косинус на 6 интервалов:
package main
import (
"fmt"
"math"
)
const pi32 float64 = math.Pi
func Cos6(ugol float32) float32 {
/// ugol от 0 до пи/2
var interval int8
var a float32
var b float32
var c float32
interval = int8((12 * float64(ugol)) / pi32)
switch interval {
case 0:
a = -0.4950150
b = -0.0005591
c = 1
case 1:
a = -0.4612805
b = -0.0193026
c = 1.0025949
case 2:
a = -0.3961106
b = -0.0885169
c = 1.0209687
case 3:
a = -0.3039463
b = -0.2340789
c = 1.0784413
case 4:
a = -0.1910687
b = -0.4710485
c = 1.2028110
case 5:
a = -0.0651700
b = -0.8009399
c = 1.4189139
default:
a = 0
b = 0
c = 0
}
return ugol*(a*ugol+b) + c
}
func main() {
var arg1 float64
for ii := 0; ii <= 90; ii++ {
arg1 = float64(ii) * pi32 / float64(180) ///, cos(1)
fmt.Print(ii, "\t", arg1, "\t", math.Cos(arg1))
fmt.Print("\t", Cos6(float32(arg1)))
fmt.Println("\t", 1000*(float32(math.Cos(arg1))-Cos6(float32(arg1))))
}
}
SemenovVV,
искренне рад видеть, что Cos6 демонстрирует отличные показатели на платформе M0:
- хорошая скорость: в 3-4 раза быстрее стандартной функции cosf();
- малое потребление памяти: 280 байт бинарного кода;
- точность выше в два раза, чем у cost() и Cos4().
Сравнительная точность:
Сравнительная скорость счёта:
numeric
скрипт на VBA. вставить в книгу Excel и можно считать коэффициенты квадратичного разложения для синуса и косинуса в зависимости от числа интервалов
Option Explicit
Sub main()
Dim kol_int As Integer ''' количество инетвалов
kol_int = 7
''' расчет коэффициентов квадратичного представления
Call calc_abc_sin(kol_int)
Call calc_abc_cos(kol_int)
End Sub
Sub calc_abc_cos(kol_int As Integer)
Dim ii As Integer, xx1 As Double, xx2 As Double, xx3 As Double
Dim yy1 As Double, yy2 As Double, yy3 As Double
Dim step As Double, wsp1 As Double, wsp2 As Double, wsp3 As Double
Dim r_sin1() As Double, r_sin2() As Double, r_sin3() As Double
step = pi32 / (2 * kol_int)
xx1 = 0
yy1 = 1
ReDim r_sin1(kol_int + 1)
ReDim r_sin2(kol_int + 1)
ReDim r_sin3(kol_int + 1)
For ii = 1 To kol_int
xx2 = xx1 + step
yy2 = Cos(xx2)
xx3 = (xx2 + xx1) / 2
yy3 = Cos(xx3)
wsp1 = 0
wsp2 = 0
wsp3 = 0
Call koef_parabola(xx1, yy1, xx2, yy2, xx3, yy3, wsp1, wsp2, wsp3)
r_sin1(ii) = wsp1
r_sin2(ii) = wsp2
r_sin3(ii) = wsp3
xx1 = xx2
yy1 = yy2
Next
Лист1.Cells(1, 6).Value = "Косинус"
Лист1.Cells(2, 6).Value = "a"
Лист1.Cells(2, 7).Value = "b"
Лист1.Cells(2, 8).Value = "c"
For ii = 1 To kol_int
Лист1.Cells(ii + 2, 6).Value = r_sin1(ii)
Лист1.Cells(ii + 2, 7).Value = r_sin2(ii)
Лист1.Cells(ii + 2, 8).Value = r_sin3(ii)
Next
End Sub
Sub calc_abc_sin(kol_int As Integer)
Dim ii As Integer, xx1 As Double, xx2 As Double, xx3 As Double
Dim yy1 As Double, yy2 As Double, yy3 As Double
Dim step As Double, wsp1 As Double, wsp2 As Double, wsp3 As Double
Dim r_sin1() As Double, r_sin2() As Double, r_sin3() As Double
step = pi32 / (2 * kol_int)
xx1 = 0
yy1 = 0
ReDim r_sin1(kol_int + 1)
ReDim r_sin2(kol_int + 1)
ReDim r_sin3(kol_int + 1)
Лист1.Cells.Clear
For ii = 1 To kol_int
xx2 = xx1 + step
yy2 = Sin(xx2)
xx3 = (xx2 + xx1) / 2
yy3 = Sin(xx3)
wsp1 = 0
wsp2 = 0
wsp3 = 0
Call koef_parabola(xx1, yy1, xx2, yy2, xx3, yy3, wsp1, wsp2, wsp3)
r_sin1(ii) = wsp1
r_sin2(ii) = wsp2
r_sin3(ii) = wsp3
xx1 = xx2
yy1 = yy2
Next
Лист1.Cells(1, 1).Value = "шаг= " + Format(step, "0.0000000")
Лист1.Cells(1, 2).Value = "Cинус"
Лист1.Cells(2, 1).Value = "интервал"
Лист1.Cells(2, 2).Value = "a"
Лист1.Cells(2, 3).Value = "b"
Лист1.Cells(2, 4).Value = "c"
For ii = 1 To kol_int
Лист1.Cells(ii + 2, 1).Value = ii
Лист1.Cells(ii + 2, 2).Value = r_sin1(ii)
Лист1.Cells(ii + 2, 3).Value = r_sin2(ii)
Лист1.Cells(ii + 2, 4).Value = r_sin3(ii)
Next
End Sub
Sub koef_parabola(x1 As Double, y1 As Double, x2 As Double, y2 As Double, x3 As Double, y3 As Double, _
ByRef a As Double, ByRef b As Double, ByRef c As Double)
Dim a1 As Double, a2 As Double
''''' расчет коэффициентов параболы по 3 точкам
a1 = y3 - (x3 * (y2 - y1) + x2 * y1 - x1 * y2) / (x2 - x1)
a2 = x3 * (x3 - x1 - x2) + x1 * x2
a = a1 / a2
b = (y2 - y1) / (x2 - x1) - a * (x1 + x2)
c = (x2 * y1 - x1 * y2) / (x2 - x1) + a * x1 * x2
End Sub
SemenovVV,
метод CosN, без сомнений, интересный и много обещающий.
Но, не могли бы вы доработать алгоритм CosN согласно техническим условиям из статьи?
Единица измерения параметра: угловой градус - 1,0 °.
Область определения параметра: (-5400) ° .. 5400 °.
Иначе получается, что мы сравниваем, пусть замечательный, но прототип и готовое решение. Что может вызывать некоторые сомнения.
для 6 интервалов:
// sin_cos project main.go
package main
import (
"fmt"
"math"
)
const pi32 float32 = math.Pi
func Cos6(ugol_i int16) float32 {
/// ugol_i от -5400 до 5400
var interval int8
var a float32
var b float32
var c float32
var rez float32
var ugol float32
var kwadr int8
var znak int8
ugol_i = ugol_i % 360
if ugol_i < 0 {
ugol_i = ugol_i + 360
}
kwadr = int8((ugol_i / 90))
znak = 1
switch kwadr {
case 0:
ugol_i = ugol_i
case 1:
ugol_i = 180 - ugol_i
znak = -1
case 2:
ugol_i = ugol_i - 180
znak = -1
case 3:
ugol_i = 360 - ugol_i
}
interval = int8(ugol_i / 15)
ugol = (float32(ugol_i) * pi32) / 180
switch interval {
case 0:
a = -0.4950150
b = -0.0005591
c = 1
case 1:
a = -0.4612805
b = -0.0193026
c = 1.0025949
case 2:
a = -0.3961106
b = -0.0885169
c = 1.0209687
case 3:
a = -0.3039463
b = -0.2340789
c = 1.0784413
case 4:
a = -0.1910687
b = -0.4710485
c = 1.2028110
case 5:
a = -0.0651700
b = -0.8009399
c = 1.4189139
default:
a = 0
b = 0
c = 0
}
if znak > 0 {
rez = (a*float32(ugol)+b)*float32(ugol) + c
} else {
rez = -((a*float32(ugol)+b)*float32(ugol) + c)
}
return rez
}
func main() {
var arg1 float64
for ii := -5400; ii <= 5400; ii++ { // 360 5400
arg1 = float64(ii) * float64(pi32) / float64(180) ///, cos(1)
fmt.Print(ii, "\t", arg1, "\t", math.Cos(arg1))
fmt.Print("\t", Cos6(int16(ii)))
fmt.Println("\t", 1000*(float32(math.Cos(arg1))-Cos6(int16(ii))))
}
}
STM32. Про синус