MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
-1

Hello,

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) ?

In other words, I'm wondering if (n exp(1/x)) is more efficient to (n exp(1/y)) for x < y and where x and y are integers.

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 : http://en.wikipedia.org/wiki/Dixon's_factorization_method

flag
1 
 I find it hard to make sense of what you are asking, but maybe what you're after is CORDIC. en.wikipedia.org/wiki/CORDIC That's more of a stackoverflow thing than a mathoverflow thing. – Dan Piponi Apr 12 2010 at 19:42
It seems to me that your example is $2^{1/100}=(2^{1/50})^{1/50}$, which is not right. You might wish to do it as either $2^{1/100}=(2^{1/2})^{1/50}$ or $2^{1/100}=(2^{1/50})^{1/2}$. – Harald Hanche-Olsen Apr 12 2010 at 21:15
This question makes no sense: 1. the example is not of divide and conquer form, 2. n*exp(1/i) can't be an integer for integer n, i (as is implied). 3. I read through the wiki link - what does this have to do with anything? (@sigfpe: I would like to point out that even though computation is almost virtually banned from MO, it is not so for math. CORDIC is math) – Dror Speiser Apr 12 2010 at 22:53
1 
 @Dror I wasn't thinking so much of what's banned but where you might get more responses from people with implementation experience. – Dan Piponi Apr 12 2010 at 23:12
1 
 On a new reading of this question, I think it's likely that my guess at what the question was all about was wrong – so I deleted my answer. Furthermore, due to the extreme vagueness of the question, I am voting to close. – Harald Hanche-Olsen Apr 13 2010 at 2:42
show 1 more comment

closed as off topic by Harry Gindi, François G. Dorais♦, Harald Hanche-Olsen, S. Carnahan♦, Steve Huntsman Apr 13 2010 at 3:53

1 Answer

0

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.

There are probably much better methods. I'm no expert in numerical approximation.

link|flag

Not the answer you're looking for? Browse other questions tagged or ask your own question.