Algorithm to calculate root (or power) in computer

[hkBattousai]

I need an algorithm to calculate n^th root or power of any given real number. "n" can be either integer or fractional, and is real.

I found http://en.wikipedia.org/wiki/N-th_root_algorithm" , but it requires to calculate power in it, therefore I can't use it.

Newton's method:
$x_{k+1} = \frac{1}{n} \left[{(n-1)x_k +\frac{A}{x_k^{n-1}}}\right]$


So, I need another algorithm.
Can you please suggest one?

 

[fedaykin]

If you are writing it in c++, you can include math or math.h depending on your compiler and use the pow() function. Some other languages have similar math libraries.

I suspect your looking for something lower level without functions other than base instructions. This may be of interest to you: http://www.syntax-example.com/Code/calculate-powerab-ie-ab-1670.aspx

 

[hkBattousai]

If you are writing it in c++, you can include math or math.h depending on your compiler and use the pow() function. Some other languages have similar math libraries.

I suspect your looking for something lower level without functions other than base instructions. This may be of interest to you: http://www.syntax-example.com/Code/calculate-powerab-ie-ab-1670.aspx

Yes, I will write in C++ without using any external libraries like pow() or sqrt() of math.h. Your example code is in Assembly language. Rather than a pseudo code, I'm looking for a mathematical method for this calculation.

 

[disregardthat]

Yes, I will write in C++ without using any external libraries like pow() or sqrt() of math.h. Your example code is in Assembly language. Rather than a pseudo code, I'm looking for a mathematical method for this calculation.

Can't you just implement pow(x,n) ?

 

[hkBattousai]

Can't you just implement pow(x,n) ?

Actually, I'm more concerned about the mathematical aspect of the problem more than computer programming. I want to implement my own power() method.

 

[disregardthat]

I want to implement my own power() method.

That's what I meant. for example to define x^k = pow(x,k) (excuse my java syntax)

double a = x;
for(int i = 0; i < k; i++) {
a = x * a;
}
return a;

 

[jasonRF]

Recall:

$$x^\alpha = e^{\ln x^\alpha} = e^{\alpha \ln x}$$

now you just need an exponential and a log. Special cases like square roots can have nice iterations that converge quick (learned in real analysis of all places!), but I'm guessing this is the route you must take for general roots/powers.

Note that even though $$x$$ and $$\alpha$$ are real, when $$x<0$$ the result is complex. Are you including this case?

Good luck,

jason

edit: just realized that your question is for for the less general case of either $$\alpha$$ or $$1/\alpha$$ an integer. Jarle has the answer for the integer case. Once you have that, the 1/integer case can be done via the algorithm in your wikipedia page. Sorry if my generalization caused any confusion!