4
$\begingroup$

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.

  • 0
    @Gurgeh: though cstheory.stackexchange is also a reasonable forum in the future. Too bad SO isn't like Quora.2012-02-29

4 Answers 4

0

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. =)

  • 2
    Note: **This answer was given in response to the question before it was (unreasonably) migrated from stackoverflow.**2012-02-29
13

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.

  • 1
    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.2012-03-01
5

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.

  • 0
    Oh. Turns out your intuition was wrong. See Bill Dubuque, below.2012-03-01
0

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 ?

And I see that you already have an answer to your question so I'll stop now.

  • 1
    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.2012-02-29