Computers can only deal with a few rational numbers. Why is it important as a computer scientist to deal with irrational numbers?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Some irrational numbers have an exact and finite representation (e.g. via periodic continuous fractions). $\endgroup$– BakuriuJan 22, 2017 at 9:19
-
3$\begingroup$ Computers can deal with computable real numbers. $\endgroup$– Andrej BauerJan 23, 2017 at 7:13
Add a comment
|
6 Answers
$\begingroup$
$\endgroup$
3
The question displays a fundamental misunderstanding about the nature of what can be done with computers. To correct this misunderstanding, I suggest getting a copy of the computer algebra software Maple and trying the commands
expand((1+sqrt(2))^5);
sin(Pi/4);
If computers can only deal with rational numbers, how do you explain the results?
-
11$\begingroup$ You mean that you don't have to know the last 4 digits of Pi in order to do exact computations with it? $\endgroup$ Jan 22, 2017 at 8:07
-
2$\begingroup$ +1 for the good answer. Unfortunately, not everyone can try the given commands. $\endgroup$– drzbirJan 25, 2017 at 0:52
-
1$\begingroup$ I think this answer displays a misunderstanding of the question: it is possible in the same way to deal with subjects from art, philosophy, botany, economics--you name it, by using symbols whose meanings we agree to interpret in some particular way. Clearly, the question doesn't ask about the symbols computation can be applied to, but about importance of irrational numbers in the application itself (which I think is rather minor up to be extraneous). $\endgroup$– wvxvwJan 30, 2017 at 8:58
$\begingroup$
$\endgroup$
3
You're assuming that numbers can only be represented as fractions (either literally, by having a datatype storing integer numerator and denominator, or implicitly by using some kind of floating point representation) but this isn't true. For example, you can easily represent rational complex numbers by storing the rational real and imaginary parts. Similarly, you can represent all numbers of the form $a+b\sqrt{2}$ for rational $a$, $b$, and compute exactly with them (note that this class of numbers is closed under addition, subtraction, multiplication and division). Going a little bit farther, it's not hard to represent all algebraic numbers (i.e., all numbers that are roots of polynomials with rational coefficients). And, hey, you might was well throw in your favourite transcendental (non-algebraic) constants, such as $\pi$ and $\mathrm{e}$.
As to why it's important to be able to deal with irrational numbers: much of mathematics uses them and we want to be able to both do mathematics with computers, and use mathematics to analyze computation.
answered Jan 22, 2017 at 10:54
-
1$\begingroup$ Of course, if you include both $e$ and $\pi$ then in principle you will not necessarily be able to tell whether two quantities are equal. $\endgroup$– DavidJan 25, 2017 at 15:00
-
1$\begingroup$ @David It depends what operations you allow and what quantities you add. For example, if you close $\mathbb{Q}\cup\{\mathrm{e},\pi\}$ under $+$, $-$ and $\times$, then any expression can be written as a sum of monomials of the form $r\mathrm{e}^i\pi^j$ for $r\in\mathbb{Q}$, $i,j\in\mathbb{N}$ and two expressions are equal if, and only if, their corresponding monomials have the same rational coefficients. $\endgroup$ Jan 25, 2017 at 15:15
-
2$\begingroup$ Only if you believe that $e$ and $\pi$ are algebraically independent, which is a famous open conjecture. $\endgroup$– DavidJan 25, 2017 at 18:26
$\begingroup$
$\endgroup$
6
I can see why the question is being downvoted, but this is too good not to post. Suppose you have a coin with bias $p\in[0,1]$, which might be rational or irrational. Question: using only finite memory, can you devise a test for determining whether $p$ is rational or not from a sequence of independent $p$-coin flips? Incredibly, as Hirschler and Cover showed in 1975, "an 8-state memory with a time-varying algorithm makes only a finite number of mistakes with probability one on determining the rationality of the parameter of a coin. Thus, determining the rationality of the Bernoulli parameter $p$ does not depend on infinite memory of the data." http://projecteuclid.org/euclid.aos/1176343194
-
1$\begingroup$ That seems like a rather misleading summary. The procedure makes only a finite number of mistakes, but you have no idea when it's done making them. It doesn't look like there's any finite time at which you can say "we've determined the rationality of $p$". $\endgroup$ Jan 22, 2017 at 19:16
-
1$\begingroup$ It's a direct quote from the abstract; please address all complaints to Profs. Hirschler and Cover. But really, you wouldn't expect to be able to determine the rationality in finite time and know it -- even with unbounded memory, right? $\endgroup$– AryehJan 22, 2017 at 20:00
-
$\begingroup$ @Aryeh: by quoting the paper you've implicitly endorsed it. I do not think it's fair to "forward" the objections to the author, who is not present on this forum. $\endgroup$ Jan 23, 2017 at 7:12
-
$\begingroup$ I'm flattered to have someone appraise my standing in the community sufficiently highly so as to be able to "endorse" a result of Tom Cover. $\endgroup$– AryehJan 23, 2017 at 7:16
-
1$\begingroup$ If they had used the phrase "decide rationality", we would say that it's incompatible with modern usage. I do feel a bit surreal having to defend a paper with Thomas Cover as a co-author -- a very clever paper at that. If the cstheory.stackexchange community feels that Hirschler and Cover oversold their results, feel free to open a thread about that somewhere. I just quoted the paper's abstract verbatim. $\endgroup$– AryehJan 29, 2017 at 9:47
$\begingroup$
$\endgroup$
4
Even if you're not trying to compute them, irrational numbers arise throughout computer science, particularly in the analysis of the complexity of algorithms.
For example, if you want to know how deep your binary search tree needs to be, or you want to know how many steps your divide-and-conquer algorithm will take, you'll need logarithms (see the so-called master theorem.) As a bonus, logarithms are not only irrational - they're typically transcendental!
Fibonacci numbers arise in many algorithms (e.g. Fibonacci hashing, Fibonacci heaps, etc.); the Fibonacci numbers are given by $\frac{1}{\sqrt5}(\alpha^n-\beta^n)$ where $\alpha=(1+\sqrt5)/2$ and $\beta=(1-\sqrt5)/2$ are both irrational. In particular, $F_{n+1}/F_n$ converges to $\alpha$ (the golden ratio.)
In a different vein, say you have to write code that compresses a certain kind of databases. You'll need to understand the (information-theoretic) entropy of the language of the information in the database in order to determine how much space you can save; this is computed in terms of logarithms.
In short, as a computer scientist, you can try to hide, but you can't escape the irrationals.
-
$\begingroup$ But the Fibonacci numbers themselves are rational. $\endgroup$ Jan 23, 2017 at 11:09
-
2$\begingroup$ @DavidRicherby That's right! But to understand them you need irrationals. Even though they're rational, the ratio of consecutive Fibonacci numbers tends to $\alpha$. $\endgroup$– TadJan 23, 2017 at 13:23
-
$\begingroup$ More generally, the analysis of algorithms rely a lot on linear recurrence sequence; their solution is expressed using an exponential polynomial, which involve irrational numbers. Yes, it so happens that all the elements of the sequence are integers, but if you want to compute the $n$-th element, for some large $n$, you'll most likely use a closed form of the sequence. $\endgroup$ Jan 26, 2017 at 10:42
-
$\begingroup$ @MichaëlCadilhac Yes, and I'd go further. Often (as in the Fibonacci case) the underlying recursive process satisfies the hypotheses of the Perron-Frobenius theorem. In such cases there's a unique eigenvalue $\alpha$ of maximum modulus and the recursive sequence is $\Theta(\alpha^n)$. $\endgroup$– TadJan 26, 2017 at 12:46
$\begingroup$
$\endgroup$
Chen and Kao use irrational numbers to reduce the number of random bits in Polynomial Identity Testing (though eventually they use rational appproximations to these irrational numbers of sufficient accuracy)
$\begingroup$
$\endgroup$
One reason that computer scientists can be interested in irrational numbers is because of any of their mathematical properties in various contexts. Such properties can then be utilized in algorithms.
An example: Fibonacci Hashing makes use of the mathematical properties of irrationals and specifically the golden-ratio (the context here is Three-Distance Theorem, which deals with gaps created by fractional-part of multiples of the irrational). Though in the implementation of this hashing, we are actually approximating that irrational (golden ratio) with some rational, but its property helped in making a choice.
