Calculating a power in Java without power function in O(log) time

Question

I had this question sent to me by a potential employer, and my answer apparently wasn't up to snuff. Can anyone help?

Implement a function that calculates power(A,B), where A and B are positive integers, assuming there is no power function in your programming language. Also, assume A and B are of Big Integer type so that there is no arithmetic overflow. What is the computational complexity of your function? Can you come up with a solution that runs with log(B) time?

Answer 1

I'll just give you a hint. Suppose B is 45. Then A⁴⁵ = A³² * A⁸ * A⁴ * A¹. You can compute A¹, A², A⁴, A⁸, etc. by starting with A and squaring it in every iteration.