# Is there an algorithm that can tell whether the power of two rational numbers is rational?

It has been known since Pythagoras that 2^(1/2) is irrational. It is also obvious that 4^(1/2) is rational. There is also a fun proof that even the power of two irrational numbers can be rational.

Can you, in general, compute whether the power of two rational numbers is rational?

The reason I am asking, besides curiosity, is that the Fraction-type in Python always returns a float on exponentiation. If there is a quick way to tell if it could be accurately expressed as a fraction, the power function could conceivably only return floats when it has to.

EDIT: By popular demand, I changed 0.5 to 1/2 to make it clearer that it is a fraction and not a float.

-

## migrated from stackoverflow.comFeb 29 '12 at 18:41

This question came from our site for professional and enthusiast programmers.

'the power function could conceivably only return floats when it has to' What would the benefit of that be? – Marcin Feb 29 '12 at 17:11
Also, I assume you mean "is there an algorithm more efficient than evaluating the power expression, and testing if the result is rational?" – Marcin Feb 29 '12 at 17:13
Why the close votes? This isn't off-topic, it was clearly stated as relating to implementing fractions. I personally find it useful. – ninjagecko Feb 29 '12 at 17:39
@ninjagecko math.hmc.edu/funfacts/ffiles/30002.3-5.shtml – Gurgeh Feb 29 '12 at 17:42
@ninjagecko I am pleased that someone recognizes this as related to programming. Why have a (well used) math tag on stackoverflow if math related programming questions does not belong? – Gurgeh Feb 29 '12 at 20:16

There is no really easy way to test if the result of a ** b with a and b being rational numbers is rational. The easiest way is to decompose a into its prime factorisation

a = p_0 ** k_0 * p_1 ** k_1 ... p_r ** k_r

with p_i being prime numbers and k_i being (signed) integers. The result of a ** b is rational if all k_i * b are integers again.

-
An arbitrary rational a=x/y doesn't have a prime factorization, but it would be sufficient to test that both x**b and y**b are rational using this method. – chepner Feb 29 '12 at 17:16
This begs the question, how do you decompose a into its prime factorisation? – Gurgeh Feb 29 '12 at 17:17
@chepner: An arbitrary rational does have a unique prime factorisation. The exponents aren't necessarily positive. – Sven Marnach Feb 29 '12 at 17:19
@Gurgeh, if that were easy, we wouldn't have cryptography. – Wilduck Feb 29 '12 at 17:19
@Gurgeh: That's a rather complex topic. The most simple approach is to iterate through the numbers 2 to x // 2 for both numerator and denominator and split off any divisors you find. – Sven Marnach Feb 29 '12 at 17:22

One can do this much quicker than using prime factorization. Below I show how to reduce the problem to testing if an integer is a (specific) perfect power.

Assume $\rm\:R,\: K/N\:$ and $\rm\:R^{K/N} = S\in\mathbb Q$, with $\rm\:K/N\:$ reduced, $\rm\:K,N\in\mathbb Z$. We show $\rm\:R^{1/N}\in \mathbb Q.\:$ By Bezout, $\rm\:gcd(N,K) = 1\:$ $\Rightarrow$ $\rm\:JN+IK = 1\:$ for some $\rm\:I,J\in \mathbb Z.\:$ Therefore

$$\rm 1/N \ =\ J + IK/N\ \Rightarrow\ R^{1/N}\ =\ R^{J+IK/N}\ =\ R^J(R^{K/N})^I = R^J S^I \in \mathbb Q$$

Conversely $\rm\:R^{1/N}\in \mathbb Q\ \Rightarrow\ R^{K/N} = (R^{1/N})^K\in \mathbb Q$.

So we've reduced the problem to determining if $\rm\:R^{1/N} = A/B \in \mathbb Q$. If so then $\rm\: R = A^N/B^N\:$ and $\rm\:gcd(A,B)=1\:$ $\Rightarrow$ $\rm\:gcd(A^n,B^n) = 1,\:$ by unique factorization or Euclid's Lemma. By uniqueness of reduced fractions, this is true iff the lowest-terms numerator and denominator of $\rm\:R\:$ are both $\rm\:N'th\:$ powers of integers.

So we reduce to the problem of checking if an integer is a perfect power. This can be done very quickly, even in the general case, see D. J. Bernstein, Detecting powers in almost linear time. 1997.

-
Fascinating! Was this result known to you, or did you just quickly derive it? – Gurgeh Mar 1 '12 at 9:24
IMO, reducing $R^{K/N}$ to $R^{1/N}$ is fairly intuitive, and a feasible algorithm to test if an integer is a perfect power is nearly obvious of you think about it. (just keep taking $n$-th roots for every $n$ until you get an integer or something less than 2) The trick is to have both thoughts in your head at the same time. – Hurkyl Mar 1 '12 at 15:34

Hmmm, I think that your assertion that 4^0.5 is rational is arguable. Bear in mind that in floating-point arithmetic 0.5 represents a range of real numbers, all of whose closest representation in the chosen version of f-p is closer to 0.5 than to either of its neighbouring f-p numbers. Only one of the numbers in that range leads to a rational result for the calculation of 4^0.5.

It is perfectly reasonable for Python (or any other computer) to, given f-p input, provide f-p output.

Perhaps you should have written it is obvious that 4^(1/2) is rational ?

-
4^0.5 is most certainly rational. But you raise an excellent point. When discussing problems about exact real numbers it's a good idea not to use decimal notation because it suggests you're talking about approximations. – Dan Piponi Feb 29 '12 at 17:23
This is why I mention that I am really talking about Python's Fraction type, which is not a float. The whole point is to avoid floats. – Gurgeh Feb 29 '12 at 17:27

I'd say that the real answer here is as follows: You don't want to be recovering precision once you've lost it.

For example (as senderle points out) one such irrational^irrational = rational example would be e^ln(10) = 10. In such a case, you don't want to be working with floats; you want to be working with symbolic math, like a computer algebra system. You look up your rules for exponentiation, and do a search to determine that it simplifies.

If you really were forced to lose precision however and try to recover it, and wanted to in this strange context (irrational^irrational = rational), and you don't care about being 100% correct, you can do as follows:

1. calculate a**b = c
2. if c is "close to a rational", return that rational

I believe this is used in graphing calculators. Even python's Fraction library uses this technique as .limit_denominator(...). Specifically you say that you will return the "closest" rational, but slightly penalizing rationals which are "complicated" (e.g. number of digits) compared to the inputs (base and exponent). One such algorithm for the "best rational approximation" would use continued fractions, e.g. http://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations (similar to how rational approximations of pi are computed); you could tweak this to penalize guesses which are complicated with respect to the base and exponent.

Thus, I personally would prefer to have the power to simplify mathematical expressions, rather than lose precision and have to recover it. =)

-
Note: This answer was given in response to the question before it was (unreasonably) migrated from stackoverflow. – ninjagecko Feb 29 '12 at 19:07