c++11快速常数整数幂
c++11快速常数整数幂
提问于 2013-07-18 09:32:08
在这里打败死马。在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，我只是想看看这里的聪明人能想出些什么)。
回答 2
Stack Overflow用户
回答已采纳
发布于 2013-07-18 16:01:24
一个好的优化编译器将转换尾递归函数以与命令式代码一样快地运行。您可以通过抽水将此函数转换为尾递归。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完全相同的指令对我来说已经足够了。
Stack Overflow用户
发布于 2013-07-18 09:45:16
这似乎是一个标准的问题，与C++中的and程序和模板编程有关。由于编译时间的限制，如果在运行时执行，将比正常版本慢。但是重载不允许选择正确的版本。标准化委员会正在处理这个问题。例如，请参阅下面的工作文档http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3583.pdf
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/17719674
复制相关文章
相似问题
腾讯云开发者
