Быстрая реализация тригонометрических функций для C++

Question

Краткая версия: Я хотел бы знать, существуют ли реализации стандартных тригонометрических функций, которые быстрее, чем те, которые включены в math.h.

Длинная версия: у меня есть программа, которая довольно тяжелая для численных моделей (это физическое моделирование), и это требует вызова тригонометрических функций, в основном sin и cos, много. В настоящее время я просто использую реализации, включенные в math.h. Профилирование показывает, что призывы к этим функциям стоят дороже, чем я ожидал (надеясь).

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

Answer 1

Вот некоторые хорошие слайды о том, как сделать приближения степенных рядов (не ряд Тейлора, хотя) функций тригонометрическими: http://www.research.scea.com/gdc2003/fast-math-functions.html

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

Приятная вещь в том, что вы также можете легко расширить его до SIMD, чтобы вы могли вычислить значение sin или cos из 4 значений в одном (2, если вы используете двойную точность).

Надежда, что помогает ...

Answer 2

Давным-давно на медленных машинах люди использовали массивы с заранее вычисленными значениями. другой вариант расчета с вашей собственной точностью как this: (ищите «определения серии»)

Answer 3

Если вы хотите использовать собственную реализацию, смотрите here, here и here

Также here (выделите Универсальной SIMD-Mathlibrary), если вам нужно вычислить грех/cos для больших массивов

Вы также можете попробовать использовать встроенные функции C++ SSE. Посмотрите here

Обратите внимание, что большинство современных компиляторов поддерживают оптимизацию SSE и SSE2. Например, для Visual Studio 2010 вам необходимо вручную включить его. Как только вы это сделаете, для большинства стандартных математических функций будет использоваться другая реализация.

Еще один вариант - использовать DirectX HLSL. Посмотрите here. Обратите внимание, что есть хорошие функции sincos, которые возвращают как sin, так и cos.

Обычно я использую IPP (который не является бесплатным). Для получения дополнительной информации смотрите here

Answer 4

Источник Quake 3 имеет некоторый код для предварительно вычисленного синуса/cos, ориентированного на скорость по точности, а не на основе sse, что, таким образом, довольно портативно (как по архитектуре, так и по внутреннему api). Вы также можете найти это резюме функций на основе sse и sse2 очень интересными: http://gruntthepeon.free.fr/ssemath/

Answer 5

A) Попытка сэкономить небольшие проценты будет не очень приятной. Отделение в 97 вместо 100 часов - еще долгое время.

B) Вы говорите, что вы профилированы и что функции триггера занимают больше времени, чем вам бы хотелось. Сколько? и как насчет оставшегося времени? Возможно, у вас есть большая рыба, чтобы жарить. Большинство профилографов based on the gprof concepts не сообщают вам о вызовах в середине стека, на которые вы могли бы сосредоточиться, чтобы сэкономить больше времени. Here's an example.

Answer 6

Для увеличения на 2-3% это почти наверняка не стоит риска погрешности, ошибки, допущения больше не соответствуют действительности (например, никогда не падают за пределы [-1,-1]) и т. Д., Если только вы не планируете использовать это на огромное количество машин (где 2-3% составляют тысячи или миллионы долларов электроэнергии и амортизируются стоимость машины).

Если у вас есть знания о домене, о которых вы пытаетесь достичь, вы можете ускорить вычисления в два или более раз. Например, если вам всегда нужны sin и cos того же значения, вычислите их близко друг к другу в коде и убедитесь, что ваш компилятор переводит их в инструкцию сборки FSINCOS (см. this question). Если вам нужна только небольшая часть полного диапазона функции, вы можете потенциально использовать набор полиномов низкого порядка, за которым следует итерация метода Ньютона, чтобы получить полную точность машины (или столько, сколько вам нужно). Опять же, это намного мощнее, если вы знаете, что вам нужны только некоторые значения - например. если вы можете использовать этот грех (x), близок к x вблизи нуля, и вам понадобятся только значения около нуля, тогда вы можете значительно уменьшить количество требуемых терминов.

Но, опять же, мой основной совет: 2-3% не стоит. Подумайте больше об используемых алгоритмах и других потенциальных узких местах (например, malloc ест слишком много времени?), Прежде чем оптимизировать это.

Answer 7

Я реализовал функцию быстрого синуса на стороне процессора, которая по крайней мере в два раза быстрее, чем функция sine math.h, однако я использовал очень маленькую таблицу поиска (20 поплавков). точность тоже неплохая; средняя относительная частота ошибок составляет 0,095%. Вы можете проверить это с http://www.hevi.info/tag/fast-sine-function/

Объяснение метода достаточно проста и основывается на том факте, что за грех малых а в (а) = а * пи/180 (см ссылку выше для доказательства)

Некоторая Тригонометрия

Несмотря на то, что можно достичь относительно точных результатов по формуле, приведенной выше для углов между 0 и 10, а угол становится шире, как она теряет accuricy. Поэтому мы должны использовать формулу для углов менее 10, но как ?!

Ответ исходит из формулы сложения тригонометрического синуса;

грех (а + б) = sin (а) соз (б) + sin (б) соз (а)

Если мы можем держать 'Ь' меньше, чем 10, то мы сможем использовать нашей формулы, чтобы найти синус с несколькими арифметическими операциями.

Предположим, нас спросили значение синуса для 71,654;

a = 70

b = 1.654

и

грех (71,654) = sin (70 + 1,654) = sin (70) Cos (1.654) + sin (1.654) сов (70)

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

Answer 8

Это должно быть довольно чертовски быстро, если вы можете оптимизировать его дальше, пожалуйста, сделайте и опубликуйте код, например, pastie.org или что-то в этом роде.

Технические характеристики компьютера -> 512 МБ Ram, Visual Studio 2010, Windows XP Professional SP3 версии 2002, Intel (R) Pentium (R) 4 CPU 2.8GHZ.

Это безумно точная информация и в некоторых ситуациях даст несколько лучшие результаты. Например. 90, 180, 270 градусов в C++ возвращает не десятичное число.

ПОЛНАЯ ТАБЛИЦА 0 до 359 градусов по: https://pastee.org/dhwbj

ФОРМАТ -> СТЕПЕНЬ # -> MINE_X (#), CosX (#), MINE_Z (#), SinZ (#).

Ниже приведен код, используемый для построения вышеуказанной таблицы. Возможно, вы сделаете это еще более точным, если используете более крупный тип данных. Я использовал unsigned short и сделал N/64000. Итак, что всегда cos (##) и sin (##), где ближайший к I округлен до этого индекса. Я также попытался использовать как можно больше дополнительных данных, поэтому это не будет какая-то загроможденная таблица с 720 значениями float для cos и sin. Это, вероятно, даст лучшие результаты, но будет полной потерей памяти. Таблица ниже настолько мала, насколько я мог это сделать. Я хотел бы посмотреть, можно ли сделать уравнение, которое может округлить до всех этих коротких значений и использовать это вместо этого. Я не уверен, что это будет быстрее, но это полностью устранит таблицу и, вероятно, не уменьшит скорость ничем и не будет.

Таким образом, точность по сравнению с операциями C++ cos/sin составляет 99,99998% на 100%.

Ниже приведена таблица, используемая для расчета значений cos/sin.

static const unsigned __int16 DEGREE_LOOKUP_TABLE[91] = 
{ 
    64000, 63990, 63961, 63912, 63844, 63756, 
    63649, 63523, 63377, 63212, 63028, 62824, 
    62601, 62360, 62099, 61819, 61521, 61204, 
    60868, 60513, 60140, 59749, 59340, 58912, 
    58467, 58004, 57523, 57024, 56509, 55976, 
    55426, 54859, 54275, 53675, 53058, 52426, 
    51777, 51113, 50433, 49737, 49027, 48301, 
    47561, 46807, 46038, 45255, 44458, 43648, 
    42824, 41988, 41138, 40277, 39402, 38516, 
    37618, 36709, 35788, 34857, 33915, 32962, 
    32000, 31028, 30046, 29055, 28056, 27048, 
    26031, 25007, 23975, 22936, 21889, 20836, 
    19777, 18712, 17641, 16564, 15483, 14397, 
    13306, 12212, 11113, 10012, 8907, 7800, 
    6690, 5578, 4464, 3350, 2234, 1117, 
     0, 
}; 

Ниже приведен фактический код, который вычисляет cos/sin.

int deg1 = (int)degrees; 
    int deg2 = 90 - deg1; 
    float module = degrees - deg1; 
    double vX = DEGREE_LOOKUP_TABLE[deg1] * 0.000015625; 
    double vZ = DEGREE_LOOKUP_TABLE[deg2] * 0.000015625; 
    double mX = DEGREE_LOOKUP_TABLE[deg1 + 1] * 0.000015625; 
    double mZ = DEGREE_LOOKUP_TABLE[deg2 - 1] * 0.000015625; 
    float vectorX = vX + (mX - vX) * module; 
    float vectorZ = vZ + (mZ - vZ) * module; 
    if (quadrant & 1) 
    { 
     float tmp = vectorX; 
     if (quadrant == 1) 
     { 
      vectorX = -vectorZ; 
      vectorZ = tmp; 
     } else { 
      vectorX = vectorZ; 
      vectorZ = -tmp; 
     } 
    } else if (quadrant == 2) { 
     vectorX = -vectorX; 
     vectorZ = -vectorZ; 
    } 

SPEEDS BELOW, используя первоначально упомянутые технические характеристики компьютера. Я запускал его в режиме отладки до того, как это режим отладки, но запускается через исполняемый файл, который, я считаю, отлаживается без отладки.

МОЙ МЕТОД

1,000 Iterations -> 0.004641 MS or 4641 NanoSeconds. 
100,000 Iterations -> 4.4328 MS. 
100,000,000 Iterations -> 454.079 MS. 
1,000,000,000 Iterations -> 4065.19 MS. 

COS/SIN МЕТОД

1,000 Iterations -> 0.581016 MS or 581016 NanoSeconds. 
100,000 Iterations -> 25.0049 MS. 
100,000,000 Iterations -> 24,731.6 MS. 
1,000,000,000 Iterations -> 246,096 MS. 

Итак, подведем итог выше выполнения как соз (###) и грех (###) с моим стратегия позволяет примерно 220 000 000 казней в секунду. Использование исходных данных компьютера. Это довольно быстро и использует очень мало памяти, поэтому это отличный заменитель математических функций cos/sin, которые обычно встречаются на C++. Если вы хотите, чтобы точность открыла ссылку, показанную выше, и есть распечатка с градусами 0 по 359.Также это поддерживает от 0 до 89 и квадранты с 0 по 3. Поэтому вам нужно либо использовать это, либо выполнять (DEGREES% 90).

Answer 9

Вы можете посмотреть this. В нем говорится об оптимизации греха, cos.