c ++ 11 fast constexpr integer powers [英] c++11 fast constexpr integer powers

问题描述

在这里击败死马。在C中执行整数幂的一种典型（和快速）方法是经典：

Beating the dead horse here. A typical (and fast) way of doing integer powers in C is this classic:

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：

However I needed a compile time integer power so I went ahead and made a recursive implementation using 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 是一个错误。

The second function is only to handle exponents less than 1 in a predictable way. Passing exp<0 is an error in this case.

我生成一个10E6随机值基数和指数的矢量，范围[0,15]和时间两个算法上的矢量（做非定时运行后，尝试删除任何缓存效果）。没有优化，递归方法的速度是循环的两倍。但是使用-O3（GCC），循环比递归方法快4倍。

I generate a vector of 10E6 random valued bases and exponents in the range [0,15] and time both algorithms on the vector (after doing a non-timed run to try to remove any caching effects). Without optimization the recursice method is twice as fast as the loop. But with -O3 (GCC) the loop is 4 times faster than the recursice method.

我的问题是这样的：可以任何人想出一个更快的ipow（）函数处理指数和基数为0，可以用作 constexpr ？

My question to you guys is this: Can any one come up with a faster ipow() function that handles exponent and bases of 0 and can be used as a constexpr?

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

(Disclaimer: I don't need a faster ipow, I'm just interested to see what the smart people here can come up with).

推荐答案

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

A good optimizing compiler will transform tail-recursive functions to run as fast as imperative code. You can transform this function to be tail recursive with pumping. GCC 4.8.1 compiles this test program:

#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

vs。 您的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

指令相同对我来说足够好了。

Instruction-by-instruction identical is good enough for me.

这篇关于c ++ 11 fast constexpr integer powers的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！