C ++ 11 fast constexpr integer degrees

Question

Beating a dead horse here. A typical (and quick) way to do integer degrees 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; } 

However, it took me an integer compilation time, so I went ahead and did 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); } 

The second function is designed to process indicators less than 1 in a predictable way. Passing exp<0 is an error in this case.

Recursive version 4 times slower

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

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

(Disclaimer: I don't need a fast ipow, I'm just interested to see what smart people have to offer).

Answer 1

A good optimizing compiler converts tail-recursive functions to work as fast as peremptory code. You can transform this function so that it is 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); } 

in a loop ( See this at 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 

against. your while loop implementation :

 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 

Identification by instructions is good enough for me.

Answer 2

This seems to be a standard problem with programming constexpr and templates in C ++. Due to compilation time limitations, the constexpr version is slower than the regular version if it is executed at run time. But overloading does not allow you to select the correct version. The standardization committee is working on this issue. See, for example, the following working document http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3583.pdf