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

Ответ 1

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

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

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

Надеюсь, что это поможет...

Ответ 2

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

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

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

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

FORMAT → DEGREE # → MINE_X (#), CosX (#), MINE_Z (#), SinZ (#).

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

Таким образом, точность по сравнению с операциями С++ 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;
    }

СКОРОСТИ НИЖЕ, используя первоначально упоминаемые спецификации компьютера. Я запускал его в режиме отладки до того, как это режим отладки, но запускается через исполняемый файл, который, как я считаю, отлаживается без отладки.

МОЙ МЕТОД

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.

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

Ответ 3

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

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

Вы также можете попробовать использовать встроенные возможности С++ SSE. Посмотрите здесь

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

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

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

Ответ 4

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

Ответ 5

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

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

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

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

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

sin (a + b) = sin (a) cos (b) + sin (b) cos (a)

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

Допустим, нам задано значение синуса для 71.654, затем:

a = 70

b = 1.654

и

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

Ответ 6

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

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

Ответ 7

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

Ответ 8

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

Ответ 9

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

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

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