computing large roots : bigdecimal / java

Question

I tried to use the standard iterative algorithm to compute nth roots.

For instance (111^123)^(1/123).

The standard algorithm computes high powers of the base (in this case 111^123) which takes a lot of time. The algorithm is given here http://en.wikipedia.org/wiki/Nth_root_algorithm

However, I noticed that the same thing using double takes less than a millisecond. So obviously they use some smart ideas. Any hints on this?

Answer 1

Try using binary exponentiation. What I mean is do:

111 * 111 = 111^2, now you know what 111^2 is, you can now calculate 111^4 by doing (111^2) * (111^2). Here is the whole sequence (Note that this is probably not the most efficient way).

111 * 111 = 111^2
111^2 * 111^2 = 111^4
111^4 * 111^4 = 111^8
111^8 * 111^8 = 111^16
111^16 * 111^16 = 111^32
111^32 * 111^32 = 111^64
111^64 * 111^32 = 111^96
111^96 * 111^16 = 111^112
111^112 * 111^8 = 111^120
111^120 * 111^2 * 111^1 = 111^123.

Answer 2

However, I noticed that the same thing using double takes less than a millisecond. So obviously they use some smart ideas.

Not really. double simply has limited precision, so it basically only has to compute the most significant 52 bits of the result and can skip the rest of the calculation. And of course, having this implemented in hardware also helps.