Какова сложность / реальная стоимость exp в cmath по сравнению с FLOP?

Question

[Я глобально отредактировал вопрос, чтобы он был более «полезным» и ясным]

Мне было интересно о сложности реализации функции exp в cmath.

Под сложностью я подразумеваю алгоритмическую сложность, если это возможно. В противном случае стоимость по сравнению с операцией с плавающей запятой (например, дополнение)

следующие строки:

double x = 3;
double y = std::exp(x);

скомпилировать в:

...
19,23d16
       movq    %rax, -40(%rbp)
       movsd   -40(%rbp), %xmm0
       call    exp
       movsd   %xmm0, -40(%rbp)
       movq    -40(%rbp), %rax
...

exp должен быть динамически загружен во время выполнения, но я не могу найти много информации о алгоритмической сложности реализации. Кажется, что нет вызова специальной инструкции процессора (по крайней мере, на моей платформе x86_64 с gcc), поэтому где-то должна быть реализация, которую я не могу найти. На мой взгляд, алгоритм, вероятно, будет использовать двоичное представление входных данных, чтобы иметь очень слабую сложность, но я не смог найти ценную ссылку на эту тему.

Может быть, говорить об алгоритмической сложности в этом случае не представляется возможным, и все, что мы можем сделать, - это тестировать (см. Ответы ниже), но я не знаю, как мы можем объективно количественно определить разницу между операцией с плавающей запятой и вызовом до опыта?

Answer 1

Кажется, что сложность на самом деле постоянна, так как компилятор MSVC9 совершает некоторую магию битов, включая конкретные таблицы, битовые маски и ошибки Поскольку веток мало, конвейер инструкций должен сильно помочь. Ниже это то, что он делает на самом деле.

unpcklpd    xmm0,xmm0 
movapd      xmm1,xmmword ptr [cv] 
movapd      xmm6,xmmword ptr [Shifter] 
movapd      xmm2,xmmword ptr [cv+10h] 
movapd      xmm3,xmmword ptr [cv+20h] 
pextrw      eax,xmm0,3 
and         eax,7FFFh 
mov         edx,408Fh 
sub         edx,eax 
sub         eax,3C90h 
or          edx,eax 
cmp         edx,80000000h 
jae         RETURN_ONE 
mulpd       xmm1,xmm0 
addpd       xmm1,xmm6 
movapd      xmm7,xmm1 
subpd       xmm1,xmm6 
mulpd       xmm2,xmm1 
movapd      xmm4,xmmword ptr [cv+30h] 
mulpd       xmm3,xmm1 
movapd      xmm5,xmmword ptr [cv+40h] 
subpd       xmm0,xmm2 
movd        eax,xmm7 
mov         ecx,eax 
and         ecx,3Fh 
shl         ecx,4 
sar         eax,6 
mov         edx,eax 
subpd       xmm0,xmm3 
movapd      xmm2,xmmword ptr Tbl_addr[ecx] 
mulpd       xmm4,xmm0 
movapd      xmm1,xmm0 
mulpd       xmm0,xmm0 
addpd       xmm5,xmm4 
mulsd       xmm0,xmm0 
addsd       xmm1,xmm2 
unpckhpd    xmm2,xmm2 
movdqa      xmm6,xmmword ptr [mmask] 
pand        xmm7,xmm6 
movdqa      xmm6,xmmword ptr [bias] 
paddq       xmm7,xmm6 
psllq       xmm7,2Eh 
mulpd       xmm0,xmm5 
addsd       xmm1,xmm0 
orpd        xmm2,xmm7 
unpckhpd    xmm0,xmm0 
addsd       xmm0,xmm1 
add         edx,37Eh 
cmp         edx,77Ch 
ja          ADJUST 
mulsd       xmm0,xmm2 
sub         esp,10h 
addsd       xmm0,xmm2 
movlpd      qword ptr [esp+4],xmm0 
fld         qword ptr [esp+4] 
add         esp,10h 
ret              

Answer 2

Вообще говоря, сложность для примитивных типов должна быть очень быстрой.Как упоминают комментаторы, иногда есть инструкции для этого, и если нет, то есть хорошо известных быстрых алгоритмов, у Кнута есть хороший раздел по таким вещам.-множить , в котором используется наблюдение, что вы можете разбить любое возведение в степень на некоторое количество квадратов плюс самое большее еще одно умножение.Базовый алгоритм для n**k задан здесь и равен O ( lg k).

Answer 3

Здесь можно найти быструю реализацию exp, которая использует инструкции SSE.

Answer 4

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

Правильный подход, если вы хотите знать, это написать тестовые функции и рассчитать их время. Выполните цикл по миллиону присваиваний с плавающей запятой и рассчитайте его время, затем выполните цикл по миллиону присваиваний экспонент и вычислите время, а затем вычтите Не упустите оптимизатор на этом, как будто вы не используете результат присваиваний, это позволяет удалить весь цикл. Вы узнаете об этом благодаря чрезвычайно быстрому времени выполнения, которое не зависит от размера цикла.