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.. )
Irrational$^\text{Irrational}$
-
5I think most calculators would calc $a^b = 2^{b\log_2 a}$, since they have fast and reliable procedures for calculating $2^{.}$ and $\log_2$. – 2011-01-22
-
2On a sidenote, if you're working with really *huge* numbers and you're still using the standard multiplication, you might want to check out this site: http://en.wikipedia.org/wiki/Multiplication_algorithm E.g. check the section on karatsuba – 2011-01-22
-
0Regarding the a^b=2^blog2(a) method, upto what precision will you express log2(a) [assuming I want a^b upto m decimals]?? because this is again an irrational term in the power... – 2011-01-22
-
0This may help you approximate the error term for $\epsilon$ small: $2^{a+\epsilon} = 2^\epsilon \cdot 2^a \approx (1 + \epsilon\ln 2/2) \cdot 2^a \approx 2^a + 0.69 \epsilon 2^a$. Actually I think physicists are good at this kind of stuff, because it can be treated as some sort of measurement uncertainty. Maybe you'll find some good reference in that direction. – 2011-01-22
-
0@Guanidene, Some irrational numbers are not computable. So you cannot compute this in general. If $a$ and $b$ are computable (whether irrational or not) you can compute $a^b$. – 2011-05-12
-
0@Guanidene, so the point is, you need to fix a computable set of numbers if you want an algorithm. – 2011-05-12
-
0@Guanidene, If this question is actually about how many digits of $a$ and $b$ are needed to compute $n$ digits of $a^b$ you should improve the question a bit to make that clearer. – 2011-05-12
-
0One possible way is to use $a^b= e^{b \ln a}$ and use the Taylor series for the exponential, since it converges pretty fast. Of course this approach has a downside, namely that you also need to estimate $b \ln a$... – 2011-05-12
-
0@quanta - suppose i wish to calculate pi^e. Now please tell me how will you proceed. – 2011-05-16
-
0Well, the way you proceed depends on how good your estimate needs to be.... – 2011-05-16
-
0Do you mean "What is the fastest algorithm to compute the $n$th digit of $a^b$ over floating point?" or "What is the precision range for $a^b = e^{b \ln a}$ computed with Taylor series?" or something else? – 2011-05-16
-
0@user9176 - Suppose I wish to find upto 100 decimals exact. Please suggest an algo for the same – 2011-05-19
-
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
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.)
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.
-
0Please elaborate your point – 2011-05-19
-
0For example, one way to calculate the digits of pi is to choose a series that converges to pi with a know error term. By examining the error term, you can tell how many digits won't change adding additional terms. I had the thought that if you had series that converge to your irrationals from above and from below, you could do the same thing with your expression, but it would be complicated, and different for any two irrational numbers. A practical question is how do you know what your irrational numbers are? – 2011-05-23
-
0That is what my question is .. when you don't know exactly what your (irrational) numbers are, how to find irr^irr. – 2011-05-25
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.
-
0Needs more LaTeX. (I tried editing it, but I don't really know how it works.) – 2012-08-20
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.