Bruno wrote:
The gain is in going from O(N) template instantiations to O(log N), which helps at compile-time.
Even at runtime I don't really agree since the solution proposed here was the one I had originally proposed. And when Joaquin corrected it by proposing something that better optimizes the number of multiplications, my tests shew that the gain at runtime was real and that my compiler didn't do that by itself. This being said, I should redo my tests to be sure I didn't miss anything.
Anyway, I think all this is a matter of compiler and the best way is to take compiler's hand to force it to write the right code, even for those compilers that would have been able to do it by themselves.
Luke, which compiler to you use?
gcc 4.3.2 -O2 I didn't mean we should use the O(N) algorithm I tested, I meant we shouldn't obsess about improving the O(log N) algorithm already checked into the trunk. Whether x^32 results in 8, 6, or 4 template instantiations probably doesn't matter as much as clarity or concise code. People should be able to use it as an example for how to write their own generic functions. Yes, it is better to force the compiler's hand than trust it. I certainly won't trust the compiler to unroll a loop for me. For built in multiply operations the compiler can optimize the expression tree you give it, but for user defined multiply operators on user defined types it will give you N multiplies if that is what you ask for and it. I think we should get the algorithm right, for sure. Have you ever seen the compiler fail to inline pow? Thanks, Luke