How fast can all nth roots of an integer be computed?

I mean that for every $$i$$ from 2 to $$\lceil \log_2n\rceil$$ I want to know $$\lfloor \sqrt[i]{n}\rfloor$$. Could this be done faster than computing the roots one by one?

• What did you try? Are you able to come up with one different method? By the way, is there any significance about $\lceil\log_2 n\rceil$ here? Why not just an arbitrary integer $m\ge2$? – Apass.Jack Feb 6 at 22:56
• The significance of $\left\lceil \log_2 n \right\rceil$ is left as an exercise to the reader. – Pseudonym Feb 6 at 23:05
• @Appas.Jack Well I tried googling and thinking and didn't come up with anything. That number is significant because for all m above it the result will just be 1. – Q.Q Feb 7 at 0:07
• @Q.Q What is the range of $n$ you are interested in? Up to $2^{31}$? $2^{63}$? $2^{2^{10}}$? Really arbitrarily large? – Apass.Jack Feb 8 at 15:52
• @Apass.Jack of course arbitrarily large, otherwise the result could be computed in $O(1)$ – Q.Q Feb 8 at 20:36

1 Answer

Let's say n is very large, say around $$2^{1000}$$. In theory, you can calculate the k-th root of n by calculating $$2^{(\log n) / k}$$. Doing this for multiple k means you calculate $$\log n$$ only once, so you save some time here.

You will spend a large amount of time calculating say the first 50 roots because you need very high precision to calculate the root rounded down to the nearest integer. I can't see you saving any time by calculating multiple roots together.

The next roots are much easier to calculate. Then if k gets large, say 200, you will find that many roots rounded down are the same. Here you can make some savings by calculating for which range of integers k the k-th root of n will be between some integer r and r+1, and therefore the k-th root rounded down equals r. In this example there will be a few hundred k where the k-th root rounded down equals 2, for example.

But I think the first few roots (2nd, 3rd, 4th root) will take so much more time due to the high precision required, that the effort for the remaining roots will be much smaller. So I would say that you can save a little bit of time, but likely just a constant factor.

(Also, the effort may be bigger if the k-th root of n is very, very close to an integer, but that doesn't change the analysis. )