Calculation of large roots: bigdecimal / java

Question

I tried using the standard iterative algorithm to calculate the nth root.

For example, (111 ^ 123) ^ (1/123).

The standard algorithm calculates the high power 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. Therefore, obviously, they use some clever ideas. Any hints of this?

Answer 1

However, I noticed that the same use of double takes less than milliseconds. Therefore, obviously, they use some clever ideas.

Not really. double just has limited accuracy, so it basically needs to calculate the most significant 52 bits of the result and can skip the rest of the calculation. And, of course, using this in hardware also helps.

Answer 2

Try using binary exponentiation. I mean:

111 * 111 = 111 ^ 2, now you know what 111 ^ 2 is, now you can 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.