Эффективность вычисления arcsin из таблицы поиска синуса

Question

Я реализовал справочную таблицу для вычисления значений синуса / косинуса в моей системе. Теперь мне нужны обратные тригонометрические функции (arcsin / arccos).

Мое приложение работает на встроенном устройстве, на котором я не могу добавить вторую таблицу поиска для arcsin, так как я ограничен в памяти программ. Поэтому решение, которое я имел в виду, состояло в том, чтобы просмотреть таблицу поиска синусов, чтобы получить соответствующий индекс.

Мне интересно, будет ли это решение более эффективным, чем использование стандартной реализации из стандартной математической библиотеки.
Кто-нибудь уже экспериментировал с этим?

Текущая реализация LUT представляет собой массив значений синусов от 0 до PI / 2. Значение, хранящееся в таблице, умножается на 4096, чтобы остаться с целочисленными значениями с достаточной точностью для моего приложения. Таблица поиска с разрешением 1/4096, которая дает нам массив из 6434 значений. Тогда у меня есть две функции синус и косинус, которые принимают угол в радианах, умноженный на 4096 в качестве аргумента. Эти функции преобразуют данный угол в соответствующий угол в первом квадранте и считывают соответствующее значение в таблице.

Мое приложение работает на dsPIC33F со скоростью 40 MIPS, и я использую пакет компиляции C30.

Answer 1

Возможно, к сожалению, вам придется использовать компилятор C30, который не поддерживает C ++, в противном случае я бы указал на Оптимизация математических приложений с арифметикой с фиксированной запятой и связанной с ней библиотекой.

Однако применяются общие принципы алгоритма CORDIC , и объем памяти будет намного меньше, чем в текущей реализации.В статье объясняется, что генерация arctan () и arccos () и arcsin () можно рассчитать исходя из того, что описано здесь .

Конечно, это также предполагает, что вам также понадобятся квадратный корень и деление.Они могут быть дорогими, хотя PIC24 / dsPIC имеют аппаратное целочисленное деление.Статья по математическому ускорению также имеет дело с квадратным корнем.Вероятно, ваш подход к поисковой таблице будет быстрее для прямого поиска, но, возможно, не для обратного поиска, но подходы, описанные в этой статье, являются более общими и более точными (библиотека использует 64-битные целые числа как 36,28-битныес фиксированной точкой, вы можете уйти с меньшей точностью и дальностью в вашем приложении) и, конечно, быстрее, чем стандартная реализация библиотеки, использующая программную плавающую точку.

Answer 2

Довольно сложно сказать что-либо с уверенностью, так как вы не сказали нам об оборудовании, компиляторе или вашем коде.Однако, априори, я ожидаю, что стандартная библиотека вашего компилятора будет более эффективной, чем ваш код.

Answer 3

Вы можете использовать подход «наполовину», комбинируя грубую таблицу поиска для экономии памяти и числовое приближение для промежуточных значений (например, Серия Маклаурина , что будет более точным, чем линейная интерполяция.)

Некоторые примеры здесь .

Этот вопрос также имеет несколько связанных ссылок.

Answer 4

Бинарный поиск 6434 потребует ~ 12 поисков, чтобы найти значение, с последующей интерполяцией, если требуется большая точность.Из-за характера кривой греха, вы получите гораздо больше точности на одном конце, чем на другом.Если вы можете сэкономить память, то создание собственной обратной таблицы, равномерно распределенной по входам, вероятно, будет лучшим выбором для скорости и точности.

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