Как калькуляторы вычисляют синус?

Введение

Синус, одна из фундаментальных тригонометрических функций, играет важнейшую роль в различных областях, включая математику, физику, проектирование и computer science. Процесс его вычисления нетривиален, особенно при реализации в электронных калькуляторах, где крайне важна эффективность и точность.

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

Как вычисляется синус

Для начала давайте взглянем на функцию синуса:

Сразу же заметно, что эта функция периодическая и что она имеет сильную симметрию в интервале от 0 до π/2:

Иными словами, достаточно вычислить функцию в интервале [0;π/2]. После этого можно использовать переворот и смену знака для получения готового значения. Один из способов вычисления sin⁡(x) в уменьшенном интервале — применение хорошо известной аппроксимации при помощи рядов Тейлора:

Вот, как выглядит этот график:

Хотя этот способ прост, нам нужно вычислять очень высокие степени, а в окрестностях π/2 погрешности аппроксимирования могут становиться довольно большими. Например, при аппроксимации девятой степени результат для π/2 будет равен 1,00000354258428. Погрешность составляет 3e-6, и это довольно плохо, так как большинство вычислений выполняется с точностью до 15 знаков. Иными словами, мы теряем примерно 10 знаков точности!

Как на самом деле вычисляется синус

Хотя представленный выше способ довольно неточен, он служит основной для более качественных способов. По сути, все реализации синуса используют следующие три этапа:

1. Приведение: при помощи алгебраических фокусов приводим x к меньшему числу r.

2. Аппроксимация: вычисляем значение sin⁡(r) при помощи способов аппроксимации, например, рядов Тейлора.

3. Воссоздание: вычисляем окончательное значение sin⁡(x) на основании sin⁡(r).

Существует множество способов решения этой задачи. Ниже я представил тот, который, судя по статье компании Intel, она использует в своих процессорах. Они начинают с формулы

Здесь N — это целое число, выбранное так, чтобы минимизировать |r|. Иными словами, мы аппроксимируем x при помощи N⋅π/16, а r — это погрешность аппроксимации. Как это можно использовать? Благодаря тождественным равенствам сумм аргументов:

Нам нужно вычислить sin⁡(r) и cos⁡(r) — это этап аппроксимации, подробнее о нём будет рассказано ниже. Пока предположим, что нам известны и sin⁡(r), и cos⁡(r). Нам всё ещё нужно найти синус и косинус (N/32)2π. Обратим внимание, что и синус, и косинус имеют период 2π, так что нам достаточно вычислить N для N=0,1,2,…,31. Это всего 32 значения, мы легко можем вычислить их предварительно. При вычислении окончательного значения нам достаточно просто взять их из списка, что довольно эффективно.

Остаётся лишь один кусок пазла: как вычислить sin⁡(r)? В статье Intel не опубликовала конкретный многочлен, но упомянула, что использовала аппроксимацию минимакс. Эта аппроксимация находит многочлен и минимизирует максимальную погрешность на интервале:

где p — аппроксимирующий многочлен. Один из способов его вычисления — это алгоритм Ремеза. Результаты могут выглядеть так:

Максимальная погрешность этого многочлена составляет 4,1⋅10⁻⁹, что в тысячу раз лучше, чем исходная аппроксимация рядами Тейлора!

Заключение

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

[Прим. пер.: тригонометрические функции на разных архитектурах процессора, операционных системах и языках программирования могут давать разный ответ.]