Результат также должен быть целым числом? x^-n это просто 1/x^n, который округляется до нуля для любого x, кроме 1. например pow(16, -2) - это 1/256.
Для целочисленного возвращаемого значения просто проверьте положительное значение n или возврат 1 или 0. Для возвращаемого значения FP вы можете использовать беззнаковую реализацию с абсолютным значением и условно принять обратную величину.
Для большой n величины вы можете использовать реализацию на основе FP exp / log (см. Мои комментарии к вопросу и Как я могу написать степенную функцию самостоятельно? ) вместо Циклическая реализация.
Для чистого целого числа с показателем без знака (или положительным знаком) возможна хорошая реализация без ответвлений с использованием обычного алгоритма смещения показателя вправо и умножения результата
если текущий бит был установлен . (См. https://eli.thegreenplace.net/2009/03/21/efficient-integer-exponentiation-algorithms для математики алгоритма и кода на Python.)
Мы можем использовать shr для сдвига вправо и CMOV для сдвинутого бита, а также разветвление петли для оставшегося значения.
Эта версия передает аргументы в те же регистры, что и x86-64 System V, но она прекрасно собирается в 32-битном режиме. Конечно, вы можете адаптировать его к любому соглашению о вызовах, которое вам нравится; ему нужно 4 регистра, поэтому вам может потребоваться сохранить / восстановить сохраненный вызовом регистр в 32-битных соглашениях о вызовах.
Это похоже на, но лучше, чем то, что вы получаете от компиляторов C x86-64 для прямого порта реализации Python. (https://godbolt.org/z/L9Kb98 gcc / clang структурирует цикл с test sil,1 / cmov` внутри, отдельно от ветви цикла в результате shr.)
;; untested
; integer power
; args in EDI,ESI (like the x86-64 System V calling convention)
; returns in EAX
; clobbers: EDX, EDI, ESI
ipown: ; (int a (EDI), unsigned n (ESI))
mov eax, 1 ; res = 1
test edi,edi
jz .zero_exponent
.loop:
mov edx, eax ; tmp = res
imul eax, edi ; res *= a (will be overwritten with old res if n&1 == 0)
imul edi, edi ; a*=a
shr esi, 1 ; n>>=1 setting ZF according to result, and CF= bit shifted out (old_n&1)
cmovnc eax, edx ; res = tmp if the bit was zero so we don't do res *= a this time
jnz .loop
.zero_exponent:
ret
На процессорах Broadwell Intel или более поздних, или AMD Ryzen, где у нас есть 1 цикл CMOV и 3 цикла задержки imul, мы надеемся, что он будет работать с 4 циклами на итерацию (цепочка зависимостей imul -> cmov через EAX).
imul полностью конвейеризован на современном x86 (или, по крайней мере, достаточно конвейерен на семействе AMD Bulldozer), но с пропускной способностью всего 1 за такт, поэтому существует потенциальный конфликт ресурсов между двумя инструкциями imul, которые могут оба ждут, пока edi будет готов. Но 3-тактная цепочка депо через EDI должна опережать 4-тактную цепочку imul / cmov, поэтому в любом цикле, когда и imul eax,edi, и imul edi,edi готовы к запуску, самое старое планирование готовности к началу должно составлять правильный выбор и начать imul eax,edi.
Обратите внимание, что mov edx,eax находится вне критического пути: он может работать параллельно с imul. Если бы я сделал tmp *= edi, mov был бы на критическом пути и повредил бы задержку на процессорах без исключения mov для исключения целочисленных регистров.
Конечно, максимальное число срабатываний цикла составляет всего 32 (если старший показатель установлен в показателе степени), поэтому выполнение в неупорядоченном порядке может проследить до конца цикла (и, надеюсь, разрешить цикл -выйдите из неверного прогноза до того, как умножения достигнут).
В этом цикле мало инструкций (по сравнению с его пропускной способностью), поэтому он должен иметь возможность значительно перекрываться с независимыми инструкциями до / после.
Ожидаемая задержка составляет приблизительно 4 cycles *trip_count = 4 * log2(n), т.е. 4 * позиция старшего установленного бита в показателе степени.
Для этой версии FP, x87 может быть действительно интересен для fcmov. В противном случае вы можете использовать сдвиги и SSE4 blendvps для смешивания на основе старшего бита другого регистра. 0.0 - это аддитивная идентичность, но не мультипликативная, поэтому AND с результатами сравнения не просто работает.