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

3
Contributors
3
Replies
4
Views
8 Years
Discussion Span
Last Post by joshuabraham

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.

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.

Edited by nezachem: n/a

thanks for the info guys

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.