8
$\begingroup$

How do I compute $\text{(irrational)}^{\text{(irrational)}}$ up to a required number of decimals say m, in the fastest way ? (one way is of course compute both the irrational numbers to a precision much larger than m and then solve it... but you never know how much excess of m you will need to calculate the irrationals.. )

  • 0
    @Mitch - I need the fastest way to compute$a^b$upto any number of decimal places (just need an algo which would work on paper, don`t worry about floating point numbers, precision, etc.).2011-05-19

4 Answers 4

3

This is a further development on the ideas of Doug Spoonwood and phv3773.

Exponentiation $a^b$ is a continuous function, in both arguments, so we can use "interval methods" to calculate a number to any desired precision. Now I'm guessing you are only interested in real numbers, so I guess I can assume $a>0$, and since $a^{-b}=1/a^b=(1/a)^b$, we can also restrict our attention to $a>1$ and $b>0$. For fixed $b>0$, $a^b$ (the power function) is a strictly increasing function for $a\in(0,\infty)$, and for fixed $a>1$, $a^b$ (an exponential function) is strictly increasing for $b\in\Bbb R$.

Now suppose $a\in[a_-,a_+]$ and $b\in[b_-,b_+]$. In your application this would correspond to having calculated the irrationals $a$ and $b$ to some precision, and $a_-,a_+$ are your rational upper and lower bounds on the number you have calculated. (For example, if I calculate $a=\pi\approx3.14$ to that many digits of precision, rounded correctly, then $a\in[a_-,a_+]=[3.135,3.145]$.) Because $a^b$ is increasing in both arguments in the region of discussion, I know $a_-^{b_-}\le a_-^b\le a^b\le a_+^b\le a_+^{b_+}$ and hence $a^b\in[a_-^{b_-},a_+^{b_+}]$. This is Doug's "interval exponentiation" (suitably simplified for the case when $a>1$ and $b>0$).

These represent pessimistic bounds on the number being calculated, but they give a guarantee that the number you want is actually in that range.


A natural second question related to this process is which $a_-,a_+,b_-,b_+$ to choose. If you have an effective method for calculating $a$ and $b$ to whatever precision you need, then that means you can demand $a_+-a_-\le\delta$ and $b_+-b_-\le\delta'$ with your choice of $\delta,\delta'$. Our true goal is to get the range of our interval within some $\epsilon$, which is to say $a_+^{b_+}-a_-^{b_-}\le\epsilon$. A good estimate of what $\delta,\delta'$ to choose can be given by taking the partial derivatives of $a^b$ at the point of approximation:

$(a+\alpha)^{b+\beta}\approx a^b+\alpha\frac\partial{\partial a}a^b+\beta\frac\partial{\partial b}a^b=a^b(1+\alpha \frac ba+\beta\log a)$

(where $|\alpha|\le\delta/2$ and $|\beta|\le\delta'/2$). For good approximations, we want these two error terms to be comparable to one another. Thus we want $\frac{\delta a}b\approx\frac{\delta'}{\log a}\approx\frac\epsilon2a^b$. (I realize that this requires the computation of $a^b$, but this is just an estimate and need not be very accurate. The true test is when you calculate $a_+^{b_+}$ and $a_-^{b_-}$ and find that the difference is within your error bounds. If it isn't, just cut $\delta,\delta'$ in half until it is.)

1

As to the number of decimals m, I think that it should be possible to create an interval between upper and lower approximations using rational numbers. You can then examine how the interval between upper and lower decreases with more digits in the rational approximations.

  • 0
    That is what my question is .. when you don't know exactly what your (irrational) numbers are, how to find irr^irr.2011-05-25
1

This might work something like phv3773's idea, this probably works far too slowly for what you want, but maybe it's a decent idea. First as an example, consider calculating the product of two irrationals. We might use lower and upper approximations here. If we use lower approximations $l_1, l_2$, and upper approximations $u_1, u_2$ to irrationals $1$ and $2$, we have $[l_1, u_1]*[l_2, u_2]=[\min\{l_1l_2, l_1u_2, u_1l_2, u_1u_2\},\max\{l_1l_2, l_1u_2, u_1l_2, u_1u_2\}]$ where $*$ denotes interval number multiplication. We have $\max\{l_1l_2, l_1u_2, u_1l_2, u_1u_2\} - \min\{l_1l_2, l_1u_2, u_1l_2, u_1u_2\}\le n$ for some nonnegative $n$. Now $1$ decimal place corresponds to $n\le.1$, $2$ decimal places to $n\le.01$, and so on. So, for $k$ decimal place precision we just need to find $l_1, l_2, u_1, u_2$ such that $n$ is less than or equal to $10^{-k}$. You don't need to know what the irrationals are exactly, you just need to know that the irrationals lie between some rational numbers.

Now, interval exponentiation, like other interval arithmetic operations, if we can do such (if it "exists"), will yield an interval of numbers $[a, b]$. So, for $k$ decimal place precision we just need $n=b-a$ less than or equal to $10^{-k}$.

Unfortunately, I don't know how to do interval exponentiation. So, maybe it comes as a better idea to figure out how it works on the reals before trying this approach.

  • 0
    Needs more LaTeX. (I tried editing it, but I don't really know how it works.)2012-08-20
0

As others have suggested, I would use $a^b=\exp(b \log a)$. In this case, there is nothing special about $a,b$ being irrational. If $b$ is rational, we are probably in for irrationals because the denominator represents a root. To know the accuracy, we need to estimate how accurate each step has to be. We can take derivatives to assess this. First we need $a,b$ to be known well enough. We have $\Delta (a^b) \approx \frac {\partial (a^b)}{\partial b} \Delta a=a^b \log a \Delta b$, or the relative error in $a^b$ is a factor $\log a$ larger than the relative error in $b$. If $a$ is not too large, an extra decimal place or two will be enough. Similarly for errors in $a$, $\Delta (a^b) \approx \frac {\partial (a^b)}{\partial a} \Delta a=b\cdot a^{(b-1)} \log a \Delta a$ so if $b$ and $a$ are about the same magnitude, again a couple places will be enough. You can do similarly for errors in your $\log$ and $\exp$ functions and the multiply.