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.
Napier, are you mixing up multiplication and division in your description, or does the algorithm really multiply to do division?
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.
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 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 a presentation that is lacking good followup–I imagine the lecture was superb
Continued fraction - Wikipedia – 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.)
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).
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.
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.
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 (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.)
Quoth Indistinguishable:
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?
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, though, which, while slightly different, at least has a nice, impressive-sounding name.
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, bn/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+bn)/(a+c), (nbn/(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.
Now compute the set (a+c)/(b+a), (c+bn)/(a+c), (an + bn)/(bn + c).
Is this not subject to some kind of diagonalization?
I’m not sure what you mean by that question. 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.
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.
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.
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.
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?
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. 