This is an open-ended question. I just want to know anything interesting related to the topic.
I’ve got a limited math background (intro to analysis, topology), and I’m aware that computers use 1s and 0s to make shiny things on my screen. What I was wanting to know is how programmers deal with irrational numbers. Just throw out anything. Examples of practical work-arounds are great, but I’m also interested in any deeper theoretical aspects that could be explained.
Irrationals are just real numbers that can be represented as floating point numbers in a computer and manipulated as such.
Remember that base 10 can’t represent irrational numbers any better than base 2 - you just pick your desired accuracy and live with it.
I’m not sure if this is what you want, but you might look at this issue’s Computing Science column, The Higher Arithmetic in American Scientist magazine.
The author deals with the basics of fixed-point and floating-point and why they have problems with irrationals and with large numbers, and suggests schemes for new approaches that would, not solve, but alleviate the problems.
Really? How would you represent pi as a floating-point number?
Computers represent irrationals, and many rationals for that matter, only approximately, just as a pocket calculator does. Imagine keeping, say, ten digits of precision. It’s a lot like that, but the representation typically doesn’t use base 10.
Don’t all irrational numbers have a fair decimal approximation? Wouldn’t they just use that to whatever number of significant digits are relevant? I assume that at some level those would be treated as constants. I don’t know where (i.e., does Excel keep track of Pi, is it part of Windows, is it down in the BIOS…?).
What really freaks me out about computers and numbers is the concept of imaginary time. I was once setting my clock manually, ticked the wrong box, and, well, remember the Great Universe Inversion of '04? Sorry, my bad.
The standard C math libraries have a value of pi listed in the source code-- There’s a line that says
#define M_PI 3.14159265358979323846 /* pi */
(which is coincidentally the same number of digits I have memorized and manually put into all my programs)
So I imagine that it’s done at a very high level, with every program that uses pi in some way having its own copy. If you had the Excel source code, you could edit that line and re-compile it with some other value of pi.
It, of course, depends on the application.
It may be thought, because of exposure to what is most common, that computers can only deal with IEEE floating point numbers or arbitrary rational numbers or some such restricted thing, but this is wrong; computers can deal with all kinds of things, as long as you tell them the rules for how to represent them and manipulate them. One particularly easy thing to do is to come up with rules for how to represent arbitrary natural numbers as bitstrings and instructions for how to computably perform basic arithmetic upon them, and from there to represent integers and rational numbers is also particularly easy, but that doesn’t mean there aren’t other representations one could use which correspond to other kinds of numbers.
As the simplest example, suppose the only irrational numbers we really cared about were ones of the form a + b * sqrt(2), where a and b were rational. Then we could just represent such numbers as pairs of two rational numbers, and compute additions, multiplications, subtractions, and divisions in the obvious way upon them. (Sure, this representation doesn’t allow for, say, logarithms; if we wanted those, we’d have to pick a slightly different representation. The representation you pick will always have to be tailored to the operations you want to be able to carry out (for anything; not just numbers); thus, “It depends on the application”).
Speaking of which, we can also go much, much further than this toy example. As a preparatory analogy, suppose the question were “How can computers deal with countably infinite strings of 0s and 1s?”. Well, one non-naive way you could represent such a string is as (some representation of the code for) a function from natural numbers to bits. In a higher-order programming language, you could pass such functions around, store them in variables, evaluate them at particular arguments, and so forth, just as if it was any other basic data type.
(The caveat may be raised now: Whatever representation your higher-order programming languages uses internally for "functions from natural numbers to bits, it presumably doesn’t allow all such functions to be directly represented; only those functions which are computable. True; but in a strong sense, for most purposes, that’s all you really needed.)
In similar ways, one can represent real numbers using higher-order techniques. For example, one can represent a real number as a pair of an integral part and a function from natural numbers to digits, representing its decimal expansion, in the manner we are all familiar with. Or one could represent a real number as a function which takes in rational numbers as input, and outputs either “I’m higher than this”, or “I’m lower than this”, or just runs forever to signal “I’m equal to this” (this corresponds to the Dedekind cuts you probably learnt about in Intro to Analysis).
An interesting aspect that plays into all this is that various different mathematical definitions of real numbers which are classically equivalent have different computational properties; the things you can computably do with them are different, depending on the representation. [In a sense which can be made precise, the internal logic of “the computable world” is not classical logic, but rather a so-called intuitionistic logic]. For example, with the Dedekind-cut representation, addition is easy, but with the decimal-expansion representation, it’s not generally possible to carry out addition [suppose you were adding two digit streams, the first of which looked like 0.09999… so far and the second of which looked like 0.0000000… so far . What should the first digit after the decimal point of the output be? You can only make it 0 once you’re sure there’s never going to be a carry, and you can only make it 1 once you’re sure there will be a carry. But if both streams keep going like they are, you’ll never reach such certainty, and thus never know what to output].
Thus, the decimal expansion representation of real numbers is actually not a very good one.
In fact, there are strong topological reasons for this as well: there is a field called “domain theory” in which computer datatypes are associated with topological spaces, in such a way as that a nice correspondence is set up between computability and continuity of functions. According to domain theory, a countably infinite series of digits corresponds to a countably infinite product of discrete spaces with ten elements; this is homeomorphic to Cantor space, but not homeomorphic to the real numbers. On the other hand, the above-described Dedekind cut datatype would correspond to a topological space which is homeomorphic to the real numbers, and thus would work well for representing them (for this, it is crucial that we use running forever as the indicator of “I’m equal to this rational number”, rather than requiring an actual return value indicating this).
Anyway, I’m just rambling now, so I’ll cut it short, but perhaps I’ve touched on some interesting ideas of use to you.
In the IEEE single-precision representation of a real number, one bit is reserved for the sign, and it is set to 0 for a positive number and to 1 for a negative one. A representation of the exponent is stored in the next eight bits, and the remaining twenty-three bits are occupied by a representation of the mantissa of the number.
pi = 3.14159265 or 11.00100100001111110110 in fixed point binary.
From above, I believe that this is pi in single-precision: 00000000111001001000011111110110
Surely, friedo’s point was that that value was not exactly equal to π. Which is true; if, for some reason, you wanted a representation which did not force you to approximate π with some nearby dyadic value, you would not want to use the IEEE floating-point datatype; you would choose to use a different representation. (What representation you chose to use would depend, as always, always, upon exactly what operations you were interested in.)
This technique would seem to correspond to what’s explained on the third page of Exapno’s cite:
Fascinating.
Yes, that’s right. But one thing I want to emphasize is that it’s silly and misleading to say things like “there’s no hope of expressing the complete value of pi or √2 in a finite machine”, firstly because talking about what it means to represent a value is meaningless without also talking about what other values one wants to represent alongside it and what kinds of operations one would like to perform upon them, and secondly because, as even the author demonstrates next, in this particular case, there are very simple ways to represent all the usual real-valued constants and operations (including pi and √2) on a finite machine.
I know, I know, the author just meant “there’s no hope of writing out the entire decimal expansion of pi or √2 in finite space”, but it’s the kind of talk that leads people astray, to speak as though expressing a number automatically means writing out its decimal expansion, as opposed to some other representation.
Maple and Mathematica and programs of their ilk treat all of the mathematical constants you’ve heard of (and many of the ones you haven’t) symbolically. So if you ask it what the square root of 8 is, for instance, it’ll tell you it’s 2√2 , not that it’s 2.828427125 , and if you ask it for e^(pi*i), it’ll tell you -1 .
Yes, we all very know what kind of very person you am. 
[Insult the Computer Scientist, will you? :mad:]
This is true for most numbers. You can’t represent 1/3 or 1/7 exactly. If you multiply (or divide or even add) two exact IEEE numbers, the true result also can’t always be exactly represented using the same precision IEEE numbers, because there won’t be enough bits. There’s no real point in singling out pi as being unable to be exactly represented.
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.
Right. Anything we can write down and work with on paper, we can program a computer to work with, by “teaching” it the rules we use.
But (IIUC) there are lots of irrational numbers that we can’t describe exactly, in any way: there’s no finite specification for them.
Heh. Nouns, adjectives, it’s so hard to keep them straight…
I did? I didn’t mean to, whatever I did. I’d like to think I just critiqued, without insulting.
You have to be very careful when you do math in a computer. Those little rounding errors can get you.
In the first gulf war, the patriot missile systems in Dharan failed miserably, where patriots elsewhere did fine. This ended up being basically due to a rounding error.
You expect problems representing something like pi in a computer, but most folks don’t expect problems representing 1/10th. In base 10, 1/10th is just 0.1. It’s a nice, simple, number. In binary, 1/10th is 0.0001100110011 with the 0011 part infinitely repeating. Obviously, the infinitely repeating part gets truncated at some point.
This is exactly what happened in the patriot. It was trying to count in 1/10th second intervals, so the longer the system ran, the greater it’s time error became. Patriot batteries elsewhere were shutting down the system for maintenance periodically. In Dharan, they just let it run, so it accumulated a huge time error.
The way the patriot works is that it sees a signal. It then predicts where it should see the next signal, based on time, speed of the target, etc. Because the time calculation was wonky, the patriot would look in the wrong area of the sky for the next signal, and when it didn’t find the incoming missile (no surprise, it’s not looking in the right place) it assumed a false target and gave up. Oops. It wasn’t a false target.
Those little bits can get you.
(This is from memory, so I may have the details a bit off, but it’s the right basic idea).