Какой самый быстрый способ вычислить грех и cos вместе?

Question

Я хотел бы вычислить синус и косинус значения вместе (например, чтобы создать матрицу вращения). Конечно, я мог бы вычислять их отдельно один за другим, как a = cos(x); b = sin(x);, но мне интересно, есть ли более быстрый способ, когда нужны оба значения.

Edit: Подведем итоги ответов на данный момент:

• Влад сказал, что есть команда asm FSINCOS, вычисляющая их обоих (почти одновременно с вызовом только FSIN)

• Как и Chi заметил, что эта оптимизация иногда уже выполняется компилятором (при использовании флагов оптимизации).

• caf отметил, что функции sincos и sincosf, вероятно, доступны и могут вызываться напрямую, просто включив math.h

• tanascius Подход с использованием справочной таблицы обсуждается спорный. (Однако на моем компьютере и в тестовом сценарии он работает в 3 раза быстрее, чем sincos с почти такой же точностью для 32-разрядных чисел с плавающей запятой.)

• Джоэл Гудвин связан с интересным подходом техники чрезвычайно быстрого приближения с довольно хорошей точностью (для меня это даже быстрее, чем поиск по таблице)

Answer 1

Современные процессоры Intel / AMD имеют инструкцию FSINCOS для одновременного расчета функций синуса и косинуса. Если вам нужна сильная оптимизация, возможно, вам следует использовать ее.

Вот небольшой пример: http://home.broadpark.no/~alein/fsincos.html

Вот еще один пример (для MSVC): http://www.codeguru.com/forum/showthread.php?t=328669

Вот еще один пример (с gcc): http://www.allegro.cc/forums/thread/588470

Надеюсь, один из них поможет. (Я сам не использовал эту инструкцию, извините.)

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

Edit:
Википедия предполагает, что FSINCOS было добавлено на 387 процессорах, поэтому вы вряд ли найдете процессор, который его не поддерживает.

Edit:
Документация Intel гласит, что FSINCOS примерно в 5 раз медленнее, чем FDIV (то есть деление с плавающей запятой).

Edit:
Обратите внимание, что не все современные компиляторы оптимизируют вычисление синуса и косинуса в вызове FSINCOS. В частности, мой VS 2008 не делал этого таким образом.

Edit:
Ссылка на первый пример не работает, но на Wayback Machine все еще есть версия .

Answer 2

Современные процессоры x86 имеют инструкцию fsincos, которая будет выполнять именно то, что вы просите - вычислять sin и cos одновременно. Хороший оптимизирующий компилятор должен обнаружить код, который вычисляет sin и cos для одного и того же значения, и использовать команду fsincos для его выполнения.

Для этого понадобилось немного изменить флаги компилятора, но:

$ gcc --version
i686-apple-darwin9-gcc-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5488)
Copyright (C) 2005 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ cat main.c
#include <math.h> 

struct Sin_cos {double sin; double cos;};

struct Sin_cos fsincos(double val) {
  struct Sin_cos r;
  r.sin = sin(val);
  r.cos = cos(val);
  return r;
}

$ gcc -c -S -O3 -ffast-math -mfpmath=387 main.c -o main.s

$ cat main.s
    .text
    .align 4,0x90
.globl _fsincos
_fsincos:
    pushl   %ebp
    movl    %esp, %ebp
    fldl    12(%ebp)
    fsincos
    movl    8(%ebp), %eax
    fstpl   8(%eax)
    fstpl   (%eax)
    leave
    ret $4
    .subsections_via_symbols

Тада, он использует инструкцию fsincos!

Answer 3

Технически, вы бы достигли этого, используя комплексные числа и Формула Эйлера . Таким образом, что-то вроде (C ++)

complex<double> res = exp(complex<double>(0, x));
// or equivalent
complex<double> res = polar<double>(1, x);
double sin_x = res.imag();
double cos_x = res.real();

должно дать вам синус и косинус за один шаг. Как это сделать внутренне - это вопрос использования компилятора и библиотеки. Это может (и может) занять больше времени, чтобы сделать это таким образом (просто потому, что формула Эйлера в основном используется для вычисления комплекса exp с использованием sin и cos - а не наоборот), но могут быть некоторые возможна теоретическая оптимизация.

---

Редактировать

Заголовки в <complex> для GNU C ++ 4.2 используют явные вычисления sin и cos внутри polar, так что это не выглядит слишком хорошо для оптимизаций там, если компилятор не делает немного магии (смотрите -ffast-math и -mfpmath переключатели, как написано в ответ Чи ).

Answer 4

Когда вам нужна производительность, вы можете использовать предварительно вычисленную таблицу sin / cos (подойдет одна таблица, сохраненная в виде словаря). Ну, это зависит от точности, которая вам нужна (возможно, таблица будет слишком большой), но она должна быть очень быстрой.

Answer 5

Вы можете вычислить любой из них, а затем использовать идентификатор:

cos(x)<sup>2</sup> = 1 - sin(x)<sup>2</sup>

но, как говорит @tanascius, заранее рассчитанная таблица - это путь.

Answer 6

На этой странице форума есть очень интересные вещи, нацеленные на быстрое нахождение хороших приближений: http://www.devmaster.net/forums/showthread.php?t=5784

Отказ от ответственности: не использовал ничего из этого сам.

Обновление 22 февраля 2018: Wayback Machine - единственный способ посетить исходную страницу: https://web.archive.org/web/20130927121234/http://devmaster.net/posts/9648/fast-and-accurate-sine-cosine

Answer 7

Если вы используете библиотеку GNU C, то вы можете сделать:

#define _GNU_SOURCE
#include <math.h>

и вы получите объявления функций sincos(), sincosf() и sincosl(), которые вычисляют оба значения вместе -предположительно самым быстрым способом для вашей целевой архитектуры.

Answer 8

Многие математические библиотеки C, как указано в caf, уже имеют sincos (). Заметным исключением является MSVC.

• У Sun sincos () по крайней мере с 1987 года (двадцать три года; у меня есть справочная страница в печатном виде)
• HPUX 11 имел его в 1997 году (но не в HPUX 10.20)
• Добавлено в glibc в версии 2.1 (февраль 1999 г.)
• Стал встроенным в gcc 3.4 (2004), __builtin_sincos ().

А что касается поиска, Эрик С. Рэймонд в «1013 * искусстве программирования Unix» (2004) (глава 12) прямо говорит, что это плохая идея (в настоящее время):

"Другой пример - предварительные вычисления небольших таблиц - например, таблицы sin (x) по степени для оптимизации вращения в трехмерном графическом движке взять 365 × 4 байта на современной машине. До процессоров хватило быстрее, чем память требует кеширования, это была очевидная скорость оптимизация. В настоящее время может быть быстрее пересчитать каждый раз, а чем платить за процент дополнительных пропусков кэша, вызванных таблица.

"Но в будущем это может обернуться снова, когда кэши увеличатся. В целом, многие оптимизации являются временными и могут легко в пессимизации, как соотношение затрат. Единственный способ узнать это измерить и увидеть. "(из Искусство программирования Unix )

Но, судя по вышеизложенному, не все согласны.

Answer 9

Я не верю, что таблицы поиска обязательно являются хорошей идеей для этой проблемы. Если ваши требования к точности не очень низки, таблица должна быть очень большой. А современные процессоры могут выполнять много вычислений, пока значение выбирается из основной памяти. Это не один из тех вопросов, на которые можно правильно ответить аргументом (даже не моим), проверить и измерить и рассмотреть данные.

Но я бы посмотрел на быстрые реализации SinCos, которые вы найдете в библиотеках, таких как AMD ACML и Intel MKL.

Answer 10

В этой статье показано, как построить параболический алгоритм, который генерирует синус и косинус:

Трюк с DSP: одновременная параболическая аппроксимация греха и Cos

http://www.dspguru.com/dsp/tricks/parabolic-approximation-of-sin-and-cos