Expert: John OConnor - 3/15/2010

Question
QUESTION: Greetings sir,
I was told that the power function for real numbers takes
O(1) time.It seems it should be so if it uses logarithms .Is
this true?And where can I get more info on this and stuff like
the range in which certain power algorithms are fastest/most accurate in ,and how they work in general?Thank you.

ANSWER: Hey there,

So, sounds like an algorithms question.  Really, it 100% depends on the implementation of the algorithm used to implement the power function itself.

When you speak of the power function for real numbers, I'm assuming you're referring to the CMATH (math.h) C Standard library implementation of the power function (pow).  This is what most higher level languages (python, C++, ruby, php, etc) use for their implementation of the power function.

I would start with a google search of "power function implementation" and see what crops up.  You can also search the KRUGLE search engine for some examples.  A google search for Power Function Algorithms also turns up some interesting finds.

The CMATH (math.h) version of pow is implemented differently depending on the architecture of your machine.  For some architectures, it implements a lookup table of logarithms (like you mentioned), and as such can provide O(1) time complexity since it's just a lookup.  This also means that, outside of this range, you cannot use that method.

For numbers outside of this, they most likely use a recursive multiplication algorithm (which can be pretty fast, depending on your architecture).  If you're using a stack-based processor, and your ISA supports it, POW is done entirely using processor specific instructions, which allows it to use it's pipelines and branch prediction to effectively calculate (real) powers very quickly. For Floating point powers, however, all bets are off.  Unless you're using a GPGPU, these take a lot of time.

I couldn't find a specific resource for power functions, but I would look through the ISA documentation or check the Linux kernel source code for the C implementation of the power function used in cmath.

---------- FOLLOW-UP ----------

QUESTION: Thanks for replying.When you spoke about the implementation that uses
lookup tables you mentioned a range.What is this range?Where can i get
more info on this?Thanks.

Answer
Sure.

So, the range depends entirely on the architecture.  If a chip implemented a lookup table, it would most likely be done up to the longest real primitive type (probably a long int) which also depends on the architecture (ie: a 32 bit x86 processor could use 4-bytes for its long int, whereas the 64-bit could use 8).  So, if you're using 4 bytes for a long int, then the largest lookup table you would implement would be 2^32, which is 4294967296.

HOWEVER, the chips themselves do not use lookup tables usually when implementing those functions (a lookup table would be used for a purely software solution, and entirely up to the implementation of your standard C library). Processors use numerical analysis techniques on the hardware themselves to calculate these (Approximating Taylor Series expansions, etc).

Check out the following link for more information about this concept in general.
http://stackoverflow.com/questions/2284860/how-does-c-compute-sin-and-other-math

If you're curious to see some specific code for a specific architecture, check out the following link:

http://cvs.savannah.gnu.org/viewvc/libc/sysdeps/i386/fpu/?root=libc

which contains the fpu source code used for many of the cmath calculations.  Be forewarned, it's in the assembly language specific to that processor (so the above is the Intel x86 arhictecture, compatible with the 386 Instruction Set Architecture (ISA), and with a Floating Point Unit (FPU)).

Hope this gives you more to check out...