Как работают тригонометрические функции?

Question

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

Мне интересно, как обычно реализуются тригонометрические функции.

Answer 1

Во-первых, вы должны сделать какое-то уменьшение диапазона. Триггерные функции являются периодическими, поэтому вам нужно уменьшить аргументы до стандартного интервала. Для начала вы можете уменьшить углы до 0–360 градусов. Но, используя несколько идентичностей, вы понимаете, что можете обойтись с меньшими затратами. Если вы вычисляете синусы и косинусы для углов от 0 до 45 градусов, вы можете начать с расчета всех функций триггера для всех углов.

Как только вы уменьшили аргумент, большинство чипов используют алгоритм CORDIC для вычисления синусов и косинусов. Вы можете услышать, как люди говорят, что компьютеры используют серию Taylor. Это звучит разумно, но это не так. Алгоритмы CORDIC намного лучше подходят для эффективной аппаратной реализации. (Программные библиотеки могут использовать ряды Тейлора, скажем, на оборудовании, которое не поддерживает триггерные функции.) Может быть некоторая дополнительная обработка, использующая алгоритм CORDIC, чтобы получить довольно хорошие ответы, но затем сделать что-то другое для повышения точности.

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

Answer 2

Отредактируйте: Джек Гэнсл имеет достойное обсуждение в своей книге по встроенным системам, "Руководство по прошивке".

К вашему сведению: если у вас есть ограничения по точности и производительности, ряд Тейлора не следует использовать для аппроксимации функций для численных целей. (Сохраните их для своих курсов по исчислению.) Они используют аналитичность функции в одной точке, например, тот факт, что все ее производные существуют в этой точке. Они не обязательно сходятся в интересующем интервале. Часто они делают паршивую работу по распределению точности аппроксимации функции, чтобы быть "идеальной" прямо возле точки оценки; ошибка обычно увеличивается вверх по мере удаления от нее. И если у вас есть функция с любой непрерывной производной (например, прямоугольные волны, треугольные волны и их интегралы), ряд Тейлора даст вам неправильный ответ.

Наилучшее "простое" решение при использовании полинома максимальной степени N для аппроксимации заданной функции f(x) на интервале x0 чебышевского приближения; см. Численные Рецепты для хорошего обсуждения. Обратите внимание, что Tj(x) и Tk(x) в статье Вольфрама, на которую я ссылался, использовали cos и обратный косинус, это полиномы, и на практике вы используете формулу повторения для получения коэффициентов. Снова, см. Численные Рецепты.

Отредактируйте: у Wikipedia есть приличная статья по теории приближения. Один из источников, которые они цитируют (Харт, "Компьютерные аппроксимации"), вышел из печати (и использованные копии, как правило, стоят дорого), но подробно рассказывает о подобных вещах. (Джек Гэнсл упоминает об этом в выпуске 39 своего бюллетеня The Embedded Muse.)

редактировать 2: Вот некоторые метрики ощутимой ошибки (см. ниже) для Тейлора против Чебышева для греха (х). Некоторые важные моменты, на которые следует обратить внимание:

1. что максимальная погрешность приближения ряда Тейлора в заданном диапазоне намного больше, чем максимальная погрешность чебышевского приближения той же степени. (Примерно с той же ошибкой вы можете избежать Чебышева на один срок, что означает более высокую производительность)
2. Уменьшение дальности - огромная победа. Это связано с тем, что вклад полиномов более высокого порядка уменьшается при уменьшении интервала аппроксимации.
3. Если вы не можете избежать сокращения диапазона, ваши коэффициенты должны храниться с большей точностью.

Не поймите меня неправильно: ряд Тейлора будет правильно работать для синуса / косинуса (с разумной точностью для диапазона от -pi/2 до +pi/2; технически, с достаточным количеством терминов, вы можете достичь любой желаемой точности для всех реальных входов, но попробуйте вычислить cos(100), используя ряды Тейлора, и вы не сможете этого сделать, если не используете арифметику произвольной точности). Если бы я застрял на необитаемом острове с ненаучным калькулятором, и мне нужно было вычислить синус и косинус, я бы, вероятно, использовал ряды Тейлора, поскольку коэффициенты легко запомнить. Но в реальных приложениях для написания ваших собственных функций sin() или cos() достаточно редко, поэтому вам лучше использовать эффективную реализацию для достижения желаемой точности, а не ряд Тейлора.

Диапазон = от -pi/2 до +pi/2, степень 5 (3 условия)

• Тейлор: максимальная ошибка около 4,5e-3, f(x) = xx 3/6 + x 5/120
• Чебышев: максимальная ошибка около 7e-5, f(x) = 0,9996949x-0,1656700x ³ + 0,0075134x ⁵

Диапазон = от -pi/2 до +pi/2, степень 7 (4 условия)

• Тейлор: максимальная ошибка около 1,5e-4, f(x) = xx 3/6 + x ⁵ /120-x 7/5040
• Чебышев: максимальная ошибка около 6e-7, f(x) = 0.99999660x-0.16664824x ³ + 0,00830629x ⁵ -0,00018363x ⁷

Диапазон = от -pi/4 до +pi/4, степень 3 (2 условия)

• Тейлор: максимальная ошибка около 2,5e-3, f(x) = xx 3/6
• Чебышев: максимальная ошибка около 1,5e-4, f(x) = 0,999x-0,1603x3

Диапазон = от -pi/4 до +pi/4, степень 5 (3 условия)

• Тейлор: максимальная ошибка около 3,5e-5, f(x) = xx 3/6 + x ⁵
• Чебышев: максимальная ошибка около 6e-7, f(x) = 0,9999995x-0,1666016x3 + 0,0081215x5

Диапазон = от -pi/4 до +pi/4, степень 7 (4 условия)

• Тейлор: максимальная ошибка около 3e-7, f(x) = xx 3/6 + x ⁵ /120-x 7/5040
• Чебышев: максимальная ошибка около 1.2e-9, f(x) = 0.999999986x-0.166666367x ³ + 0,008331584x ⁵ -0,000194621x ⁷

Answer 3

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

Answer 4

Проверьте статью в Википедии о функциях триггера. Хорошее место, чтобы узнать о фактической реализации их в коде - это Numeric Recipes.

Я не большой математик, но мое понимание того, откуда "взялись" грех, кос и загар, заключается в том, что они, в некотором смысле, наблюдаются, когда вы работаете с прямоугольными треугольниками. Если вы измеряете длины сторон группы различных прямоугольных треугольников и наносите точки на график, вы можете получить из этого значения sin, cos и tan. Как указывает Харпер Шелби, функции просто определяются как свойства прямоугольных треугольников.

Более глубокое понимание достигается путем понимания того, как эти соотношения связаны с геометрией круга, что приводит к радианам и всей этой доброте. Все это есть в записи в Википедии.

Answer 5

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

Метод CORDIC быстрее, поскольку он реализован на оборудовании, но в основном он используется для встроенных систем, а не для стандартных компьютеров.

Answer 6

Я хотел бы расширить ответ, предоставленный @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, ..., 161pi/80. Затем tan(), sin() и cos () из этих 81 опорных точек были оценены и сохранены. С помощью идентификаторов триггеров для каждой функции триггеров была разработана отдельная функция ряда Маклаурина. Любой угол между ± бесконечностью может быть передан в функции аппроксимации триггера, потому что функции сначала переводят входной угол в область от 0 до 2pi. Эти накладные расходы на перевод включаются в накладные расходы на аппроксимацию.

Аналогичные методы были разработаны для функций atan (), asin () и acos (), где перекрывающийся домен от -1,0 до 1,1 был разделен на 21 равный интервал с точками привязки в -19/20, -17/20, ..., 19/20, 21/20. Тогда только atan () из этих 21 опорных точек был сохранен. Опять же, с помощью обратных тригональных тождеств, была разработана единственная функция ряда Маклаурина для функции 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

Время, проведенное в грехе () и соз (): 19.4052 19.4311

Время проведенное в SINCOS3(): 7.85564 7.92844

Время проведенное в SINCOS4(): 9.36672 9.57946

Время проведенное в atan(): 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.

Answer 7

Если вы просите более физическое объяснение греха, соз и загар, подумайте, как они соотносятся с прямоугольными треугольниками. Фактическое числовое значение cos(лямбда) может быть найдено путем формирования прямоугольного треугольника с одним из углов, являющегося лямбда, и делением длины стороны треугольников, примыкающей к лямбде, на длину гипотенузы. Точно так же для греха используйте противоположную сторону, разделенную на гипотенузу. Для касательной используйте противоположную сторону, разделенную на соседнюю сторону. Классический мемоник, чтобы помнить это - SOHCAHTOA (произносится как socatoa).