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

Question

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

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

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

Answer 1

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

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

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

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

Answer 2

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

Характеристики компьютера -> 512 МБ Ram, Visual Studio 2010, Windows XP Professional SP3Версия 2002, процессор Intel® Pentium® 4 с тактовой частотой 2,8 ГГц.

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

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

FORMAT -> DEGREE # -> MINE_X (#),CosX (#), MINE_Z (#), SinZ (#).

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

Таким образом, точность по сравнению с операциями C ++ cos / sin составляет 99,999998%.до 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 METHOD

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).

Answer 3

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

Answer 4

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

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

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

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

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

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

Answer 5

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

Объяснение метода довольно простое и основано на том факте, что для малых a грех (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,665

и

sin (71.654) = sin (70 + 1.654) = sin (70) cos (1.654) + sin (1.654) cos (70)

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

Answer 6

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

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

Answer 7

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

Answer 8

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

Answer 9

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

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

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