Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I can calculate the result of $x^y$ provided that $y \in\mathbb{N}, x \neq 0$ using a simple recursive function:

$$ f(x,y) = \begin {cases} 1 & y = 0 \\ (x)f(x, y-1) & y > 0 \end {cases} $$

or, perhaps more simply stated, by multiplying $x$ by itself $y$ times.

Unfortunately, I am unsure how I can numerically approximate $x^y$ for non-integer rationals.

For example, what method can I use to approximate 33.3?

If possible, I would like to be able to do this using only elementary arithmetic operations, i.e. addition, subtraction, multiplication, and division.

share|improve this question
2  
If the exponent is rational, you'll have to use an iterative method like Newton-Raphson. For more general exponents, you'll definitely need $\exp$ and $\ln$. –  J. M. Sep 6 '11 at 5:01
    
@J.M. For my purposes, I can assume that the exponent is rational. –  Peter Olson Sep 6 '11 at 5:02
    
For the specific case of $3^{\frac{33}{10}}$, you can use Newton-Raphson for $\sqrt[10]{3}$ and then use your method to exponentiate that 33 times. –  J. M. Sep 6 '11 at 5:03
1  
If you can also take square roots, you can expand the exponent as a binary number and repeatedly take square roots to get $x^{1/2^k}$ and multiply when the bit in the exponent is a 1. There is a technique for taking $x^{1/2}$ when x is close to 1 that preserves accuracy - write $x = 1+y$ so $x^{1/2} \approx 1+y/2$. I think I saw this in a book by Henrici many years ago. –  marty cohen Sep 6 '11 at 5:31
2  
Are you asking how $x^y$ is defined for rational $y=n/m$? It is as $(x^{1/m})^n$, where $x^{1/m}$ is defined as the $m$th root of $x$, that is, the unique number $t>0$ such that $t^m=x$. To approximate $t=x^{1/m}$ you can, as said, use Newton-Raphson to find the root to the function $f(t)=t^m-x$. Arbitrary real exponents can be treated as limits of rational exponents. For example, $x^{3.14159}$ will approximate $x^\pi$. –  Samuel Sep 6 '11 at 11:50

2 Answers 2

I'll consider the problem of computing $x^\frac1{q}, \; q > 0$; as I've already mentioned in the comments, one can decompose any positive rational number as $m+\dfrac{p}{q}$, where $m,p$ are nonnegative integers, $q$ is a positive integer, and $p < q$. Thus for computing $x^{m+\frac{p}{q}}$, one could use binary exponentiation on $x^m$ and $\left(x^\frac1{q}\right)^p$ and multiply the results accordingly.

A.N. Khovanskiĭ, in his book on continued fractions, displays a continued fraction representation for the binomial function:

$$(1+z)^\alpha=1+\cfrac{2\alpha z}{2+(1-\alpha)z-\cfrac{(1-\alpha^2)z^2}{3(z+2)-\cfrac{(4-\alpha^2)z^2}{5(z+2)-\cfrac{(9-\alpha^2)z^2}{7(z+2)-\cdots}}}}$$

which converges for $|\arg(z+1)| < \pi$.

Letting $z=x-1$ and $\alpha=\dfrac1{q}$, one can then evaluate this continued fraction (with, say, Lentz-Thompson-Barnett) to generate a "seed" that can be subsequently polished with Newton-Raphson, Halley, or any of a number of iterations with high-order convergence. You'll have to experiment with how accurate a seed you need to start up the iteration, by picking a not-too-small tolerance when evaluating the continued fraction.


Here's some Mathematica code demonstrating what I've been saying earlier, for computing $\sqrt[3]{55}$:

With[{q = 3, t = 55, prec = 30},
 y = N[2 + (1 - 1/q) (t - 1), prec];
 c = y; d = 0; k = 1;
 While[True,
  u = (k^2 - q^-2) (t - 1)^2; v = (2 k + 1) (t + 1);
  c = v - u/c; d = 1/(v - u d);
  h = c*d; y *= h;
  If[Abs[h - 1] <= 10^-4, Break[]];
  k++];
 FixedPoint[
  Function[x, x ((1 + q) t - x^q (1 - q))/(x^q (1 + q) - (1 - q) t)], 
  1 + 2 (t - 1)/q/y]]

Here, I've arbitrarily chosen to stop when the continued fraction has already converged to $\approx 4$ digits, and then polished the result with Halley's method. The result here is good to $\approx 28$ digits. Again, you'll have to experiment on the accuracy versus expense of evaluating the "seed", as well as picking the appropriate iteration method for polishing the seed.

share|improve this answer

There is a concept using "fractional continued fractions" invented by D. Gomez Morin , see http://domingogomez.web.officelive.com/gcf.aspx . I've fiddled some time ago with this and think I recall right, that you can find roots of m'th order and that the apparent complexitiy of the "fractional continued fraction" reduces to rational fractions recursively applied. I'll try next days to recover the algorithm again, but perhaps the link to the page is already helpful.
Just found the hint of D.G.Morin to an excerpt of Steven Finch's book "mathematical constants", where S.F. mentions also this method in a much compacted way (see page 4 of http://assets.cambridge.org/052181/8052/sample/0521818052ws.pdf ).



[update] For the first broken link there is an entry in the wayback internet archive: Domingo Fomez Morin [/update]

share|improve this answer
    
Two of your links are dead. –  Arlen Sep 14 '12 at 19:39
    
Thanks @Arlen! Too bad - I don't know where D.G.Morin is now... He moved several times and I cannot track down his path, sorry... –  Gottfried Helms Sep 14 '12 at 21:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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