Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Fast positive integer power function

Name: Anonymous 2012-04-15 6:00

I'm trying to figure out how to compute an integer power of a double efficiently with as little overhead as possible (trying to avoid loops and recursion to minimize the amount of calls and jumps). Calculation speed is the priority.
So far I got this trivial piece of code:

double f(double a,char b){
if(b==2)return a*a;
if(b==3)return a*a*a;
if(b==4)return a*a*a*a;
if(b==5)return a*a*a*a*a;
if(b==6)return a*a*a*a*a*a;
if(b==7)return a*a*a*a*a*a*a;
if(b==8)return a*a*a*a*a*a*a*a;
if(b==9)return a*a*a*a*a*a*a*a*a;
        return a*a*a*a*a*a*a*a*a*a;
}


...which of course assumes the exponent is at most 10. The code can easily be expanded if higher exponents are needed.
I'm thinking this is probably optimal, but I know you /prog/riders have some magic tricks up your sleeve, so hit me with them.

Name: Anonymous 2012-04-15 14:57

>>26
And what happens if the compiler does TCO on the non tail call optimized version (you know, like a modern version of GCC would do with optimization)?

Well, seeing how both posters were comparing >>1 to a non tail call optimized version of the program, I can only trust that they know for a fact that compiler C_i did not produce a tail call optimized version of implementation NTC_i, for platform P_i. We could account for unreliability there by assigning a probability to the event of NTC_i being tail call optimized.

And what happens if the compiler creates separate functions for each branch in >>1's function and chooses the corresponding function to call at compile time so the whole procedure becomes branch-less (you know, like a modern version of GCC would do with optimization)?

Then that would be a pretty bitchen compiler. Inlining and constant folding ma nigga. But even then that is still describable using this model. Because the compiler and source file are both present in the time function, the compiler is free to generate whatever binary for the platform it wants. The time function only measures the time taken for the generated binary.

Your first inequality fails as long as the second optimization is performed,

maybe, maybe not. You never know.

the second of course can never fail since you haven't given any bounds to your epsilon (I presume it is at least greater than zero), which also renders the whole inequality totally worthless since it teaches us nothing new beyond that an absolute value is less than some other value.

There exists a reasonably small epsilon such that the sentence holds true. The value of epsilon depends on >>5-kun's accuracy in perception of time, and is probably something like a tenth of a second, or maybe a half of a second. Come to think of it, it's probably linearly related to the amount of time ey waits, so it might be better to describe it like that in general.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List