# Importance of irrational numbers in computer science

Computers can only deal with a few rational numbers. Why is it important as a computer scientist to deal with irrational numbers?

• Some irrational numbers have an exact and finite representation (e.g. via periodic continuous fractions). – Bakuriu Jan 22 '17 at 9:19
• Computers can deal with computable real numbers. – Andrej Bauer Jan 23 '17 at 7:13

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?

• You mean that you don't have to know the last 4 digits of Pi in order to do exact computations with it? – Peter - Reinstate Monica Jan 22 '17 at 8:07
• +1 for the good answer. Unfortunately, not everyone can try the given commands. – drzbir Jan 25 '17 at 0:52
• 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). – wvxvw Jan 30 '17 at 8:58

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.

• 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. – David Jan 25 '17 at 15:00
• @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. – David Richerby Jan 25 '17 at 15:15
• Only if you believe that $e$ and $\pi$ are algebraically independent, which is a famous open conjecture. – David Jan 25 '17 at 18:26

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

• 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$". – user2357112 supports Monica Jan 22 '17 at 19:16
• 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? – Aryeh Jan 22 '17 at 20:00
• @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. – Andrej Bauer Jan 23 '17 at 7:12
• 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. – Aryeh Jan 23 '17 at 7:16
• you wouldn't expect to be able to determine the rationality in finite time and know ii -- Isn't that what "determine" means? – Jeffε Jan 29 '17 at 9:02

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.

• But the Fibonacci numbers themselves are rational. – David Richerby Jan 23 '17 at 11:09
• @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$. – Tad Jan 23 '17 at 13:23
• 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. – Michaël Cadilhac Jan 26 '17 at 10:42
• @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)$. – Tad Jan 26 '17 at 12:46

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)