Итак, в математике в старших классах и, возможно, в колледже нас учат, как использовать триггерные функции, что они делают и какие задачи решают. Но они всегда представлялись мне черным ящиком. Если вам нужен синус или косинус чего-либо, вы нажимаете кнопку sin или cos на своем калькуляторе, и все готово. Что нормально.
Мне интересно, как обычно реализуются тригонометрические функции.
Во-первых, вам нужно сделать какое-то сокращение диапазона. Триггерные функции являются периодическими, поэтому вам нужно уменьшить аргументы до стандартного интервала. Для начала, вы можете уменьшить углы от 0 до 360 градусов. Но, используя несколько личностей, вы понимаете, что можете обойтись меньшими затратами. Если вы вычисляете синусы и косинусы для углов от 0 до 45 градусов, вы можете начать свой способ вычисления всех триггерных функций для всех углов.
После того, как вы уменьшите аргумент, большинство микросхем используют алгоритм CORDIC для вычисления синусов и косинусов. Вы можете слышать, как люди говорят, что компьютеры используют серию Тейлора. Звучит разумно, но это неправда. Алгоритмы CORDIC намного лучше подходят для эффективной аппаратной реализации. (Программные библиотеки могут использовать серию Тейлора, скажем, на оборудовании, которое не поддерживает триггерные функции.) Может потребоваться некоторая дополнительная обработка, использующая алгоритм CORDIC для получения достаточно хороших ответов, но затем делая что-то еще для улучшения точность.
К вышеизложенному есть некоторые уточнения. Например, для очень малых углов theta (в радианах) sin (theta) = theta для всей имеющейся точности, поэтому более эффективно просто вернуть theta, чем использовать какой-либо другой алгоритм. Так что на практике существует много логики для особых случаев, чтобы выжать из них всю возможную производительность и точность. Для чипов с меньшими рынками может потребоваться меньше усилий по оптимизации.
edit: Джек Гэнссл достойно обсуждает в своей книге по встроенным системам «Справочник по встроенному ПО» < / а>.
К вашему сведению: если у вас есть ограничения по точности и производительности, ряды Тейлора не следует использовать для аппроксимации функций в числовых целях. (Сохраните их для своих курсов по математике.) Они используют аналитичность функции в одной точке, например тот факт, что все его производные существуют в этой точке. Они не обязательно сходятся в интересующем интервале. Часто они плохо справляются с распределением точности аппроксимации функции, чтобы быть «идеальными» прямо возле точки оценки; ошибка обычно увеличивается по мере удаления от нее. И если у вас есть функция с любой непрерывной производной (например, прямоугольные волны, треугольные волны и их интегралы), ряд Тейлора даст вам неправильный ответ.
Лучшее «простое» решение при использовании полинома максимальной степени N для аппроксимации заданной функции f (x) на интервале x0 ‹x‹ x1 - это Чебышевское приближение; см. «Числовые рецепты» для хорошей дискуссии. Обратите внимание, что Tj (x) и Tk (x) в статье Wolfram, которую я связал, использовали cos и обратный косинус, это многочлены, и на практике вы используете рекуррентную формулу для получения коэффициентов. Опять же, см. Числовые рецепты.
изменить: В Википедии есть неплохая статья по теории приближения. Один из цитируемых ими источников (Харт, «Компьютерное приближение») больше не издается (а старые копии, как правило, дороги), но в нем подробно рассказывается о подобных вещах. (Джек Гэнссл упоминает об этом в выпуске 39 своего информационного бюллетеня The Embedded Muse.)
изменить 2: Вот некоторые ощутимые метрики ошибок (см. ниже) для Тейлора и Чебышева для sin (x). Некоторые важные моменты, на которые следует обратить внимание:
Не поймите меня неправильно: серия Тейлора будет работать правильно для синуса / косинуса (с разумной точностью для диапазона от -pi / 2 до + pi / 2; технически, имея достаточное количество терминов, вы можете достичь любой желаемой точности для всех реальных входных данных, но попробуйте вычислить cos (100) с использованием ряда Тейлора, и вы не сможете этого сделать, если не используете арифметику произвольной точности). Если бы я застрял на необитаемом острове с ненаучным калькулятором и мне нужно было вычислить синус и косинус, я бы, вероятно, использовал ряд Тейлора, поскольку коэффициенты легко запомнить. Но реальные приложения для написания собственных функций sin () или cos () достаточно редки, поэтому для достижения желаемой точности лучше всего было бы использовать эффективную реализацию, что в серии Тейлора не < / сильный>.
Диапазон = от -pi / 2 до + pi / 2, степень 5 (3 члена)
Диапазон = от -pi / 2 до + pi / 2, степень 7 (4 члена)
Диапазон = от -pi / 4 до + pi / 4, степень 3 (2 члена)
Диапазон = от -pi / 4 до + pi / 4, степень 5 (3 члена)
Диапазон = от -pi / 4 до + pi / 4, степень 7 (4 члена)
Я считаю, что они рассчитываются с использованием серии Тейлора или CORDIC. Некоторые приложения, интенсивно использующие триггерные функции (игры, графика), при запуске создают таблицы триггеров, чтобы они могли просто искать значения, а не пересчитывать их снова и снова.
Прочтите статью в Википедии о триггерных функциях. Хорошее место, чтобы узнать, как их реализовать в коде, - Числовые рецепты.
Я не особо разбираюсь в математике, но мое понимание того, откуда «берутся» sin, cos и tan, заключается в том, что они в некотором смысле наблюдаются, когда вы работаете с прямоугольными треугольниками. Если вы измеряете длины сторон группы разных прямоугольных треугольников и наносите точки на график, вы можете получить из этого sin, cos и tan. Как указывает Харпер Шелби, функции просто определяются как свойства прямоугольных треугольников.
Более сложное понимание достигается за счет понимания того, как эти отношения соотносятся с геометрией круга, что приводит к радианам и всему этому добру. Все это есть в статье в Википедии.
Чаще всего для компьютеров используется представление степенного ряда для вычисления синусов и косинусов, а также для других триггерных функций. Расширение этих рядов примерно до 8 членов позволяет вычислить необходимые значения с точностью, близкой к машинному эпсилону (наименьшее ненулевое число с плавающей запятой, которое может быть сохранено).
Метод CORDIC быстрее, поскольку он реализован на оборудовании, но в основном он используется для встроенных систем, а не для стандартных компьютеров.
Я хотел бы расширить ответ, предоставленный @Jason S. Используя метод подразделения домена, аналогичный описанному @Jason S, и используя приближения серии Маклорена, среднее (2-3) X ускорение по сравнению с tan (), sin () , были реализованы функции cos (), atan (), asin () и acos (), встроенные в компилятор gcc с оптимизацией -O3. Лучшие аппроксимирующие функции ряда Маклорена, описанные ниже, достигли точности двойной точности.
Для функций tan (), sin () и cos () и для простоты перекрывающаяся область от 0 до 2pi + pi / 80 была разделена на 81 равный интервал с «точками привязки» в pi / 80, 3pi / 80, ..., 161 дюйм / 80. Затем были оценены и сохранены tan (), sin () и cos () этих 81 опорной точки. С помощью триггерных идентификаторов для каждой триггерной функции была разработана отдельная функция серии Маклорена. Любой угол между ± бесконечностью может быть представлен триггерной аппроксимирующей функции, потому что функции сначала переводят входной угол в область от 0 до 2pi. Эти накладные расходы на перевод включены в накладные расходы аппроксимации.
Аналогичные методы были разработаны для функций atan (), asin () и acos (), где перекрывающаяся область от -1,0 до 1,1 была разделена на 21 равный интервал с точками привязки в -19/20, -17/20, .. ., 19/20, 21/20. Затем из 21 точки привязки была сохранена только atan (). Опять же, с помощью тождеств обратных триггеров, для функции atan () была разработана одна функция ряда Маклорена. Затем результаты функции atan () использовались для аппроксимации asin () и acos ().
Поскольку все аппроксимирующие функции обратного триггера основаны на аппроксимирующей функции atan (), допускается любое входное значение аргумента с двойной точностью. Однако аргумент, входящий в аппроксимирующие функции asin () и acos (), усекается до области ± 1, потому что любое значение вне его не имеет смысла.
Чтобы проверить аппроксимирующие функции, необходимо было оценить миллиард случайных оценок функций (то есть оптимизирующему компилятору -O3 не разрешалось обходить оценку чего-либо, потому что некоторые вычисленные результаты не использовались). Чтобы удалить смещение оценки миллиарда случайных чисел и обработки результатов, сначала рассчитывалась стоимость прогона без оценки какой-либо триггерной или обратной триггерной функции. Затем это смещение вычиталось из каждого теста, чтобы получить более репрезентативное приближение фактического времени оценки функции.
Таблица 2. Время, затраченное в секундах на выполнение указанной функции или функций миллиард раз. Оценки получаются путем вычитания временных затрат на оценку одного миллиарда случайных чисел, показанных в первой строке таблицы 1, из оставшихся строк в таблице 1.
Время, проведенное в загар (): 18.0515 18.2545
Время, проведенное в TAN3 (): 5.93853 6.02349
Время, проведенное в TAN4 (): 6.72216 6.99134
Время, проведенное в sin () и cos (): 19,4052 19,4311
Время, проведенное в SINCOS3 (): 7.85564 7.92844
Время, проведенное в SINCOS4 (): 9,36672 9,57946
Время нахождения в атане (): 15.7160 15.6599
Время нахождения в ATAN1 (): 6.47800 6.55230
Время, проведенное в ATAN2 (): 7.26730 7.24885
Время нахождения в ATAN3 (): 8.15299 8.21284
Время, проведенное в asin () и acos (): 36,8833 36,9496
Время, проведенное в ASINCOS1 (): 10,1655 9,78479
Время, проведенное в ASINCOS2 (): 10,6236 10,6000
Время, проведенное в ASINCOS3 (): 12.8430 12.0707
(В целях экономии места таблица 1 не показана.) Таблица 2 показывает результаты двух отдельных прогонов миллиарда оценок каждой аппроксимирующей функции. Первый столбец - это первый прогон, а второй столбец - второй прогон. Цифры «1», «2», «3» или «4» в именах функций указывают количество терминов, используемых в функции ряда Маклорена для оценки конкретного триггерного или обратного триггерного приближения. SINCOS # () означает, что sin и cos были вычислены одновременно. Точно так же ASINCOS # () означает, что asin и acos оценивались одновременно. Одновременная оценка обеих величин не требует дополнительных затрат.
Результаты показывают, что увеличение количества терминов немного увеличивает время выполнения, как и следовало ожидать. Даже наименьшее количество членов дает точность около 12-14 цифр везде, за исключением приближения tan (), где его значение приближается к ± бесконечности. Можно было бы ожидать, что даже у функции tan () будут проблемы.
Аналогичные результаты были получены на ноутбуке MacBook Pro высокого класса в Unix и на настольном компьютере высокого класса в Linux.
Если вы просите более физического объяснения sin, cos и tan, подумайте, как они соотносятся с прямоугольными треугольниками. Фактическое числовое значение cos (лямбда) можно найти, сформировав прямоугольный треугольник с одним из углов, являющимся лямбдой, и разделив длину стороны треугольника, примыкающей к лямбде, на длину гипотенузы. Точно так же для sin используйте противоположную сторону, разделенную гипотенузой. Для касательной используйте противоположную сторону, разделенную на прилегающую сторону. Классический мемоник, который следует запомнить, - это SOHCAHTOA (произносится как сокатоа).
