Какой алгоритм вычисления sin или cos используется в современных языках?

#алгоритм #любой_язык

Мне интересно, каким образом, например, реализован этот алгоритм в math.h:

Если разложение в ряд, то какое, и сколько элементов?
Если таблица, то на сколько элементов?
Есть ли какие-либо альтернативные варианты, которые я не привёл?

Интересует не конкретно math.h, а больше методы расчёта этих функций, используемые
в библиотеках языков программирования.
    

Ответы

Ответ 1

В современных алгоритмах вычисления трансцендентных функций творится полная жесть.
Там используется не один алгоритм, а целое семейство, и в зависимости от входного значения,
возможностей аппаратуры, необходимой точности и других параметров подбирается наиболее
подходящий.

Начнём с того, что вычисление синусов поддерживается на уровне железа. Но есть нюанс,
что аппаратная инструкция не отличается точностью, поэтому на неё часто не полагаются.

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

Какие конкретно многочлены и при каких условиях используются — смотрите сорцы.

Информация основана на ответе на вопрос How does C compute sin() and other math functions?,
автор Donald Murray. По ссылке вы найдёте больше подробностей.

Что касается Java, C#, PHP и остальных высокоуровневых языков, то в конечном счёте
они вызывают низкоуровневые заоптимизированные десятилетиями низкоуровневые реализации
на C, которые и выполняют всё это шаманство. Как правило, лезть туда не надо. Это одни
из самых проверенных временем алгоритмов.


Ответ 2

Матфункции в Java реализуются не на Java в чистом виде, а вызовом нативных  функций
Си. Какой бы альтернативный вариант вы не использовали, крайне сомнительно, что он
будет быстрее. А конкретная реализация зависит от платформы на которой запущена JVM.


Ответ 3

Есть справочник по спецфункциям под ред. Абрамовиц, Стиган. По сути - стандарт США.
Прописанные в нём формулы заточены либо под абсолютную, либо под относительную ошибку. 

Скажем, в районе нуля функцию sinc x = sin x / x выражают через экономизированные
представления рядов Тейлора. Экономизация состоит в замене степеней x на их выражения
через полиномы Чебышёва Pn = cos(n arccos x), которые в силу своей синуисоидальной
природы стабилизируют абсолютную ошибку (поскольку первый отброшенный полином - это
косинус). Синус получают как x*sinc x, и поэтому у него стабилизирована относительная
ошибка. 

Надо понимать, что речь шла о некоторой окрестности нуля. На дпугих интервалах могут
быть использованы другие методы.
Косинус как функция самостоятельного значения не имеет, поскольку даже в школе рассказывают,
как из синуса угла 0-90 можно линейными операциями получить и синус, и косинус любого угла.

Но есть и специализированные алгоритмы для табулирования синуса и косинуса. Например,
в самой популярной модификации Кули-Тьюки алгоритма быстрого (дискретного) преобразования
Фурье на массивах с размерностью степени двойки востребованы синусы и косинусы аргумента
pi / 2k. Такие таблицы обычно вычисляют рекуррентно, с использованием формул для половинного
аргумента.