问题描述
在这里击败死马。在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 是一个错误。
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);
}
加入循环():
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。 :
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的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!