10

在这里打死马。在 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 个随机值基数和指数的向量，并在向量上对两种算法进行计时（在进行非定时运行以尝试消除任何缓存效果之后）。如果不进行优化，递归方法的速度是循环的两倍。但是使用 -O3 (GCC)，循环比递归方法快 4 倍。

我对你们的问题是：任何人都可以想出一个更快的 ipow() 函数来处理 0 的指数和底数并且可以用作constexpr?

（免责声明：我不需要更快的 ipow，我只是想看看这里的聪明人能想出什么）。

4

2 回答 2

15

一个好的优化编译器会将尾递归函数转换为与命令式代码一样快的运行。您可以将此函数转换为带有泵送的尾递归。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

逐条指令相同的指令对我来说已经足够了。

于 2013-07-18T16:01:24.333 回答
3

这似乎是 C++ 中 constexpr 和模板编程的标准问题。由于编译时间限制，如果在运行时执行，constexpr 版本比普通版本慢。但是重载不允许选择正确的版本。标准化委员会正在研究这个问题。参见例如以下工作文件http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3583.pdf

于 2013-07-18T09:45:16.327 回答