Divide and conquer method to compute roots [SOLVED]

Question

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.

Answer 1

As x,y are floating point numbers exp(1/x) might not be more efficient than exp(1/y) for all x<y.

But point of divide and conquer algorithms is that

if we have something like exp(1/x) we won't calculate it again i.e. we divide 2^N into two same problems of smaller size 2^(N/2) * 2^(N/2) and we calculate 2^(N/2) only once.

Similarly for exp(2/x) can be divided into exp(1/x)*exp(1/x) and we will have to calculate exp(1/x) only once. This should improve performance.

Also having smaller number in denominator should help.

So I think this should work fine.

Answer 2

I don't think that a divide and conquer method is used when you have non-integer exponentials. I would assume that a taylor polynomial is used to compute x^y as e^(y ln(x)). You can compute the integer part of y, using divide and conquer then multiply it by the real part. But it doesn't make sense to divide it in two otherwise. Also:

2 exp (1/100) = (2 exp(1/50)) exp(1/50)

This is not true.

(2 exp(1/50))exp(1/50) = 2 exp(1/50+1/50)= 2*exp(1/25) != 2 exp(1/100)

You would be doing:

2 exp(1/100)= 2*exp(1/200)* exp(1/200)