c ++ 11快速constexpr整数幂

Question

在这里击败死马.在C中执行整数幂的典型(和快速)方法是经典的:

int64_t ipow(int64_t base, int exp){
  int64_t result = 1;
  while(exp){
    if(exp & 1)
      result *= base;
    exp >>= 1;
    base *= base;
  }
  return result;
}

但是我需要一个编译时整数幂,所以我继续使用constexpr进行递归实现:

constexpr int64_t ipow_(int base, int exp){
  return exp > 1 ? ipow_(base, (exp>>1) + (exp&1)) * ipow_(base, exp>>1) : base;
}
constexpr int64_t ipow(int base, int exp){
  return exp < 1 ? 1 : ipow_(base, exp);
}

第二个函数只是以可预测的方式处理小于1的指数.exp<0在这种情况下,传递是一个错误.

递归版本慢4倍

我在[0,15]范围内生成10E6随机值基数和指数的向量,并在向量上计算两个算法的时间(在进行非定时运行以尝试去除任何缓存效果之后).没有优化,recursice方法的速度是循环的两倍.但是使用-O3(GCC)时,循环比recursice方法快4倍.

我向你们提出的问题是:任何人都可以提出一个更快的ipow()函数来处理指数和0的基数并且可以用作constexpr？

(免责声明:我不需要更快的ipow,我只是想看看这里的聪明人能想出什么).

Answer 1

一个好的优化编译器会将尾递归函数转换为与命令式代码一样快的运行.您可以通过泵送将此函数转换为尾递归.GCC 4.8.1编译了这个测试程序:

#include <cstdint>

constexpr int64_t ipow(int64_t base, int exp, int64_t result = 1) {
  return exp < 1 ? result : ipow(base*base, exp/2, (exp % 2) ? result*base : result);
}

int64_t foo(int64_t base, int exp) {
  return ipow(base, exp);
}

进入循环(请参阅gcc.godbolt.org):

foo(long, int):
    testl   %esi, %esi
    movl    $1, %eax
    jle .L4
.L3:
    movq    %rax, %rdx
    imulq   %rdi, %rdx
    testb   $1, %sil
    cmovne  %rdx, %rax
    imulq   %rdi, %rdi
    sarl    %esi
    jne .L3
    rep; ret
.L4:
    rep; ret

与你的while循环实现:

ipow(long, int):
    testl   %esi, %esi
    movl    $1, %eax
    je  .L4
.L3:
    movq    %rax, %rdx
    imulq   %rdi, %rdx
    testb   $1, %sil
    cmovne  %rdx, %rax
    imulq   %rdi, %rdi
    sarl    %esi
    jne .L3
    rep; ret
.L4:
    rep; ret

对于我来说,相同的指令对我来说已经足够了.