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

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

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

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

Полная таблица от 0 до 359 градусов: https://pastee.org/dhwbj

Формат - > степень # - > MINE_X (#), CosX (#), MINE_Z (#), SinZ (#).

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

Таким образом, точность по сравнению с операциями Cos/sin C++ составляет 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, обычно встречающихся в C++. Если вы хотите увидеть точность, откройте ссылку, показанную выше,и там есть печать из градусов 0 по 359. Кроме того, это поддерживает от 0 до 89 и квадранты от 0 до 3. Так что вам нужно либо использовать это, либо выполните (Градусы % 90).

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

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

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

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

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

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

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

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

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

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

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

Немного Тригонометрии

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

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

Грех(а+б) = Син(а) потому что(б) + грех(Б) потому что(A)

Если мы можем держать ‘b ' меньше 10, то мы сможем используйте нашу формулу для того, чтобы найти синус с помощью пары аритметических операций.

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

A = 70

B = 1,654

И,

Грех(71.654) = грех(70 + 1.654) = грех(70) потому что(1.654) + грех(1.654), потому что (70)

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

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

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

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

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

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