Divide and conquer method to compute roots - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-05-24T23:35:45Z http://mathoverflow.net/feeds/question/21147 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/21147/divide-and-conquer-method-to-compute-roots Divide and conquer method to compute roots hellsoul153 2010-04-12T19:27:57Z 2010-04-12T22:56:15Z <p>Hello,</p> <p>Knowing that we can use Divide-and-Conquer algorithm to compute large exponents, for exemple 2 exp 100 = 2 exp(50) * 2 exp(50), which is quite more efficient, is this method efficient using roots ? For exemple 2 exp (1/100) = (2 exp(1/50)) exp(1/50) ?</p> <p>In other words, I'm wondering if (n exp(1/x)) is more efficient to (n exp(1/y)) for x &lt; y and where x and y are integers.</p> <p>There seems to be a method using Dichotomic search and Divide-and-conquer method to know if n exp(1/i) is an Integer. See Dixon's factorisation method : <a href="http://en.wikipedia.org/wiki/Dixon" rel="nofollow">http://en.wikipedia.org/wiki/Dixon</a>'s_factorization_method</p> http://mathoverflow.net/questions/21147/divide-and-conquer-method-to-compute-roots/21151#21151 Answer by REDace0 for Divide and conquer method to compute roots REDace0 2010-04-12T20:13:55Z 2010-04-12T22:56:15Z <p>You can approximate the real \$n\$th root of \$k\$ as the real solution to \$x^n-k=0\$. Since this is a monotone function on \$[0,k]\$, you can use a bisection method to approximate it to an arbitrary degree. So finding a root amounts to iterated computation of \$x^n\$. So if divide-and-conquer makes computing \$x^n\$ more efficient so it should make computing \$k^{1/n}\$ more efficient.</p> <p>There are probably much better methods. I'm no expert in numerical approximation.</p>