Question

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?

Answer 1

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?

Answer 2

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.