How fast can all nth roots of an integer be computed? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-05-25T18:15:52Z https://cs.stackexchange.com/feeds/question/103962 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/103962 0 How fast can all nth roots of an integer be computed? Q.Q https://cs.stackexchange.com/users/100104 2019-02-06T22:14:00Z 2019-02-06T23:58:33Z <p>I mean that for every <span class="math-container">$i$</span> from 2 to <span class="math-container">$\lceil \log_2n\rceil$</span> I want to know <span class="math-container">$\lfloor \sqrt[i]{n}\rfloor$</span>. Could this be done faster than computing the roots one by one?</p> https://cs.stackexchange.com/questions/103962/-/103965#103965 1 Answer by gnasher729 for How fast can all nth roots of an integer be computed? gnasher729 https://cs.stackexchange.com/users/17408 2019-02-06T23:58:33Z 2019-02-06T23:58:33Z <p>Let's say n is very large, say around <span class="math-container">$2^{1000}$</span>. In theory, you can calculate the k-th root of n by calculating <span class="math-container">$2^{(\log n) / k}$</span>. Doing this for multiple k means you calculate <span class="math-container">$\log n$</span> only once, so you save some time here. </p> <p>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. </p> <p>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. </p> <p>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. </p> <p>(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. )</p>