How can I test if a number is irrational?

Hello there,

In digital signal processing, one indicator that a signal may be quasi-periodic is that the ratio between the pair of frequencies (f1/f2) provides an irrational number as result. What I want to do is check if the result is irrational or not in the form of a function, just as ge(a,b) returns a boolean relative to 'a' being greater or equal to 'b' or not. However, I was not able to find any function appropriate for this (and no other posts regarding this too).

P.S.: I know that the user will know if (s)he is inputing an irrational number. As silly as it seems, I still want to display a message saying whether it is periodic or quasi-periodic. By the way, of course, there is still the possibility of inputing two irrational numbers, one for each frequency, and having a rational result. This is why such a check becomes helpful.

----------------------------------------------

EDIT 1: As an addition, I guess the aformentioned may have mislead most of you to believe that I wanted MATLAB to tell me if a number is rational or not only by its double or int value. However, I'm thinking about what is going in the Symbolic Toolbox level.

Take, for instance, these parameters:

f1 = 2;
f2 = sqrt(2);

a = f1/f2;

Provides (or must provide) in symbolical level...

a = sqrt(2);

Since I can work, for instance, with functions. I'm considering that this is different from

a = double(f1/f2);

We know that if we type this, say, in the command window, f1/f2 will yield the same as double(f1/f2), but the processing is not exactly the same for these cases. My knowledge on MATLAB may fail at this point, but I believe that in some point in the processing of data, f1/f2 still is a symbolic value before it is converted to double to be displayed. That is the level of processing that I'm trying to work with. It seems reasonable to me that, at this stage, it may be easy to infer the "class" of our symbolic number... or isn't it?

[Walter Roberson]

f1 or f2 would have to have been defined as sym() for sqrt(2) to be the output. Having the symbolic toolbox available does not change what happens for strictly numeric values.

Is it correct that in your situation, the user might have communicated to you two arbitrary symbolic constant expressions (that is, something that might be a formula but does not have free variables) and the task is to determine whether the ratio is irrational? If so then can it be further restricted to there being no variables at all, not just no free variables (so for example no definite integration over a formula for which there might not happen to be a closed form solution?) Are there any other restrictions? For example can you guarantee that none of the values will be complex? Can there be roots of a higher order polynomial?

[Walter Roberson]

If you use

f1 = sym(2);
f2 = sqrt(sym(2));

a = f1/f2;

then the result will be the symbolic expression 2^(1/2) not the same as double(f1/f2) which will be 1.4142135623731 and not the same as 2/sqrt(2) or double(2/sqrt(2)) which will be 1.41421356237309 due to differences in roundoff in the intermediate expressions.

When you have the symbolic toolbox, sqrt(2) is still 1.4142135623731 not the symbolic expression 2^(1/2)

[Alexandre Piccini]

Thank you Walter,

This actually sheds some light in part of the problem, which is having a symmbolic value to analyse.

Ok, so, answering what you asked before:

"Is it correct that in your situation, the user might have communicated to you two arbitrary symbolic constant expressions (that is, something that might be a formula but does not have free variables) and the task is to determine whether the ratio is irrational?" - Yes

If so then can it be further restricted to there being no variables at all, not just no free variables (so for example no definite integration over a formula for which there might not happen to be a closed form solution?) - Yes

Are there any other restrictions? For example can you guarantee that none of the values will be complex? Can there be roots of a higher order polynomial? - Only positive and real numbers are to be considered for f1 and f2. No variables, only constants of any kind within real numbers. In terms of roots, I am only considering roots of integers or rationals. There is no restriction that it has to be specifically a square or cubic (or further) root.

Answer 1

[Guillaume]

I don't think you've thought this through properly:

1. Nobody knows a way to find whether an arbitrary number is irrational.
2. By definition, all numbers stored on a computer (in IEE754 format) are rationals, since they're all fractions of powers of 2.

[Alexandre Piccini]

I do know this. However, since I'm working in symbolic environment, irrational numbers and results are a possibility...

[Fahad]

Even in the symbolic environment, there exists no automatic way (or algorithm) to know whether a number is irrational or not?

If you can tell us about the rationality/ irrationality of any number, please let us know.

[Walter Roberson]

No-one has been able to prove whether pi+e is rational or not. If there was an existing algorithm then the question would have been answered by using that algorithm.

Answer 2

[Walter Roberson]

In MATLAB, all numbers that can be expressed in the data types uint8, uint16, uint32, uint64, int8, int16, int32, int64, and logical are definitely rational. For the data types single and double, the only values that can be expressed that are not rational are -inf, +inf, and NaN, but those values are also not irrational (they are not, strictly speaking, numbers.)

Therefore the only way numbers could be entered that might potentially be irrational is if they are entered as strings, either as named constants or as expressions like sqrt(2) and you would have to proceed from there.

http://math.stackexchange.com/questions/62878/proving-irrationality

[John BG]

Walter, in your answer, where you write

the only way numbers could be 
entered that might potentially be 
irrational is if they are entered as strings,

it is not correct:

If you find a cycle in the decimals, you can stop dividing and state that the cycle will repeat endlessly and therefore the number is irrational.

This procedure is clearly explained in the link you provide.

anyway, what a question, it's like asking how does time work .. in the MATLAB forum

[John D'Errico]

Huh? John, this makes no sense. A repeating decimal ALWAYS represents a rational number.

But Walter said nothing about repeating decimals. The point that Walter made is you can create a string as 'sqrt(2)' or some other radical, then use it in the symbolic toolbox.

[Walter Roberson]

John, every double() and every single() is stored as a rational value in MATLAB, as a sign bit, and then (2^an_exponent) times (some_integer). The numerator is (some_integer) and the denominator is (2^(-an_exponent)). You can read about the formats here for double() and here for single()

This is a consequence of floating point numbers being stored in finite precision, in a fixed number of bits. The representation happens to be binary.

It is much the same logic as would be used if the definition had instead been that hypothetically 16 decimal digits and an exponent had been stored: in such a case you could say that it had been stored as a rational value of (10^an_exponent) times (some_integer). IEEE 754 does define the possibility of decimal representation instead of binary; the only modern systems that I am aware of that use that are some IBM Z-series.

If you happen to be using the OS-X version of MATLAB, then you can use

sprintf('%.999g', TheNumber)

to see the complete decimal expansion of the number. For example, for pi it shows

3.141592653589793115997963468544185161590576171875

If you happen to be using MS Windows, then doing this is hopeless; the run-time library doesn't even try past 16 digits. If you happen to be using Linux, then the situation is not as bad as on MS Windows, but the output has not always been accurate. So for MS Windows or Linux, I recommend that you get James Tulsa's num2strexact from the File Exchange.

Every system that uses a fixed finite number of bits to represent numbers has to represent them as implicit rationals (unless it goes through the trouble of having a finite list of irrational constants that it represented specially, but as soon as you started using those constants in combination with the finite-length numbers it would have to drop into the finite-length mode.)

[Jan]

Note: The output of sprintf on Macs shows the decimal representation of the the double value, which is the nearest value to pi, but not pi itself:

sprintf('%.20f', pi)
Output:  3.14159265358979311599
Correct: 3.14159265358979323846...

[Alexandre Piccini]

I believe I may have expressed myself badly... I will make an edit to the original question and wait for you guys to weigh in.

Thanks for the attention, anyways :)

[Walter Roberson]

pi lower case is a function that returns an approximation to Pi the constant .

[Walter Roberson]

"Only positive and real numbers are to be considered for f1 and f2. No variables, only constants of any kind within real numbers. In terms of roots, I am only considering roots of integers or rationals. There is no restriction that it has to be specifically a square or cubic (or further) root."

Given two symbolic constants, f1 and f2, that involve only numbers and roots of integers or rationals, then MATLAB will automatically factor the rationals inside of roots and remove as much outside the root as possible. For example, (sym(5)/64)^sym(1/3) will be simplified to 5^(1/3)/4 . Therefore provided that MATLAB has been allowed to evaluate the symbolic expression at least once, then any remaining root contains only parts that could not be reduced, and you can be certain that the resulting root is not a rational number.

However, as mentioned by John D'Errico, it is not known whether Pi*e is rational, so if your f1 = Pi and f2 = exp(-1) then f1/f2 would be Pi*e and the rationality of that is not known.

This starts to allow us to build a table:

• f1 and f2 are each rational (including integer): result is rational and real
• f1 or f2 is rational (including integer) and the other still contains a root of a positive rational (including integer) after allowing MATLAB to simplify: result is irrational and real
• f1 or f2 is rational (including integer) and the other still contains a root of a negative rational (including integer) after allowing MATLAB to simplify: result is both irrational and complex
• f1 and f2 both contain roots of positive rationals (including integer), or both contain roots of negative rationals (including integer): allow MATLAB to simplify once, and if the result still contains a root, the result is irrational and real
• one of f1 and f2 contains pi but not e, and the other contains the other of the two, either plain or inside a root: the rationality of the result is probably not known and is probably difficult to prove
• one of f1 or f2 contains pi but not e, including inside a root, and the other does not contain either pi or e: I don't know; I suspect it might be difficult to prove. My suspicion is that the result is not rational
• one of f1 or f2 contains e but not pi, including inside a root, and the other does not contain either pi or e: I am not sure, but the material I read is suggestive that there might be ways to deal with this situation. My suspicion is that the result is not rational
• both f1 and f2 contain pi, including inside a root, or both contain e, including inside a root, but pi and e are not both present: let MATLAB simplify, and if the result still contains pi or e, then the result is irrational.

Rationals and integers and their roots are "algebraic numbers" and it seems plausible to me that if you multiply or divide an algebraic number and a transcendental that the result would be transcendental. The tricky parts come when you combine transcendental numbers.

The table is possibly reducible to this: let MATLAB simplify the expression f1/f2 . If the result contains both pi and e, then the answer is likely "Nobody knows"; if the result contains either pi or e but not both, then I think the result is irrational; if the result does not contain pi or e but contains a root, then the result is irrational; if the result is pure rational (or integer) then the result is rational.

This analysis does not, however, extend to the case where f1 or f2 can be expressions in constants if either addition or subtraction is permitted. MATLAB cannot reliably automatically factor additive expressions into their roots (though using the simplify() command with the 'steps' option helps.) For example it does not even automatically handle this well:

>> sqrt((x+1)^2)
ans =
((x + 1)^2)^(1/2)

The difficulty is reduced by the fact that MATLAB will automatically combine rational constants, but if the expression is over pi or e then MATLAB might not simplify:

Pi = sym('pi');
>> sqrt(expand((Pi+1)^2))/(Pi+1)
ans =
(2*pi + pi^2 + 1)^(1/2)/(pi + 1)

though simplify can help:

>> simplify(ans)
ans =
1

[Christopher Creutzig]

> Given two symbolic constants, f1 and f2, that involve only numbers and roots of integers or rationals, then MATLAB will automatically factor the rationals inside of roots and remove as much outside the root as possible.

That is not exactly true. E.g., MATLAB will not cancel sqrt(sym(6))/sqrt(sym(2)) by default. A call to simplify will.

Answer 3

[John D'Errico]

You say there should be some simple way to know if a symbolic toolbox result is rational or not. Note that as simple a question of whether pi+exp(1) is rational is unproven as far as I can see.

You can want a nice simple solution to exist. But nice simple solutions are not always available.

You talk about a ratio between a pair of frequencies as a rational number. To me, this is silly, that you are worried about something being EXACTLY representable as a rational number, beyond 16 significant digits. Instead, you might just look if the ratio is well approximated by a fraction with a reasonably small denominator.

[N,D] = rat(.2324343434232,0.001)
N =
    10
D =
    43

N/D
ans =
      0.23256

[N,D] = rat(0.30000001,0.001)
N =
     3
D =
    10

Pick some reasonable tolerance, and don't worry about 40 digits.

[Walter Roberson]

(more on pi+e: https://www.quora.com/Why-is-it-hard-to-prove-the-irrationality-of-e+pi-e-pi-and-other-combinations-of-e-and-pi)

[Alexandre Piccini]

John,

It is more a matter of finding out if what I said already exists/is possible to be done in MATLAB. There are several ways I could get to the same conclusion (the signal is quasiperiodic), through countless methods of tackling the same problem. I could, for instance, take two cycles of quantized data and compare them...

cont = 1;
for i = 1:samplingrate:lambda
x1[cont] = num2str(signal(i));
cont = cont + 1;
end

for i = 1:samplingrate:lambda
x2[cont] = num2str(signal(i+lambda));
cont = cont + 1;
end

notquasi = strcmp(1,2)

If notquasi = 1, means that both strings are equal, and hence the signal is periodic. This code is just hypothetical - there might be a detail here and there not clicking.

Anyway, as I said, this is one amongst several ways of tackling this question. It is more about mathematical "righteousness" than actual practicality.

Thanks for the help.

Answer 4

[David Goodmanson]

Hello Alexandre, although your interest is along conceptual lines, still it's fun to look at practical consequences. Supposing the two frequencies are high, up around the GHz cell phone range, and have all 16 digits of double precision:

f1 = 1234567890123456e-6 
f1 = 1234567890123457e-6

If f1 and f2 are incommensurate (gcd = 1) as in this example, and supposing you had frequency stability of better than one part in 10^16 (which isn't going to happen outside of a metrology lab) then it will take 1e6 seconds before the carrier pattern repeats, or about 12 days. Not even Heloise and Abelard would be on the phone that long.

There is of course a big difference philosophically, but when you get enough digits the distinction between incommensurate and 'irrational ratio' becomes moot.

[Walter Roberson]

Looking at a reference it appears the diameter of the universe could be expressed as roughly 206 bits of Planck distances. There might not be any point going to more than 206 digits ;-)

[David Goodmanson]

Yo Walter, you are using more than half of those bits all by yourself!

[Walter Roberson]

The surface area of a black hole is proportional to the amount of information encoded on it, so I am building a perpetual monument by inflating a black hole as quickly as I can!

[David Goodmanson]

:)

Answer 5

[LALE ASIK]

May I ask you a question? Do you find a method how to test it?

[Alexandre Piccini]

As pointed out by someone here, even a logical proof for the general case is not existent. Numerically, you eventually run into the limits of double precision, at which certainty about irrationality may become blurry. I also solved my main problem in some other form, but that is not revelant here. Do you really need such a test or can you do what you need with an workaround or approximation?

[LALE ASIK]

I plotted the solutions of a predator-prey model in the time domain and then by using the data, FFTs were plotted. But they are not clear enough which one is periodic or quasi-periodic. Therefore, I want to test that the ratio of frequencies is rational or irrational. May I ask how you solved your main problem?

[Alexandre Piccini]

In your case you're already working with numerical precision limitations. Therefore, I would suggest calculating the ratio and checking how many decimals were necessary to express the ratio of frequencies. Maybe it is safe to say that your data is quasi-periodic if you reached the limit of digits of precision. After all, your data input and output wouldn't be much different form being actually (ir)rational, if it is not.

[Walter Roberson]

Remember though that you need to take into account the width of the fft bins.

[LALE ASIK]

Thank you so much.

[Walter Roberson]

For example, consider 43 and 179 with an fft bin width of 1. 43/179 is 0.240223463687151, which needs all of the decimals to express the ratio of frequencies as far as humans can easily perceive. But with the bin width of 1, the value could be between 42/180 and 44/178, and 42/180 is 0.233333333333333 which is 7/30 which people probably would consider rational.

Can we get a measure of rationality by using rat() and looking at the complexity of the continued fraction?

>> rat(43/179)
ans =
    '0 + 1/(4 + 1/(6 + 1/(7)))'
>> rat(42/180)
ans =
    '0 + 1/(4 + 1/(4 + 1/(-2)))'
>> rat(44/178)
ans =
    '0 + 1/(4 + 1/(22))'
>> rat(pi)
ans =
    '3 + 1/(7 + 1/(16))'

Ummm... No, apparently not. When rat(pi) shows up as less complex than the other values, we are in trouble. Unless, that is, we start adding in the tolerance to the rat() call:

>> rat(pi,1e-16)
ans =
    '3 + 1/(7 + 1/(16 + 1/(-294 + 1/(3 + 1/(-4 + 1/(5 + 1/(-15)))))))'

But still, what we would tend to see as simple, 42/180, 0.23* comes out more complex than 44/178, 0.247191011235955, that we would struggle to see rationality in.