This is been pondering me since university where I was an economics student in first year linear algebra. x^y = (x-1)*sumof(x^(y-1) + x^(y-2)...x^0)+1. I remember a business C programming class in which I tried that but could never get it to work. Is the pow function in C language for integers based on this recursion?
closed as off topic by Anton Geraschenko Oct 21 '09 at 20:07
Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.
There is no
FWIW, the actual implementation of the floating-point
When people implement integer exponentiation carefully, they usually use a repeated-squaring algorithm, which requires $O(log n)$ multiplications to raise x to the nth power (the complexity of each multiplication is a separate issue if you're not working with fixed-size integers). Knuth has an interesting discussion of integer exponentiation -- in particular, there is no known algorithm other than brute-force search that finds the optimal sequence of multiplications for raising an input to a known power.
Also, why is this question tagged
Short version, no. pow() is a finicky beast, if you understand floating point numbers. pow() is stable for small numbers, up until its return value is 2^53. Beyond that, and you not only suffer floating point error, but for integer computations you also don't gain speed.