How to check a number for irrationality

Question

How can I check a number for irrationality? We enter an irrational number and use only the standard std library.

Answer 1

All floating-point numbers can be represented in the form x = significand × 2exponent, where significand and exponent are integers. All such numbers are rational by definition. That's why this problem has only an approximate solution.

One possible approach is to expand a number into a continued fraction. If you encounter very small or zero denominator, the input number is approximately rational. Or, better, if all denominators are not small, then the number is approximately irrational.

Rough idea:

bool is_rational(double x) {
    x = std::abs(x);
    for (int i = 0; i < 20; ++i) {
        const auto a = std::floor(x);
        if (x - a < 1e-8)
            return true;
        x = 1 / (x - a);
    }
    return false;
}

int main() {
    std::cout << std::boolalpha;
    std::cout << is_rational(2019. / 9102.) << std::endl;  // Output: true
    std::cout << is_rational(std::sqrt(2)) << std::endl;   // Output: false
}

One should think about the optimal choice of magic numbers inside is_rational().

Answer 2

As @Jabberwocky pointed out, you won't be able to verify whether the number is truly irrational with computational means.

Looking at it like a typical student's assignment, my best bet it trying to approach the number by division without creating an endless loop. Consider using Hurwitz's Theorem or Dirichlet's approximation theorem. Either way you will have to set some boundary for your computation (your precision), after how many digits you consider the number irrational.

Answer 3

Irrational number are... Well.. irational. Meaning you can't represent them with a Numerical Value, that's why we write them via a symbole (eg: π). Most you can do is an approximation. For exemple: In Math.h there is approximation for Pi as long double. If you want something more accurate you can use a byte array to reimplements something like BigNum but it will still be an approximation.

We enter an irrational number

If your question was about an Input (cin) then just grab it as a string and do an aproximation.

Answer 4

The amount of memory your computer has is finite. The number of rational numbers is infinite. More importantly, the amount of rational number with a decimal expression too long for your computer to store it is infinite as well (and this is the same to every computer in the world). This is due to the fact that you can build a rational number as "long" as you want just by adding random digits to it.

A computer can't really work with (all) real numbers. As far as I know the only thing computers do is work with a limited accuracy (although accurate enough to be very useful) . All of the numbers they work with are rational.

Given a number, the only thing you can ask your computer to do for you is to calculate its decimal expression to some extent after enough time. All numbers your computer is able to do this with are known as the set of computable numbers. But even this set is "small" when compared with the real numbers set in terms of cardinality.

Therefore, a computer has no way to decide wheter if a number is rational or not, as the concept of number they work with is too simple for doing that.