irrational
An irrational number cannot be represented as a fraction composed of integer parts. EG PI, e.
There are an infinite number of irrational numbers between each rational number, and there are an infinite number of rational numbers. Which you might think means there are more irrational than rationals [ CL feels compelled to point out that this is not a correct proof; notice, for example, that between each two distinct irrationals there are infinitely-many rationals]. See Cantor for the transfinite numbers.
Any number whose decimal representation recurs at any point is rational. This is proved since:
Make PRE = the decimal representation up to where the number starts repeating, and replace the repeating part with 0000... then the number PRE can be represented as PRE*1000..../1000.... (ie a fraction, using as many digits in the multiplier as needed to make PRE an integer). Eg 3.4352141414... = 34353/10000 + 0.141414/10000....
The repeating part can be made into a fraction by taking the repeat and dividing by 99999.... (as many 9s as are in the repeated part).
For example: .77777... = 7/9. 0.7171.. = 71/99; 0.142857142857... = 142857/999999, .00000717171... = 71/99/100000 and so on. So any number which has a recurring representation can be written as a sum of 2 fractions: Val = PRE + rept/999.... and is therefore a rational number.
Well that is a simple version of the proof, but largely correct.
In finite digit arithmetic (eg in a coding language such as C++ or Fortran or TCL) there are only a finite number of digits representing a value. Most computer languages therefore use rational numbers ONLY, and operate on rational numbers too. Thus computers really work in integers, though some algebra packages such as Mathematica, Maple etc do have some understanding of irrationals.
AMG: Accurately representing irrational numbers on finite computers requires some creativity. The obvious encoding is to store the sign, magnitude, and binary exponent (or implicitly understand the exponent to be 0 or -16 or some such for integer or fixed-point storage), but no combination of integral magnitude and integral exponent can exactly represent any irrational number. But there are ways around this...
One possibility is retaining the algebraic expression that generates said number, much like we do with pencil and paper. Let's say we're writing a calculator program using two-digit fixed point decimal encoding. First the user enters 2, so it remembers 2.00. Next the user hits sqrt, and the calculator stores 1.41. Lastly, the user presses sqr, resulting in 1.98. Huh? The calculator would have been correct if it instead had stored sqr(sqrt(2)).
Another is remembering not the number but rather its properties, the same way we mentally handle pi (for example). I know that when I work with pi I almost never think to myself "3.1415"; instead pi is pi, sin(pi) is 0, tan(pi/2) is undefined, etc. Or for sqrt(2): sure it comes close to 1.414, but more importantly sqr(sqrt(2)) is 2, for any value of 2 :^) .
All this leads to a computer algebra system.
So I wonder, is there a number that cannot even be expressed by a finite series of algebraic manipulations? How about cos(cos(...(cos(cos(0.5)))...))? It tends to, but is not equal to 0.739085133215. I don't know how to express it as a limit or an iterative expression (summation, product, or even an integral), yet still I have managed to enter it into my tkcon by turning it into a chunk of code. Since it doesn't terminate, it doesn't qualify as an algorithm, and it's impossible to manipulate in a finite amount of time. A clever fellow may be able to devise a usable limit (not just "x_0 = 0.5; x_i = cos(x_(i - i)); limit of x_i as i->infinity", which only restates the original expression), yet some other clever fellow might prove the nonexistence of a handy closed-form limit expression. If such a thing is proven, what does that say about our friend the infinite cosine? Or the computer algebra system? Does this mean there are numbers computers simply cannot manipulate? Or is there a way to master the infinite? These are just thoughts...
Update: The moment I hit the Save button I realized this particular "infinitely complex" expression really can be distilled into something more workable: It is equal to the (a?) value of x which solves cos(x)=x. Now I'm embarrassed. The Save button is a teacher both wise and cruel. Only the Send button is more harsh. :^)
tomas 2013-12-25 Actually, there are such nasty irrationals. See, e.g. Chaitin's "constant" http://en.wikipedia.org/wiki/Chaitin%27s_constant . "Real" real numbers are quite weird.
EKB No reason to be embarrassed if you rediscover something interesting (IMHO). First, I think you've answered your own question -- yes, indeed, there are equations that have no closed-form solution. Also, you have implemented a reasonable (but not, I think, optimal) solution algorithm. Graphically, what you were doing is tracing the green line in the following diagram, which has plots of y=cos(x) and y=x:
I think by looking at the graph you can convince yourself that 1) there is a unique, positive solution to cos(x) = x and 2) it doesn't matter what your starting point is (it doesn't have to be 0.5). Another way to cast the problem you were working on is: what is the solution to cos(x) - x = 0? There are well-established algorithms for finding zeros of functions (e.g., Newton's method), but I don't know which algorithms are better in which situations.
AM (27 march 2008) The algorithm above to find the solution of cos(x) = x is known as a Picard iteration. It converges for starting values "close" enough to the solution if the derivative of the function at the solution has an absolute value less than 1. The convergence criteria for such iterative algorithms provide a whole new world of mathematical objects (the classic example is Newton-Raphson iteration for the equation x^3 = 1 - the area for which the convergent is 1 - or one of the two complex roots for that matter - is a complicated fractal).
AMG: By the way, 1. pi is irrational, 2. pi is the ratio between a circle's diameter and its circumference, therefore 3. no circle can have rational values for both diameter and circumference. Just thought I'd throw that in there. :^)
AM (27 march 2008) Another - more philosophically interesting - type of number is this (beloved by constructivistic mathematicians):
Define a number x as follows: x is the decimal expansion of sqrt(2) up to the point where the expansion contains 10 consecutive 1's (or something similar).
Such a number is perfectly defined, but it is very hard to determine whether it is rational or not. If the decimal expansion of sqrt(2) does contain such a sequence, x is rational. If it does not, x is equal to sqrt(2) and therefore irrational.
But this has little to do with ordinary programming problems ...
AMG: I wonder if it's theoretically possible to make a non-constructive proof of such a number's rationality. Sure, a constructive proof (is that the right term?) will just demonstrate that the zillionth digit of sqrt(2) is the first in a sequence of at least ten 1's; what's the challenge in that? :^) The really fun thing would be a proof that says: sqrt(2) must have a sequence of ten 1's, but I don't have to show you where it is in order to convince you that it can't help but be there.
Going the other direction, proof of such a number's irrationality cannot be done through demonstration. Right?
See http://en.wikipedia.org/wiki/Feynman_point for a sequence of six 9's in the decimal expansion of pi. In the article, it mentions that nine 9's can be found starting at digit #564,665,206.
HAL0000 - 2012-06-01 14:06:26
History of Pi (fiction)
Pi is irrational because Euclidean geometry and Peano arithmetic were integrated. The irrational numbers were generated during the integration process. The number used to allow the integration was zero.
The three instruments of Euclidean geometry are the stylus, the straight edge and the compass. Geometry relates to figures than can be drawn with these instruments plus the rules of using the instruments. Arithmetic is based upon the use of the stylus plus rules for using the stylus. Rational numbers can be drawn by using a symbol for repeat or a symbol for continue with no change. An interesting question is whether or not a figure drawn in geometry can be matched with a figures drawn in arithmetic. The answer is no. Irrational numbers cannot be drawn in arithmetic, no matter what numeration is used.
Arithmetic was designed to represent change in quantity, for example, two apples versus seven apples. Perhaps it takes three seconds to move five apples to another box. The time period of the physical movement is not included. Time is assumed to be represented by the number one, that is, one transaction.
Geometry was designed to represent movement, the wheel. Immediately people noticed that time was a factor. The wheel can turn fast or slow. If one rotation is represented as one transaction, then transactions are not all equal in time. Most importantly, the transaction rate can change from one second to the next.
Arithmetic was designed for one dimension, and geometry was designed for two dimensions. The two designs met when the unit square and unit circle were analyzed in detail. The Pythagorean theorem was written in two dimensions. The lengths were measured in one dimension. The square root was the integration operation from two dimensions to one dimension.
Consider the increments: x>x+dx, and x^2>x+2(dx) +(dx)(dx) In the limit toward zero, arithmetic can accomodate the 2 in the middle term but cannot accommodate the additional dx in the third term. That is one dx too many. Geometry can accommodate the third term. In calculus these refer to the ordinary first and second derivatives.
If the limit toward zero is not taken then dx is an extremely small countable number and (dx) is discarded, which, by the way, is only allowed by the addition of another axiom, usually unmentioned. Note that discarding a very small number is not the same as setting it equal to zero because zero has different axioms attached to it.
Zero in the Peano axioms is defined to be a natural number. However, some numbers are more natural than others, and zero is the most unnatural of the naturals. Zero represents the unseen apple remaining when all of the other natural apples have been removed from the apple box. I like to draw the apple box for zero as {}. The apple box with an unseen apple in it is drawn like this: {0}. A well ordered apple box has a corrogated bottom with a place for each unseen apple and each unseen apple in its place: {0,0}. In three dimensions I have a crate. In four dimensions I have a truck full of crates moving across town. In the world of the farmer empty crates are not all the same and have to be handled. In the world of the mathematicians only one empty crate {} exists.
The irrational numbers appear when the government mandates that a partition must be placed across the diagonal of the crate. In compliance the crate is redesigned, otherwise the red apples will have to be sliced along the diagonal with half an apple on each side of the partition. For health reasons cutting the apples is illegal. The new design must avoid apple fractionation. The first design is a zigzag partition. This works perfectly except for gourmet apples. Gourmet apples are so expensive that only one gourmet apple is in one gourmet apple box and still must have one government mandidated gourmet partition.
The first design for gourmet apple boxes places an unseen apple on one side of the partition and the gourmet apple on the other side. By law the unseen apple is allowed in the box, but it cannot be sold. Unfortunately the apple container is now too big. Half of the space is wasted. The box {} of the invisible apple is taking up half the space. Obviously it is time to lobby and to have the law changed.
The new law states that the mandated partition may be part of the {} box of the invisible apple. The {} is flattened and redesigned so that it begins at one corner fits around the apple and ends at the diagonal corner. Obviously this does not work because the flattened {} does not extend along the diagonal line segment as required by law. Back to the lobby.
The next law allows the box {} itself to be considered part of the invisible apple; hence, it too is invisible. Now {} is both flattened and straightened so that it moves along the diagonal line segment and has the invisible apple in it {0}. A label in added to the gourmet apple box. "This box contains one irrational partition as mandated by Federal Law." This solves the problem and is a good example of government and industry working together to solve problems in a free society.
The diagonal of the square is the radius of the circle. Multiply by 2, and the diameter is also irrational. Is the circumference rational or irrational. It does not matter. One irrational number contaminates all of subsequent arithmetic. Pi is irrational by travelling in the bad company of the square root of two.
End