6 ms·

Nice story. An even more powerful way to express numbers is as a continued fraction (https://en.wikipedia.org/wiki/Continued_fraction https://en.wikipedia.org/w

Nice story. An even more powerful way to express numbers is as a continued fraction (https://en.wikipedia.org/wiki/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 https://perl.plover.com/yak/cftalk/INFO/gosper.txt. I have been working on a Python library called reals (https://github.com/rubenvannieuwpoort/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.

naniwaduni 2y ago
> 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.
- layer8 2y ago
  The linked paper by Bill Gosper is about potentially infinite continued fractions with potentially irrational symbolic terms.
- rustybolt 2y ago
  > 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.
  - lifthrasiir 2y ago
    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.)
    - npodbielski 2y ago
      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.
      - lifthrasiir 2y ago
- SkiFire13 2y ago
  > finite 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.
  - pclmulqdq 2y ago
    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.
    - deleted 2y ago
      [deleted]
    - tiagod 2y ago
      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.
      - pclmulqdq 2y ago
        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.
    - SkiFire13 2y ago
      > 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.
dan-robertson 2y ago
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?
- rustybolt 2y ago
  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 ϵ).
  - zozbot234 2y ago
    > 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_dilemma https://en.wikipedia.org/wiki/Rounding#Table-maker%27s_dilem...
    - jostylr 2y ago
      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.
LPisGood 2y ago
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.
- jwilk 2y ago
  Sounds a bit like https://en.wikipedia.org/wiki/Wiener%27s_attack https://en.wikipedia.org/wiki/Wiener%27s_attack. (It's not a good article when it comes to the attack details, unfortunately.)
  - LPisGood 2y ago
    I gave a presentation on that attack in a number theory class - it made not getting that problem sting a little more.
- throwaway2037 2y ago
  What do you mean by "[n]aturally" here?
  - LPisGood 2y ago
    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.
    - throwaway2037 2y ago
      Why not just say "ironically"?
      - LPisGood 2y ago
        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.
luxuryballs 2y ago
is that how that kid calculated super long pi?
jostylr 2y ago
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 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 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.
- lanstin 2y ago
  That sounds kind of similar to Dedikin cuts but crossed with ordered sequence < and > the real? Cool web site.
  - jostylr 2y ago
    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.

naniwaduni 2y ago

> 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.

layer8 2y ago
The linked paper by Bill Gosper is about potentially infinite continued fractions with potentially irrational symbolic terms.
rustybolt 2y ago
> 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.
- lifthrasiir 2y ago
  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.)
  - npodbielski 2y ago
    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.
    - lifthrasiir 2y ago
SkiFire13 2y ago
> finite 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.
- pclmulqdq 2y ago
  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.
  - deleted 2y ago
    [deleted]
  - tiagod 2y ago
    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.
    - pclmulqdq 2y ago
      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.
  - SkiFire13 2y ago
    > 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.

dan-robertson 2y ago

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?

rustybolt 2y ago
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 ϵ).
- zozbot234 2y ago
  > 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_dilemma https://en.wikipedia.org/wiki/Rounding#Table-maker%27s_dilem...
  - jostylr 2y ago
    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.

LPisGood 2y ago

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.

jwilk 2y ago
Sounds a bit like https://en.wikipedia.org/wiki/Wiener%27s_attack https://en.wikipedia.org/wiki/Wiener%27s_attack. (It's not a good article when it comes to the attack details, unfortunately.)
- LPisGood 2y ago
  I gave a presentation on that attack in a number theory class - it made not getting that problem sting a little more.
throwaway2037 2y ago
What do you mean by "[n]aturally" here?
- LPisGood 2y ago
  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.
  - throwaway2037 2y ago
    Why not just say "ironically"?
    - LPisGood 2y ago
      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.

luxuryballs 2y ago

is that how that kid calculated super long pi?

jostylr 2y ago

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 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 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.

lanstin 2y ago
That sounds kind of similar to Dedikin cuts but crossed with ordered sequence < and > the real? Cool web site.
- jostylr 2y ago
  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.