Комментарии 27
Собственно, тема-то осталась не раскрыта: вы прекрасно объяснили работу алгоритма, но не объяснили, чем он для вас так важен :)
Сам алгоритм мы могли наблюдать в компьютерах 70-80-х, микрокалькуляторах, в libcordic в Linux, факт. (интересно, как работали FPU типа 80287, 80387)
CORDIC - это последний шанс. Т.е. если у нас нет мат. сопроцессора, чтобы вызвать готовые тригонометрические функции, если нет памяти, чтобы держать таблицу значений или нам нужен синус или тангенс на полном периоде а не только на углах меньше 20, где их можно аппроксимировать линейной функцией. Вот тогда уже да, CORDIC вытаскивают из запылившегося ящика.
Ну не то, чтобы вытаскивают. Если надо крохотного размера, быстро и дешёво вычислять (например, векторное управление BLDC с частотой сотни кГц), можно взять микроконтроллер с аппаратным CORDIC. ( https://brushless.zone/stm32g4-cordic-vs-sinf-for-motor-control/ ). Хотя в нем и на таблицы памяти хватает и FPU есть, но это, всё равно, дольше.
Одно плохо - stm32g431 сложно в РФ купить за адекватные деньги
Аппаратный будет быстрее выборки по таблице? Не знаю как реализован на stm CORDIC, но в целом скорость вычисления зависит от разрядности, т.е. если мы хотим получить 16-битное значение, то должны ждать 16 тактов.
Не знаю как реализован на stm CORDIC
там реализован 24-битный юнит и в базе требует 29 циклов: https://www.st.com/resource/en/application_note/an5325-how-to-use-the-cordic-to-perform-mathematical-functions-on-stm32-mcus-stmicroelectronics.pdf
Я проверял скорость вычисления синуса на STM32G474. Там в регистр аргумента записывается угол, после чего в регистре состояния нужно ждать появления бита готовности. Я в цикле ожидания инкрементировал переменную чтобы узнать да сколько циклов вычислится синус. Так вот, количество циклов равно нулю! То есть бит готовности появляется практически сразу.
Тут такое.... В STM32G474 база Cortex-M4F, - соответственно в списке инструкций FPU синуса нет.... Совсем нет. Убеждаемся.
Что вы там намерили - ну, по крайней мере непонятно.
А в модуле Cordic - все-таки 29 циклов. Проверять - на ассемблере.
Конечно нет, так же как нет регистра состояния и бита готовности. Я писал про модуль CORDIC, который есть в этом микроконтроллере. И про его быстродействие. И проверять это можно на чём угодно.
Без цифр cycnt из dwt я бы тоже не поверил. Учитывая какую дичь иногда выдают компиляторы
Смотря как у вас подключена память. Если есть мегабайт встроенной – хорошо, если снаружи болтается и обращение занимает от 3 тактов, высчитать может быть быстрее
Выборка по таблице - это несколько операций сравнения (хоть и двоичным поиском) для поиска соседей, а потом ещё несколько float-операций для интерполяции.
Помню неск лет назад в одном проекте драйвера BLDC на stm32f4xx использовали как раз табличный метод, коллеги оценивали гарантированную частоту обработки в 32 кГц
На STM32x4 есть есть FPU, и фиксированная запятая работает в итоге медленнее, чем плавающая. Ну и памяти там валом, чтобы хранить таблицы, а потом (если вдруг надо очень точно) интерполировать между соседними точками...
Ну тут такая ситуация. Там где используется STM32 обычно хватает просто таблицы и CORDIC просто не нужен. Но там где он нужен, уже STM32 не вывозит. Это какой-нибудь широкий FFT, который скорее всего будет имплементирован на FPGA и в такой ситуации просто не будет столько памяти хранить комплексные коэффициенты. Тут уже надо считать коэффициенты на лету.
Ну, все-же sinf() работает несколько подольше 29 циклов.....
По поиску в большой таблице, которая находится у Бога на куличках (8 к значений во внешнем ОЗУ/ПЗУ) - думаю, что тоже будет дольше 29 циклов (честно признаюсь - не проверял....). Так-что вариант фактически безальтернативный по скорости для данного контроллера (ну, если устраивает "приблизительность" и фиксточка).
FPU-то там есть, но синуса нет. А библиотечная функция в итоге работает медленнее, чем CORDIC. И, как было справедливо замечено, float - это костыль, который программисты используют когда до конца не понимают алгоритм. Ведь результат вычисления синуса нужен в конечном итоге для записи в таймер очередного значения ШИМ, или для регистров другой периферии, но в любом случае это будет целое. Тогда зачем нужны лишние преобразования?
Костыль, но тянуть 64-и-более-разрядные вычисления из-за большого динамического диапазона (например в модемах) - дорогое удовольствие. И постоянно следить, чтобы разрядности хватало... На FPGA - понятное дело, а на MCU более 32 разрядов жутко медленно, float работает за 1 такт. Если тригонометрия табличная, то взять значение - тоже единицы тактов
Напрасно Вы так про "запылившийся ящик". Применение CORDIC не ограничено вычислениями элементарных функций. Напомню, что Волдер/Меджитт называли этот метод методом псевдоповоротов вектора. Например, сейчас этот метод широко используется в ФАР для фазирования и весовой суммирования, причём он удобен для построения конвейерного процессора формирования ДН. А "вектор" может быть не обязательно двумерный. Вся быстрая матричная арифметика, связанная с преобразование базовой системы координат делается на этом алгоритме, список просто бесконечно - там просто не паханое поле... А Вы про "ящик". Я думаю, что Вы пересмотрит Ваше отношение.
В самом начале же написано:
Перейду сразу к делу и скажу, почему я так сильно люблю этот алгоритм... по сути, фактические операции CORDIC весьма просты... но выполняет он их путём комбинирования векторной арифметики, тригонометрии, доказательств сходимости и продуманных техник компьютерных наук.
А что там с аппроксимацией полиномом? Если привести значение угла в диапазон от -pi/2 до pi/2, то можно использовать полином не очень большой степени. Или он будет всё же медленнее вышеописанного способа?
С точки зрения теории полином на отрезке прекрасно аппроксимирует синус, т.к. синус бесконечно дифференцируем. Но я подозреваю, что высокая точность потянет высокие степени полинома (почему-то есть ощущение, что нужна степень не ниже пятой), с которыми уже на практике могут быть траблы с переполнением, накоплением ошибки и т.д. Плюс вычисление полинома в точке по схеме Горнера это n именно умножений, а в вышеописанном алгоритме, как я понял, обходятся сдвигами, которые дешевле.
Тут важно то, что CORDIC очень хорошо ложится на FPGA, которая, по своей сути, является схемой, а не процессором. И в таком применении альтернатив у него практически нет. Поставить память, в которой держать значения, например, для 256 углов? А если нужно большее разрешение/точность? Пристроить к памяти автомат, который делает интерполяцию?
Несколько странно, конечно, что вы по статье решили использовать запятую в качестве разделителя.
https://web.archive.org/web/20170625184808/http://lab.polygonal.de/2007/07/18/fast-and-accurate-sinecosine-approximation/
На кривых проще както выглядит считать синус
Почему для меня так важен алгоритм CORDIC