Nice story. An even more powerful way to express numbers is as a continued fraction (https://en.wikipedia.org/wiki/Continued_fraction). You can express both real and rational numbers efficiently using a continued fraction representation.
As a fun fact, I have a not-that-old math textbook (from a famous number theorist) that says that it is most likely that algorithms for adding/multiplying continued fractions do not exist. Then in 1972 Bill Gosper came along and proved that (in his own words) "Continued fractions are not only perfectly amenable to arithmetic, they are amenable to perfect arithmetic.", see https://perl.plover.com/yak/cftalk/INFO/gosper.txt.
I have been working on a Python library called reals (https://github.com/rubenvannieuwpoort/reals). The idea is that you should be able to use it as a drop-in replacement for the Decimal or Fraction type, and it should "just work" (it's very much a work-in-progress, though). It works by using the techniques described by Bill Gosper to manipulate continued fractions. I ran into the problems described on this page, and a lot more. Fun times.
> You can express both real and rational numbers efficiently using a continued fraction representation.
No, all finite continued fractions express a rational number (for... obvious reasons), which is honestly kind of a disappointment, since arbitrary sequences of integers can, as a matter of principle, represent arbitrary computable numbers if you want them to. They're powerful than finite positional representations, but fundamentally equivalent to simple fractions.
They are occasionally convenient for certain problem structures but, as I'm sure you've already discovered, somewhat less convenient for a wide range of common problems.
> No, all finite continued fractions express a rational number
Any real number x has an infinite continued fraction representation. By efficient I mean that the information of the continued fraction coefficients is an efficient way to compute rational upper and lower bounds that approximate x well (they are the best rational approximations to x).
> They are occasionally convenient for certain problem structures but, as I'm sure you've already discovered, somewhat less convenient for a wide range of common problems.
I'm curious what you mean exactly. I've found them to be very convenient for evaluating arithmetic expressions (involving both rational and irrational numbers) to fairly high accuracy. They are not the most efficient solution for this, but their simplicity and not having to do error analysis is far better than any other purely numerical system.
> fundamentally equivalent to simple fractions.
This feels like it is a bit too reductionist. I can come up with a lot of example, but it's quite hard to find the best rational approximations of a number with just fractions, while it's trivial with continued fractions. Likewise, a number like the golden ratio, e, or any algebraic number has a simple description in terms of continued fractions, while this is certainly not the case for normal fractions.
That continued fractions can be easily converted to normal fractions and vice versa, is a strength of continued fractions, not a weakness.
Fractions do pose a non-trivial issue when they have to be converted to decimal representations. So that is indeed a weakness, although not a direct one. (You can argue the same for big decimals with a binary mantissa, for example.)
As to my understanding continued fractions can represent any number to as many decimal points as you need. So if you need π you can just calculate 2 decimal points and write 3.14
if you want to calculate π*10^9 you can calculate i.e. 11 digits and write 3141592653.58
I think this is what OP means and I am not sure why you do not agree.
But here continued fractions are used to progressively generate approximations to the true real number. So you have no control over denominator and as you mentioned repeated division is necessary for most numbers. In comparison, digit generation approach can be tailored to the output radix (typically 10). Division still does likely happen, but only in the approximation routine itself and thus can be made more efficient.
I agree though the article is about calculator app and user typically won't care if this is 10ns or 100ms to gen an output - it would look like an instant response anyway.
That's the issue, no? If you go infinite you can then express any real number. You can then actually represent all those whose sequence is equivalent to a computable function.
You are describing something that is practically more like a computer algebra system than a number system. To go infinite without infinite storage, you need to store the information required to compute the trailing digits of the number. That is possible with things like pi, which have recursive formulas to compute, but it's not easy for arbitrary numbers.
> That is possible with things like pi, which have recursive formulas to compute, but it's not easy for arbitrary numbers.
It is possible for pretty much all the numbers you could care about. I'm not claiming it is possible for all real numbers though (notice my wording with "express" and "represent"). In fact since this creates an equivalence between real numbers and functions on natural numbers, and not all functions are computable, it follows that some real numbers are not representable because they correspond to non-computable functions. Those that are representable are instead called computable numbers.
How would you get those numbers into the computer anyway? It seems like this would be a practical system to deal with numbers that can be represented exactly in that way, and numbers you can get at from there.
The way every other weird number gets into a computer: through math operations. For example, sqrt(7) is irrational. If you subtract something very close to sqrt(7) from it, then you need to keep making digits.
Continued fractions are very cool. I saw in a CTF competition once a question about breaking an RSA variant that relied on the fact that a certain ratio was a term in sequence of continued fraction convergents.
Naturally the person pursing a PhD in number theory (whom I recruited to our team for specifically this reason) was unable to solve the problem and we finished in third place.
Why unnecessarily air this grievance in a public forum. If this person reads it they will be unhappy and I'm sure they have already suffered enough from this failure.
Oh I don’t think of it like that - it was not a super serious competition and aside from some lighthearted ribbing there was certainly no suffering from any failure.
It's used with sarcasm / irony. In this use case, "naturally" implies the author intended to communicate one or more emotions from a certain narrow set of possibilities. That set includes:
- An eye-rolling, critical emotion - where they used up a valuable spot on the team to retain a person who ostensibly promises to specialize in exactly this type of problem, but instead they proved to be useless even in the one area they were supposed to deliver value.
- A emotion similar to that invoked by "c'est la vie". Sometimes this is resigned, sometimes this is playful, sometimes this is simply neutrally accepting reality.
Follow-up comments from the person who wrote it indicate they meant it in a playful sense of "c'est la vie", and indicated that the team found camaraderie and joy in teasing each other about it.
Sorry if this sounds a little bit like ChatGPT - I wrote it myself but at the point when one is explaining this kind of thing, it's difficult to not write like an alien or a robot.
It was an ironic twist of fate that we were preparing specifically for this type of challenge and, when presented with exactly what we had prepared for we failed to see the solution.
I think the other comment had an excellent breakdown of the various factors at play, so I will start by saying I fully endorse what was said there.
To highlight a key point: “naturally” is slightly humorous because it implies that while the outcome was ironic, it should almost be expected that an ironic bad thing happens. In addition, it signals my opinion on such situations more generally, whereas “ironically” is a more straightforward description of what happened that would add less humor and signal less of my personality.
I have been working on a new definition of real numbers which I think is a better foundation for real numbers and seems to be a theoretical version of what you are doing practically. I am currently calling them rational betweenness relations. Namely, it is the set of all rational intervals that contain the real number. Since this is circular, it is really about properties that a family of intervals must satisfy. Since real numbers are messy, this idealized form is supplemented with a fuzzy procedure for figuring out whether an interval contains the number or not. The work is hosted at (https://github.com/jostylr/Reals-as-Oracles) with the first paper in the readme being the most recent version of this idea.
The older and longer paper of Defining Real Numbers as Oracles contains some exploration of these ideas in terms of continued fractions. In section 6, I explore the use of mediants to compute continued fractions, as inspired by the old paper Continued Fractions without Tears ( https://www.jstor.org/stable/2689627 ). I also explore a bit of Bill Gosper's arithmetic in Section 7.9.2. In there, I square the square root of 2 and the procedure, as far as I can tell, never settles down to give a result as you seem to indicate in another comment.
For fun, I am hoping to implement a version of some of these ideas in Julia at some point. I am glad to see a version in Python and I will no doubt draw inspiration from it and look forward to using it as a check on my work.
It is equivalent to Dedekind cuts as one of my papers shows. You can think of Dedekind cuts as collecting all the lower bounds of the intervals and throwing away the upper bounds. But if you think about flushing out a Dedekind cut to be useful, it is about pairing with an upper bound. For example, if I say that 1 and 1.1 and 1.2 are in the Dedekind cut, then I know the real number is above 1.2. But it could be any number above 1.2. What I also need to know is, say, that 1.5 is not in the cut. Then the real number is between 1.2 and 1.5. But this is really just a slightly roundabout way of talking about an interval that contains the real number.
Similarly with decimals and Cauchy sequences, what is lurking around to make those useful is an interval. If I tell you the sequence consists of a trillion approximations to pi, to within 10^-20 precision, but I do not tell you anything about the tail of the sequence, then one has no information. The next term could easily be -10000. It is having that criterion about all the rest of the terms being within epsilon that matters and that, fundamentally, is an interval notion.
How do you work out an answer for x - y when eg x = sqrt(2) and y = sqrt(2) - epsilon for arbitrarily small epsilon? How do you differentiate that from x - x?
In a purely numerical setting, you can only distinguish these two cases when you evaluate the expression with enough accuracy. This may feel like a weakness, but if you think about this it is a much more "honest" way of handling inaccuracy than just rounding like you would do with floating point arithmetic.
A good way to think about the framework, is that for any expression you can compute a rational lower and upper bound for the "true" real solution. With enough computation you can get them arbitrarily close, but when an intermediate result is not rational, you will never be able to compute the true solution (even if it happens to be rational; a good example is that for sqrt(2) * sqrt(2) you will only be able to get a solution of the form 2 ± ϵ for some arbitrarily small ϵ).
> you will only be able to get a solution of the form 2 ± ϵ for some arbitrarily small ϵ
The problem with that from a UX perspective is that you won't even get to write out the first digit of the solution because you can never decide whether it should be 1.999...999something (which truncates to 1.99) or 2.000...000something (which truncates to 2.00). This is a well-known peculiarity of "exact" real computation and is basically one especially relevant case of the 'Table-maker's dilemma' https://en.wikipedia.org/wiki/Rounding#Table-maker%27s_dilem...
If one embraces rational intervals throughout, they can be the computational foundation and the ux could have the option of displaying the interval for the complete truth or, to gain an intuitive sense, pick a number in the interval to display, such as the median or mediant. Presumably this would be a a user choice in any given context.
As a fun fact, I have a not-that-old math textbook (from a famous number theorist) that says that it is most likely that algorithms for adding/multiplying continued fractions do not exist. Then in 1972 Bill Gosper came along and proved that (in his own words) "Continued fractions are not only perfectly amenable to arithmetic, they are amenable to perfect arithmetic.", see https://perl.plover.com/yak/cftalk/INFO/gosper.txt.
I have been working on a Python library called reals (https://github.com/rubenvannieuwpoort/reals). The idea is that you should be able to use it as a drop-in replacement for the Decimal or Fraction type, and it should "just work" (it's very much a work-in-progress, though). It works by using the techniques described by Bill Gosper to manipulate continued fractions. I ran into the problems described on this page, and a lot more. Fun times.