Computer Science and Irrational Numbers

[Indistinguishable]

@Hypnagogic_Jerk

I think what Indistinguishable is saying is that while there is no way to represent 1/3 or 1/7 exactly in decimal notation, just saying that “it’s impossible to represent them exactly” without specifying what other numbers you want to be able to represent is misleading at best. For example, 1/3 can be represented (exactly) as 0.1 in base 3, and even pi could be represented exactly in some systems.

Yes, exactly. (For example, notice that none of us in this thread have had any difficulty in referring to pi exactly. We ourselves do not always only use the particular notation system of finitely expanded decimal representations)

@Thudlow_Boink

But (IIUC) there are lots of irrational numbers that we can’t describe exactly, in any way: there’s no finite specification for them.

That all depends on what you want a finite specification to do. I can always say, of any number X, “I will let the bit pattern 0100111001 represent X”, and thus consider it to have been represented. This is why it’s meaningless to talk of representation of a particular value in isolation, without specifying what operations and observations one wants to be able to carry out upon the represented datatype.

[billfish678]

One thing that recently occured to me.

With something like e or pi, you can’t tell me exactly where it is on the number line…or can you?

Or in other words, I could take some number that I knew out to some large number of digits/decimal places. WITHOUT calculating pi or e past that point, I cant automatically tell you whether my chosen number is greater or less than e or pi.

I can (sorta?) do that with repeating numbers.

Is this a distinction with or without a difference?

[Indistinguishable]

@Indistinguishable

Yes, exactly.

But I see now that perhaps this train of conversation may have been unfair to ZenBeam, because ZenBeam’s point is also true; there are a great many rational values which binary floating-point doesn’t represent exactly, either. It only represents dyadic values (a multiple of 2 raised to some integer). So 1/3 and 1/7 are just as bad as pi in terms of their ability to be represented in IEEE floating-point.

Which means, if you wanted, for some purpose, to represent them exactly, you would need to use some other datatype. Granted, IEEE floating-point arithmetic will be much faster than whatever else, since your computer has built-in hardware support for it, but that’s a quirk of your computer, not a fundamental truth about computing.

[Thudlow_Boink]

@Indistinguishable

That all depends on what you want a finite specification to do. I can always say, of any number X, “I will let the bit pattern 0100111001 represent X”, and thus consider it to have been represented.

But how do you know what “number X” is, if you haven’t already specified it somehow?

[Indistinguishable]

@billfish678

One thing that recently occured to me.

With something like e or pi, you can’t tell me exactly where it is on the number line…or can you?

Or in other words, I could take some number that I knew out to some large number of digits/decimal places. WITHOUT calculating pi or e past that point, I cant automatically tell you whether my chosen number is greater or less than e or pi.

I can (sorta?) do that with repeating numbers.

Is this a distinction with or without a difference?

It’s an extremely important observation. This is the Dedekind cut system I mentioned above; represent a real number as a function which gives the answers to the question “Am I bigger than or smaller than X?” for any rational number X. You can computably do addition, multiplication, division, exponentiation, logarithms, sines, and so on, all the basic smooth functions you were ever exposed to, in terms of such representation. (Which is more than can be said of standard decimal representations…). It’s a very good system (for many purposes).

[Hypnagogic_Jerk]

@Thudlow_Boink

But how do you know what “number X” is, if you haven’t already specified it somehow?

Knowing that we can represent a number in some way doesn’t mean we can figure all that many properties about it, for example, having a process (even infinite) to compute its decimal (or other) representation. This is probably what you mean.

@Indistinguishable

It’s an extremely important observation. This is the Dedekind cut system I mentioned above; represent a real number as a function which gives the answers to the question “Am I bigger than or smaller than X?” for any rational number X. You can computably do addition, multiplication, division, exponentiation, logarithms, sines, and so on, all the basic smooth functions you were ever exposed to, in terms of such representation. (Which is more than can be said of standard decimal representations…). It’s a very good system (for many purposes).

That’s interesting. Though I’m guessing that it’s probably more computationally costly than the usual way numbers are represented in computers.

[Indistinguishable]

@Thudlow_Boink

But how do you know what “number X” is, if you haven’t already specified it somehow?

As Wittgenstein said, “Explanations come to an end somewhere”. If I were to give you a further specification of number X, you could ask “But how do I know how to interpret that specification? It’s just a bunch of words. Give me a blueprint for how to interpret that specification”. And so on ad infinitum. Whatever “specification” is, it cannot require such complete regress. Every word in the dictionary leads to other words in the dictionary.

I’m being gnomic and abstruse, but the point you raise is the very reason it is meaningless to talk about representations without specifying what you want to be able to do with those representations.

If the only thing you want to be able to do is represent the numbers 0.9042352352… and 0.832523533… and tell of numbers when they’re equal and when they’re not, then you can represent 0.9042352352… by “0” and 0.832523533… by “1” and, in the obvious way, carry out all the things you want to do with those representations.

If you want to represent people in the world and you want to be able to tell whether they’re male or female and whether they’re living or dead, then you can use the representations 00, 01, 10, and 11, with the first bit signifying gender and the second bit signifying life status. This representation won’t allow you to tell of two people whether they’re the same or different; you’d need to use a different representation for that. The representation system always depends on what you want to do.

If you want to represent positive integers, and you want to be able to quickly determine whether they are prime or not, then you could represent primes as a 0 and composite numbers as a 1. This representation system won’t let you do very much other than determining primality. If you also want to be able to tell of two numbers whether they are equal or not, then you could represent primes as a 0 followed by their standard representation in binary, and composites as a 1 followed by their standard representation in binary. Now you can quickly determine primality and quickly determine equality, and, in fact, you can quickly multiply as well, but you can’t quickly add. If you want to be able to quickly add, but don’t care so much for being able to quickly determine primality, then you would pick a different representation system (e.g., just go with standard binary representation and forget the initial primality tags). And in neither of those two systems can you quickly factorize composite numbers (at least, so far as is known); if you want to be able to quickly factorize, then you could use a representation directly in terms of the prime factorization; now you can multiply quickly but you can’t add quickly but you can factorize quickly. It all depends on what you want to do.

And the only sense in which any of these representation systems really do represent the things they could be said to represent is in the fact that if we do to them such and such operations as specified, we’ll get results which correspond to the things which we said we wanted to do with them. Representation depends on what you want to do. No more and no less.

[Indistinguishable]

@Hypnagogic_Jerk

Knowing that we can represent a number in some way doesn’t mean we can figure all that many properties about it, for example, having a process (even infinite) to compute its decimal (or other) representation. This is probably what you mean.

Right. This is a much more concise and better put response than mine.

That’s interesting. Though I’m guessing that it’s probably more computationally costly than the usual way numbers are represented in computers.

Yes, indeed. Though, to some extent, everything depends on what your hardware is optimized for. Standard floating-point arithmetic is so fast because computers, as an idiosyncratic design decision, have built-in units to do standard floating-point arithmetic, because people do so much standard floating-point arithmetic. There was a time when that wasn’t true. If people decided to do something else a lot more, then we could make computers where that was a lot faster. The same applies to standard binary representation of integers and so forth.

I don’t mean to handwave it all away. There’s still some fundamental differences between those and the “higher-order” definition of a Dedekind cut. But some amount of “But, the standard setup is so much faster” is often just because the standard setup is what architecture has been specially optimized for.

[Yossarian]

Just for yucks, I asked my Excel the following questions…

=4*ATAN(1)

and

=exp(1)

And got answers to pi and e to 15 decimal places, with nothing but zeros for the next however many I asked.

[Superfluous_Parentheses]

@Hypnagogic_Jerk

I think what Indistinguishable is saying is that while there is no way to represent 1/3 or 1/7 exactly in decimal notation, just saying that “it’s impossible to represent them exactly” without specifying what other numbers you want to be able to represent is misleading at best. For example, 1/3 can be represented (exactly) as 0.1 in base 3[…]

And quite a few programming languages (like Common Lisp) either store fractions as a simple pair of (big) integers by default or (like Perl and Ruby) have some standard facility you can use to do the same.

Also note that even (decimal) 0.1 (aka 1/10) cannot be represented exactly in an IEEE float, but for many calculations the approximation is good enough.

[Thudlow_Boink]

@Hypnagogic_Jerk

Knowing that we can represent a number in some way doesn’t mean we can figure all that many properties about it, for example, having a process (even infinite) to compute its decimal (or other) representation. This is probably what you mean.

Actually, what I was thinking of was irrational numbers that contain an infinite amount of information—ones you could think of as an infinite string of (decimal or binary or whatever) digits that was incompressible in an information theory sense.

So when Indistinguishable says, "represent the numbers 0.9042352352… and 0.832523533… " I say “which numbers 0.9042352352… and 0.832523533…”? There are uncountably many numbers that start with 0.832523533.

So I’m not thinking of the kind of irrational number that comes up as the result of some calculation or the answer to some question (because then the question would be the finite description of that number), but about all those other irrational numbers that nobody ever thinks about.

So (again, IIUC) you can’t have a scheme for representing all irrational numbers (either on a computer or anywhere else) where each one has a finite description. Which maybe means there’s no way to establish a system ahead of time that will allow you to exactly represent every rational number that might come up. Or to select a random irrational number.

[RaftPeople]

@Indistinguishable

Yes, indeed. Though, to some extent, everything depends on what your hardware is optimized for. Standard floating-point arithmetic is so fast because computers, as an idiosyncratic design decision, have built-in units to do standard floating-point arithmetic, because people do so much standard floating-point arithmetic. There was a time when that wasn’t true. If people decided to do something else a lot more, then we could make computers where that was a lot faster. The same applies to standard binary representation of integers and so forth.

Just to add to your point, mainframes and minicomputers still have hardware for performing operations on base 10 values stored in a binary format (BCD, Packed and Zoned Decimal) so that currency calculations like those found in financial applications can be precise and fast (floating point is generally not).

[RaftPeople]

@Thudlow_Boink

So (again, IIUC) you can’t have a scheme for representing all irrational numbers (either on a computer or anywhere else) where each one has a finite description. Which maybe means there’s no way to establish a system ahead of time that will allow you to exactly represent every rational number that might come up. Or to select a random irrational number.

Just total gut feel thought (that agrees with you): It seems that a system that allowed for representing all irrational numbers has just made a trade-off from trying to represent an infinitely long string to possibly being able to represent that string efficiently (meaning as a symbolic calculation), but that there will exist some other number that now has an infinitely long symbolic calculation representation. The problem has been shifted but not solved.

[Indistinguishable]

@Thudlow_Boink

Actually, what I was thinking of was irrational numbers that contain an infinite amount of information—ones you could think of as an infinite string of (decimal or binary or whatever) digits that was incompressible in an information theory sense.

Yes, but even measuring how much information a number (or anything else) contains is a relative notion. We could say “In this language, the shortest program which serially outputs the decimal expansion of X has length…” whatever. But who said anything about focusing on decimal expansions? That’s my point.

So when Indistinguishable says, "represent the numbers 0.9042352352… and 0.832523533… " I say “which numbers 0.9042352352… and 0.832523533…”? There are uncountably many numbers that start with 0.832523533.

That’s true, but when I said that, you were to imagine two particular numbers (the particulars of which didn’t matter, because the only thing we were going to be able to do with them was check for equality).

So I’m not thinking of the kind of irrational number that comes up as the result of some calculation or the answer to some question (because then the question would be the finite description of that number), but about all those other irrational numbers that nobody ever thinks about.

So am I. Take any particular number that no one ever thinks about, and let’s imagine the representation scheme under which it is represented by 1011101010100. Bam; it’s been represented! In a silly, futile way where we can’t do much with it. But then, you never said what you wanted to be able to do with it…

So (again, IIUC) you can’t have a scheme for representing all irrational numbers (either on a computer or anywhere else) where each one has a finite description. Which maybe means there’s no way to establish a system ahead of time that will allow you to exactly represent every rational number that might come up. Or to select a random irrational number.

That’s true. You can’t represent them all at once (if the things you want to be able to do require that you keep them all distinct). But that doesn’t mean any particular number is unrepresentable; all of them can be represented in some scheme or another. They just can’t all be simultaneously represented in one scheme.

Sure: there are lots of numbers for which no computer program can be written which outputs their entire decimal expansion. Which just means, in any scheme where we represent them, outputting decimal expansions is not one of the things we can do with them. But it may be the case that there are other things we want to do, which some representation scheme will be amenable to.

[ultrafilter]

@Thudlow_Boink

So (again, IIUC) you can’t have a scheme for representing all irrational numbers (either on a computer or anywhere else) where each one has a finite description. Which maybe means there’s no way to establish a system ahead of time that will allow you to exactly represent every rational number that might come up. Or to select a random irrational number.

If you ignore the numbers and sequences that can’t be finitely described, you end up with something that looks a lot like the real numbers, at least as far as the average mathematician is concerned. In particular, it contains all the algebraic numbers, which means that you have all of the rationals.

[Indistinguishable]

Incidentally: it’s only in classical logic that you can’t have a partial surjection from the natural numbers onto the reals [i.e., can’t give each real number at least one finite representation, with all of these distinct]. In intuitionistic logic, for example, it is consistent to suppose that all Dedekind cuts are computable, and thus, on that account of what real numbers are, there would be no problem in supposing there were some system of assigning unique real numbers to bitstrings in such a way as that ever real number was covered. It’s similarly intuitionistically consistent to suppose that there is a partial surjection from the naturals onto the countably infinite strings of bits or even that all functions from bitstrings to bitstrings are computable, even though Cantor’s proof is also intuitionistically valid, the key being that Cantor’s proof only forbids certain total surjections, but, in the intuitionistic setting, one can get away with partial functions doing almost the same thing. Which makes perfect sense; internally to “the computable world”, there clearly is a a universal datatype (that of bitstrings) with partial surjections onto all other suitably “normal” datatypes (since they’re all represented by particular bitstrings).

But this gets into foundational issues perhaps not worth dragging this thread into.

[Indistinguishable]

@ultrafilter

If you ignore the numbers and sequences that can’t be finitely described, you end up with something that looks a lot like the real numbers, at least as far as the average mathematician is concerned. In particular, it contains all the algebraic numbers, which means that you have all of the rationals.

Right (though when Thudlow Boink said “represent every rational”, he surely actually meant “represent every irrational”; he surely never doubted the capability to do the former).

But, again, the clarification I would want to make is to not say “the numbers that can’t be described”; this is misleading language. There isn’t really any such thing as a number which can’t be described, objectively, intrinsically. There’s only numbers for which, in such and such a language, you can’t give a specification in such and such a way. E.g., numbers whose decimal expansions aren’t computable [or numbers whose decimal expansions aren’t computable by a pushdown automaton, or numbers which can’t be defined as the roots to polynomial equations with integer coefficients, or numbers which can’t be uniquely specified by a formula in the first-order logical language of the real additive group, or numbers which can’t be uniquely specified by a formula in the first-order logical language of the real field with the logarithm operation, or numbers which can’t be uniquely specified by a formula in the second-order logical language of Peano Arithmetic, or what have you]. To say “can be described” is always relative to some notion of what form descriptions should come in and what one should be able to do with them.

[Rysto]

@RaftPeople

Just to add to your point, mainframes and minicomputers still have hardware for performing operations on base 10 values stored in a binary format (BCD, Packed and Zoned Decimal) so that currency calculations like those found in financial applications can be precise and fast (floating point is generally not).

Those of us who don’t have such hardware use cents as the unit instead of dollars to avoid the rounding problem.

[Napier]

Hellistal, I didn’t quite see the following statement laid out so simply and by itself, so would like to offer the following (better late than never) as the first tier answer to your OP:

Computer programmers almost never care whether a “real” number (that is, not an integer) is irrational or not. They usually care whether a number is a “real” (which they would call a “floating point” number or more often a “double”) versus an integer, and fairly often care how many bits it takes to represent it. But fairly often people or their programming environment defaults to treating “reals” as “IEEE double precision” numbers, and so they are just handling a “double” or even a “dbl”.

IEEE 754-2008 revision - Wikipedia has a good overview of the forms that non-integer numbers take in computing. In most programming, the things described at this link are hidden inside the “double” the programmer uses.

[ZenBeam]

@Hypnagogic_Jerk

I think what Indistinguishable is saying is that while there is no way to represent 1/3 or 1/7 exactly in decimal notation, just saying that “it’s impossible to represent them exactly” without specifying what other numbers you want to be able to represent is misleading at best. For example, 1/3 can be represented (exactly) as 0.1 in base 3, and even pi could be represented exactly in some systems.

You can switch to base 3, but then you can’t represent 1/4 exactly. You haven’t solved the problem, you’ve just moved it to a different place.

Whatever (finite) representation you want to use, most numbers still can’t be represented. The OP specifically asked about irrational numbers, but not being able to represent pi exactly isn’t because pi is irrational, and isn’t anything exceptional. Really, it’s the typical situation.