6
$\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.

$\endgroup$
18
  • $\begingroup$ 'the power function could conceivably only return floats when it has to' What would the benefit of that be? $\endgroup$
    – Marcin
    Feb 29, 2012 at 17:11
  • $\begingroup$ Also, I assume you mean "is there an algorithm more efficient than evaluating the power expression, and testing if the result is rational?" $\endgroup$
    – Marcin
    Feb 29, 2012 at 17:13
  • 1
    $\begingroup$ Why the close votes? This isn't off-topic, it was clearly stated as relating to implementing fractions. I personally find it useful. $\endgroup$
    – ninjagecko
    Feb 29, 2012 at 17:39
  • 3
    $\begingroup$ @ninjagecko math.hmc.edu/funfacts/ffiles/30002.3-5.shtml $\endgroup$
    – Gurgeh
    Feb 29, 2012 at 17:42
  • 1
    $\begingroup$ @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? $\endgroup$
    – Gurgeh
    Feb 29, 2012 at 20:16

4 Answers 4

17
$\begingroup$

We 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 - i.e. an integer perfect power test.

Lemma $\ $ If $\rm\,R\,$ and $\,\rm K/N\:$ are rationals, $\rm\:K,N\in\mathbb Z,\ \gcd(K,N)=1,\,$ then $$\rm\:R^{K/N}\in\Bbb Q\iff R^{1/N}\in \mathbb Q\qquad$$

Proof $\ (\Rightarrow)\ $ If $\,\rm\color{#0a0}{R^{K/N}\in\Bbb Q},\,$ then by $\rm\:gcd(N,K) = 1\:$ we have a Bezout equation

$$\rm 1 = JN+I\:\!K\, \overset{\!\div\ N}\Rightarrow\ 1/N = J + IK/N\ \Rightarrow\ R^{1/N} =\ R^J(\color{#0a0}{R^{K/N}})^I \in \mathbb Q$$

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

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.

$\endgroup$
4
  • $\begingroup$ Fascinating! Was this result known to you, or did you just quickly derive it? $\endgroup$
    – Gurgeh
    Mar 1, 2012 at 9:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – user14972
    Mar 1, 2012 at 15:34
  • 1
    $\begingroup$ Especially if you're going to be marking other questions as duplicates of this one, please include the algorithm in your answer rather than linking to it. (Or at least include a simpler algorithm that's not as good, but still efficient.) $\endgroup$ Apr 1, 2022 at 19:30
  • 1
    $\begingroup$ @Misha That has been on my (very long) to-do list for quite some time but, alas, has not yet percolated to top priority. $\endgroup$ Apr 1, 2022 at 19:44
6
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – chepner
    Feb 29, 2012 at 17:16
  • $\begingroup$ This begs the question, how do you decompose a into its prime factorisation? $\endgroup$
    – Gurgeh
    Feb 29, 2012 at 17:17
  • $\begingroup$ @chepner: An arbitrary rational does have a unique prime factorisation. The exponents aren't necessarily positive. $\endgroup$ Feb 29, 2012 at 17:19
  • 1
    $\begingroup$ @Gurgeh, if that were easy, we wouldn't have cryptography. $\endgroup$
    – Wilduck
    Feb 29, 2012 at 17:19
  • $\begingroup$ @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. $\endgroup$ Feb 29, 2012 at 17:22
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Dan Piponi
    Feb 29, 2012 at 17:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – Gurgeh
    Feb 29, 2012 at 17:27
0
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ Note: This answer was given in response to the question before it was (unreasonably) migrated from stackoverflow. $\endgroup$
    – ninjagecko
    Feb 29, 2012 at 19:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .