# Computer Science and Irrational Numbers **URL:** \ **Category:** Factual Questions\ **Created:** [August 19, 2009, 3:40am UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916 "2009-08-19T03:40:20Z")\ **Posts on this page:** 20\ **Page:** 4
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [August 20, 2009, 9:53pm UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/61 "2009-08-20T21:53:47Z")
> [@](#): > > I think it isn’t too unusual to treat a pair of numbers that, in principle, ought to get divided, but in practice are kept as integers for a while longer in the program. Once, when I was bored, I developed an algorithm for calculating rational approximations to square roots that used entirely integer math: At the end, it would output a numerator and a denominator. It’s probably not the most efficient routine, but it’s simple enough to be done in one’s head. ---
**Author:** ![ZenBeam](https://avatars.discourse-cdn.com/v4/letter/z/3ab097/32.png) [@ZenBeam](https://boards.straightdope.com/u/ZenBeam)\ **Post date:** [August 20, 2009, 10:12pm UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/62 "2009-08-20T22:12:26Z")
**Napier** , are you mixing up multiplication and division in your description, or does the algorithm really multiply to do division? ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [August 20, 2009, 10:29pm UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/63 "2009-08-20T22:29:56Z")
> [@Chronos](#): > > Once, when I was bored, I developed an algorithm for calculating rational approximations to square roots that used entirely integer math: At the end, it would output a numerator and a denominator. It’s probably not the most efficient routine, but it’s simple enough to be done in one’s head. Out of curiosity, what was it? One simple method I can think of for iteratively forming rational approximations of square roots of natural numbers without even much multiplication is the following: to take the square root of k, initialize your numerator and denominator to some first approximation, and then keep doing the following: simultaneously increment your numerator by k \* your old denominator, while incrementing your denominator by your old numerator. [Thus, move from n/d to (n+kd)/(n+d)]. As you say, it may not be the most efficient routine, but it’s simple and it works ok. Particularly if k is small, then you can just replace the multiplication step with repeated additions. [Though how often do you have to re-calculate the square root of 2? :)] The one problem is that the denominator will keep growing with this method, but you can divide common factors out of the numerator and denominator any time you feel like it. ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [August 20, 2009, 10:30pm UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/64 "2009-08-20T22:30:52Z")
I am really suprised no one here has mentioned **continued fractions**. Given arbitrary precision arithmetic, continued fractions are extremely capable of dealing with irrational numbers, and combinations of irrational numbers, extremely well with automatic error analysis. If precision is a concern, I see no real choice in the matter. Floating point is simply not usable for arbitrary precision irrationals. Some links: [HAKMEM -- CONTENTS -- DRAFT, NOT YET PROOFED](http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html) A good intro to cf arithmetic, but some implementation details are lacking and you will need to discover them on your own [Arithmetic with Continued Fractions](http://perl.plover.com/yak/cftalk/) a presentation that is lacking good followup–I imagine the lecture was superb [Continued fraction - Wikipedia](http://en.wikipedia.org/wiki/Continued_fraction) – well, it is wiki. There’s nothing wrong with the presentation but implementing continued fraction arithmetic should be based off the Gosper link, not recurrence relations mentioned in the wiki page (especially avoid any recurrence relation for general continued fractions) I don’t remember how I came across them but they’re very fun and pretty easily implemented in any high-level language. I found it easiest in lisps, though I know they’d probably be easy to use in mathematica, and probably haskell but I don’t know it. I guess python would be usable and java, too (bignums are a necessity). They’re the next best thing to symbolic math, IMO. **Edit** I should mention that continued fractions are capable of finite representations of any solution to a quadratic. (All irrationals are infinite continued fractions, but solutions to quadratics always have a repeating tail, so they can be represented exacty.) ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [August 20, 2009, 10:48pm UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/65 "2009-08-20T22:48:06Z")
> [@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 a fairly fundamental result. In fact, in a fininte amount of time, here’s some things you can’t do with computable real numbers _in all cases_: - tell if they’re equal - tell if they’re zero - tell if it is rational - find the first digit of a decimal expansion Weirdly, since you cannot tell if a number is zero _in general_, you cannot help but divide by zero in real computer arithmetic. Whoops! In a lot of cases, you can tell if a number is equal to another, zero, rational, or etc. But you cannot do it in _all_ cases (in finite time). ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [August 20, 2009, 11:08pm UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/66 "2009-08-20T23:08:51Z")
It’s even worse than that. You can’t decide _any_ nontrivial property of computable reals (in a suitable sense) in full generality. The general principle is that whatsoever is computable is continuous [again, an idea explored at great length in domain theory]; after all, whatsoever you output in a finite amount of time can only have depended on finitely amount of the input having been read in. So, on a standard representation of reals (one which respects their standard topology, such as the Dedekind cut based definition above), the only computable functions from them to booleans will have to be continuous functions from the reals to the discrete space with two elements; but as reals form a connected space, the only such functions are the constant ones. What one _can_ do is semidecide some properties (output “yes” just in case they hold, and run forever otherwise) or co-semidecide them (output “no” just in case they don’t hold, and run forever otherwise); the information as to whether a program halted or not corresponds to Sierpinski space rather than the discrete space on two elements. The semidecidable properties accordingly correspond to open subspaces and the co-semidecidable ones to closed subspaces. Thus, as the reals are Hausdorff (which just means the pairs of equal reals form a closed subspace of R^2), you can co-semidecide equality [that is, output “These are inequal” when the inputs are inequal, and run forever otherwise], and as a special case, co-semidecide whether an input is zero [that is, output “This is nonzero” when appropriate, and run forever otherwise]. Similarly, for finding the digits of a decimal expansion, one can computably output the digit just in case it is uniquely determined, and run forever if the digit isn’t uniquely determined (e.g., in the case of 0.50000… vs. 0.499999…). Again, the topology comes into play here: rather than considering functions into the discrete space on 10 elements [which, if nontrivial, must be discontinuous], we can instead use functions into a suitable gluing together of 10 copies of Sierpinski space. The rational numbers form neither an open nor a closed subspace, however, so rationality can neither be semidecided nor co-semidecided. The higher-order properties are even more amazing; you can computably determine, of a predicate on reals, whether it holds of the entire real interval [0, 1], this corresponding precisely to the fact that this interval is compact. ---
**Author:** ![Ruminator](https://avatars.discourse-cdn.com/v4/letter/r/b9bd4f/32.png) [@Ruminator](https://boards.straightdope.com/u/Ruminator)\ **Post date:** [August 20, 2009, 11:13pm UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/67 "2009-08-20T23:13:23Z")
> [@Uncertain](#): > > Only according to a twisted definition of “describe”. I say “There’s a number that can’t be described”, and you say “Sure it can: ‘ujn’ is my description of that number in a particular system of description”. Well, you haven’t described it. Now, if you will specify your method of description as well, then you can be said to have described it. But there are only a countable number of descriptions of methods. And so on. > > Back to representation. Nobody cares that for every real number there is a way of representing it by, for example, declaring that a byte containing 42 represents that real. The question is whether any system of representation can represent all of them, or some range of them (e.g., -1e300 to 1e300). The answer, even allowing for infinite (but countable) memory, is “no”. This sounds something like Cantor’s mathematical proofs of countable infinite sets instead of insights into how we’ve coded of numbers with bit representation. I don’t think your comments are helpful in terms of understanding computers because insisting that no system of representation can represent all numbers is the same constraint for pencil and paper. An sheet of paper of infinite length will still not allow you to write (represent) all possible numbers, even using compact scientific notation. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [August 20, 2009, 11:24pm UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/68 "2009-08-20T23:24:42Z")
> [@Indistinguishable](#): > > The higher-order properties are even more amazing; you can computably determine, of a predicate on reals, whether it holds of the entire real interval [0, 1], this corresponding precisely to the fact that this interval is compact. Sorry, I should be more explicit here: given a semidecidable predicate on reals, one can semidecide whether it holds of the entire real interval [0, 1]. A similar result is explained [here](http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs) (under the title “Seemingly Impossible Functional Programs”), but for Cantor space instead of the unit interval. The compactness of Cantor space amounts to the fact that, given a semidecidable predicate on the total functions from naturals to booleans, one can semidecide whether it holds universally. (Of course, everything I say is very sensitive to what representation of reals you use and what higher-order constructs you have available. But it’s all morally right.) ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [August 21, 2009, 12:18am UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/69 "2009-08-21T00:18:40Z")
Quoth **Indistinguishable** : > [@](#): > > Out of curiosity, what was it? > > One simple method I can think of for iteratively forming rational approximations of square roots of natural numbers without even much multiplication is the following: to take the square root of k, initialize your numerator and denominator to some first approximation, and then keep doing the following: simultaneously increment your numerator by k \* your old denominator, while incrementing your denominator by your old numerator. [Thus, move from n/d to (n+kd)/(n+d)]. As you say, it may not be the most efficient routine, but it’s simple and it works ok. Particularly if k is small, then you can just replace the multiplication step with repeated additions. [Though how often do you have to re-calculate the square root of 2?] Interestingly enough, this was exactly it. I don’t suppose I should be surprised that it was independently developed by someone else already; does this method have a name? ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [August 21, 2009, 12:45am UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/70 "2009-08-21T00:45:26Z")
Oh, I don’t know. I just made it up on the spot from your description. So I suppose probably lots of people have come up with it independently, once the idea occurred to them to try to do it. I was influenced by the [Babylonian method](http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method), though, which, while slightly different, at least has a nice, impressive-sounding name. ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [August 21, 2009, 1:06am UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/71 "2009-08-21T01:06:09Z")
There’s a very curious (and terribly inefficient) method of calculating roots I came across from a strange website. Roughly, it goes like this: Take your number, say, **n**. You wish to find the cube root of it. Construct three pairs[sup]_[/sup], a/b, c/a, b **n** /c ordered such that the first number is the smallest. The product of these three numbers is, trivially, **n**. Now compute the set (a+c)/(b+a), (c+b **n** )/(a+c), ( **n** _b **n** /( **n** \*c). The product of these three numbers is again equal to exactly **n**. Given that a/b \< (a+ b + c)/(d + e + f) \< c/f in the ordered set a/d, b/e, c/f, this iterative process converges (poorly) on our root. For higher roots, use more terms. If you implement this you will see it is very shitty but it is a neat curiosity. - – do not interpret these as rational numbers directly; i.e., _do not reduce them_ except on inspection to see how good the approximation is. ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [August 21, 2009, 1:13am UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/72 "2009-08-21T01:13:17Z")
> [@erislover](#): > > Now compute the set (a+c)/(b+a), (c+b **n** )/(a+c), ( **n** _b__n_\*/( **n** \*c). Now compute the set (a+c)/(b+a), (c+b **n** )/(a+c), (a **n** + b **n** )/(b **n** + c). ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [August 21, 2009, 2:44am UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/73 "2009-08-21T02:44:31Z")
> [@Indistinguishable](#): > > The point I am making is that there’s no point looking at a number itself and considering it intrinsically specifiable or unspecifiable. It’s only specifiable relative to some particular coding scheme. Is this not subject to some kind of diagonalization? ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [August 21, 2009, 2:46am UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/74 "2009-08-21T02:46:30Z")
I’m not sure what you mean by that question. What diagonalization are you thinking of? ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [August 21, 2009, 2:48am UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/75 "2009-08-21T02:48:51Z")
> [@Indistinguishable](#): > > I’m not sure what you mean by that. What diagonalization are you thinking of? I mean diagonalization-style argument that there most real numbers aren’t even nameable, period. Sorry… actually I will try to find the reference to be more clear. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [August 21, 2009, 2:55am UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/76 "2009-08-21T02:55:42Z")
Well, like I said, there’s no such thing as “nameable, period”. It’s easy to use a diagonalization argument to establish that, for any particular coding scheme (i.e., function from, say, finite bitstrings to real numbers), there is some real number not in its range. [In fact, the diagonalization argument shows us precisely how to define such a real number from the coding scheme]. This is the straightforward invocation of Cantor’s theorem everyone keeps referring to. But “For every coding scheme, there is some real number not in its range” is different from “There is some real number not in the range of _any_ coding scheme”. Now, one could again say “Suppose you have a system of describing coding schemes (i.e., maps from bitstrings to reals) themselves by finite bitstrings. Then there will be some real number not in the range of any of the coding schemes described by any bitstring in this system”. Sure. But again, that’s just one system of mapping bitstrings into coding schemes. The true statement “For any system of mapping bitstrings into (maps from bitstrings to reals), there is some real number not in the range of any of the maps in the range of this system” is different from “There is some real number such that for every system of mapping bitstrings into (maps from bitstrings to reals), that number is not in the range of any of the maps in the range of this system”. Nameability is always relative to some system of naming. There’s no such thing as objective nameability, at least not in any nontrivial sense; there’s only nameability in this language, nameability in that language, and so on. After all, what does nameability mean? It just means you’re in the range of some map from words to whatever. It would be silly to say of some number “This number is intrinsically not in the range”, irrespective of the map. You only speak of being or not being in the range _of some particular map_; there’s no “objective”, map-independent notion of what the “range” is. It’s a very silly, pedantic point, but it should be made. ---
**Author:** ![Uncertain](https://avatars.discourse-cdn.com/v4/letter/u/6a8cbe/32.png) [@Uncertain](https://boards.straightdope.com/u/Uncertain)\ **Post date:** [August 21, 2009, 4:04am UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/77 "2009-08-21T04:04:39Z")
> [@Ruminator](#): > > I don’t think your comments are helpful in terms of understanding computers because insisting that no system of representation can represent all numbers is the same constraint for pencil and paper. An sheet of paper of infinite length will still not allow you to write (represent) all possible numbers, even using compact scientific notation. That was my point. For integers or rationals you can do it (with pencil and paper or on a computer). For the reals you can’t. ---
**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\ **Post date:** [August 21, 2009, 9:11am UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/78 "2009-08-21T09:11:18Z")
> [@Indistinguishable](#): > > Sorry, I should be more explicit here: given a semidecidable predicate on reals, one can semidecide whether it holds of the entire real interval [0, 1]. > > A similar result is explained [here](http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs) (under the title “Seemingly Impossible Functional Programs”), but for Cantor space instead of the unit interval. The compactness of Cantor space amounts to the fact that, given a semidecidable predicate on the total functions from naturals to booleans, one can semidecide whether it holds universally. > > (Of course, everything I say is very sensitive to what representation of reals you use and what higher-order constructs you have available. But it’s all morally right.) Ha! I was wondering how long it would be before this came up before, when I saw you’d mentioned Cantor’s set. Escardo’s work is always interesting. ---
**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\ **Post date:** [August 21, 2009, 9:21am UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/79 "2009-08-21T09:21:14Z")
Also, what do you mean by your last sentence? I take it you’re hinting at the fact that higher-type computability isn’t a settled matter (i.e. there’s four or five different notions, none of them equivalent)? Or something else? ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [August 21, 2009, 9:50am UTC](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916/80 "2009-08-21T09:50:49Z")
Just that, that there are different possible accounts of higher-type computability. Though not even necessarily referring to anything particularly subtle or technical; even simple little things like whether one can carry out “parallel or” on Sierpinski space (or instead must remain strictly sequential) can change the strict validity of some of the things I said above. So, rather than taking the time to sit down and think about exactly what sort of setup was in my mind as making the things I said true, I just slapped a cover-my-ass statement on the end instead. 🙂 [Previous page](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916.md?page=3) [Next page](https://boards.straightdope.com/t/computer-science-and-irrational-numbers/506916.md?page=5)