How do computers work out powers?

[stefano5]

I'm deep in debate with a collegue of mine as to how computers work out powers. i.e what is the working behind the Math.Pow() function?

I seem to remember from school there being a method involving natural logarithms. Is this correct? And what is the working?

Thanks

Stefano

[stefano5]

Ok so I think I've managed to jog my memory....

x^n = e^(n*ln(x))

since both e^x and ln(x) can be calculated using series this should work right?

[jemidiah]

You could use that. There are also series for x^n.

However, computers often use Exponentiation by Squaring. One would compute 15^73 by taking [ignoring order of operations so I don't have to write a zillion parentheses]

15^2^2^2*15^2^2^2*15 = 15^[(2*2*2+1)*2*2*2+1] = 15^[9*8+1] = 15^73.

This reduces exponentiation to a few multiplications. I'm pretty sure you could generalize this without too much hassle to floating point numbers, taking the number of bits of precision multiplications per exponentiation.

[stefano5]

That's very elegant, I guess it must be easier for computers to use any of the Exponentiation by Squaring methods if x and n are both Integer values as series often result in floating point numbers, and we all know what that means

I'd be interested to see a Exponentiation by Squaring method which could be applied to non integer values.

[jemidiah]

I believe the above method works fine if x is a floating point number, just using floating point multiplications at each step. You would want to make sure you don't under or overflow in intermediate steps.

If n is a floating point number... I have no idea how to extend it.