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

Question

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

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

Answer 1

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

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

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

Answer 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 3

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

Answer 4

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

Я не большой математик, но мое понимание того, откуда "взялись" грех, соз и загар, заключается в том, что они, в некотором смысле, наблюдаются, когда вы работаете с прямоугольными треугольниками. Если вы измеряете длины сторон группы различных прямоугольных треугольников и наносите точки на график, вы можете получить из этого значения 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 и tan, подумайте, как они соотносятся с прямоугольными треугольниками. Фактическое числовое значение cos (лямбда) может быть найдено путем формирования прямоугольного треугольника с одним из углов, являющегося лямбда, и делением длины стороны треугольников, примыкающей к лямбде, на длину гипотенузы. Точно так же для греха используйте противоположную сторону, разделенную на гипотенузу. Для касательной используйте противоположную сторону, разделенную на соседнюю сторону. Классический мемоник, чтобы помнить это - SOHCAHTOA (произносится как socatoa).