# Is x^y a recursive algorythm [closed]

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 GeraschenkoOct 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.

As far as I can tell, this is a computer question. –  Anton Geraschenko Oct 21 '09 at 20:08

There is no pow function in the C language for integers. There is a pow defined in the standard header <math.h>, but it operates on floating-point data, not integers.

FWIW, the actual implementation of the floating-point pow function varies from platform to platform, but it does not typically use any sort of recursion. The implementation is often, but not always, based on the definition $x^y = \exp(y\log x)$ (though not necessarily using the base-e logarithm or exponential; 2 is a common choice).

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 linear-algebra?

-

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.

-