time complexity of pow and equation solver

[joshuabraham]

hi everyone.i'm just wondering what the time complexity of the fastest pow function you know of,in the general case i.e when it's parameters are real numbers .Heard someone say it is virtually constant.Also whats the likely complexity of the most efficient algorithm that finds the derivative of a function of order n,at a given point.Thanks for every reply

[mrnutty]

For powers of two all you have to do is use the shifter, which is very
fast and is probably almost constants for the usual powers of 2.

For ordinary numbers, its probably the O(exp), where exp is the
exponent. For example, base^exp, to calculate that it would probably take exp times to multiply base to get the answer.

The above is not definite, its just a hunch.

[nezachem]

For ordinary numbers, its probably the O(exp), where exp is the
exponent. For example, base^exp, to calculate that it would probably take exp times to multiply base to get the answer.

It is at worst O(log(exp)). For example:
^2: x*x
^4: x2 = x*x, x^4 = x2 * x2
^8: x2 = x*x, x4 = x2*x2, x^8 = x4 * x4
etc.

In the general case, the multiplication schedule is a bit hairy (and finding the best one is probably NP-hard).

PS: this is assuming that a multiplication itself has a constant complexity, which is definitely wrong.

[joshuabraham]

thanks for the info guys