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

Ответ 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:
Wikipedia предполагает, что FSINCOS был добавлен на 387 процессорах, поэтому вряд ли можно найти процессор, который его не поддерживает.

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

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

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

Ответ 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

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

Ответ 3

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

Ответ 4

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

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();

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

Edit

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

Ответ 5

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

cos(x)2 = 1 - sin(x)2

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

Ответ 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

Ответ 7

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

#define _GNU_SOURCE
#include <math.h>

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

Ответ 8

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

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

И в отношении взгляда, Эрик С. Раймонд в Art of Unix Programming (2004) (глава 12) прямо говорит о том, что это плохая идея (в настоящий момент времени):

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

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

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

Ответ 9

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

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

Ответ 10

Если вы хотите использовать коммерческий продукт и одновременно вычисляете количество вычислений sin/cos (так что вы можете использовать векторные функции), вы должны проверить Библиотека математического ядра Intel.

У него есть функция sincos

В соответствии с этой документацией в режиме высокой точности он составляет в среднем 13,08 часов/элемент на двухъядерном процессоре 2, что, я думаю, будет даже быстрее, чем fsincos.

Ответ 11

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

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

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

Ответ 12

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

Ответ 13

Для творческого подхода, как насчет расширения серии Тейлора? Поскольку они имеют схожие термины, вы можете сделать что-то вроде следующего псевдо:

numerator = x
denominator = 1
sine = x
cosine = 1
op = -1
fact = 1

while (not enough precision) {
    fact++
    denominator *= fact
    numerator *= x

    cosine += op * numerator / denominator

    fact++
    denominator *= fact
    numerator *= x

    sine += op * numerator / denominator

    op *= -1
}

Это означает, что вы делаете что-то вроде этого: начиная с x и 1 для sin и косинуса, следуйте шаблону - вычитайте x ^ 2/2! из косинуса вычесть х ^ 3/3! от синуса, добавьте x ^ 4/4! к косинусу, добавьте x ^ 5/5! на синус...

Я не знаю, будет ли это работать. Если вам нужна меньше точности, чем встроенные функции sin() и cos(), вы можете выбрать вариант.

Ответ 14

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

Помните, что cos (x) и sin (x) - действительная и мнимая части exp (ix). Поэтому мы хотим рассчитать exp (ix), чтобы получить оба. Предварительно вычисляем exp (iy) для некоторых дискретных значений y между 0 и 2pi. Переместим х на отрезок [0, 2pi). Затем мы выбираем y, ближайший к x и записываем
ехр (IX) = ехр (гу + (IX-гу)) = ехр (гу) ехр (я (х-у)).

Мы получаем exp (iy) из таблицы поиска. А так как | x-y | (не более половины расстояния между значениями y), ряд Тейлора будет сходиться хорошо всего за несколько членов, поэтому мы используем это для exp (i (x-y)). И тогда нам просто нужно комплексное умножение, чтобы получить exp (ix).

Другим приятным свойством этого является то, что вы можете его векторизовать с помощью SSE.

Ответ 15

Возможно, вам захочется взглянуть на http://gruntthepeon.free.fr/ssemath/, который предлагает векторную реализацию SSE, вдохновленную библиотекой CEPHES. Он имеет хорошую точность (максимальное отклонение от sin/cos порядка 5e-8) и скорость (немного превосходит fsincos на основе единого вызова и явный победитель над несколькими значениями).

Ответ 16

Я опубликовал решение, включающее встроенную сборку ARM, способную одновременно вычислять синус и косинус с двумя углами: Быстрый синус/косинус для ARMv7 + NEON

Ответ 17

Точное, но быстрое приближение функции sin и cos одновременно, в javascript, можно найти здесь: http://danisraelmalta.github.io/Fmath/ (легко импортируется в c/С++)

Ответ 18

Вы думали о том, чтобы объявить таблицы поиска для двух функций? Вам все равно придется "вычислять" sin (x) и cos (x), но это будет значительно быстрее, если вам не нужна высокая степень точности.

Ответ 19

Компилятор MSVC может использовать (внутренние) функции SSE2

 ___libm_sse2_sincos_ (for x86)
 __libm_sse2_sincos_  (for x64)

в оптимизированных сборках, если указаны соответствующие флаги компилятора (как минимум /O2/arch: SSE2/fp: fast). Названия этих функций, по-видимому, подразумевают, что они не вычисляют отдельные sin и cos, а оба "за один шаг".

Например:

void sincos(double const x, double & s, double & c)
{
  s = std::sin(x);
  c = std::cos(x);
}

Сборка (для x86) с /fp: fast:

movsd   xmm0, QWORD PTR _x$[esp-4]
call    ___libm_sse2_sincos_
mov     eax, DWORD PTR _s$[esp-4]
movsd   QWORD PTR [eax], xmm0
mov     eax, DWORD PTR _c$[esp-4]
shufpd  xmm0, xmm0, 1
movsd   QWORD PTR [eax], xmm0
ret     0

Сборка (для x86) без /fp: быстрая, но с /fp: точная вместо этого (которая по умолчанию) вызывает отдельные sin и cos:

movsd   xmm0, QWORD PTR _x$[esp-4]
call    __libm_sse2_sin_precise
mov     eax, DWORD PTR _s$[esp-4]
movsd   QWORD PTR [eax], xmm0
movsd   xmm0, QWORD PTR _x$[esp-4]
call    __libm_sse2_cos_precise
mov     eax, DWORD PTR _c$[esp-4]
movsd   QWORD PTR [eax], xmm0
ret     0

Итак,/fp: fast обязателен для оптимизации sincos.

Но учтите, что

___libm_sse2_sincos_

может быть не так точно, как

__libm_sse2_sin_precise
__libm_sse2_cos_precise

из-за пропущенного "точного" в конце названия.

В моей "слегка" более старой системе (Intel Core 2 Duo E6750) с новейшим компилятором MSVC 2019 и соответствующей оптимизацией мой тест показывает, что вызов sincos примерно в 2,4 раза быстрее, чем отдельные вызовы sin и cos.