5 ms·

If you do not care about speed, you can get not arbitrary-precision (static number of significant digits, set upfront) but exact (dynamic number of significant

by mci 6y ago

If you do not care about speed, you can get not arbitrary-precision (static number of significant digits, set upfront) but exact (dynamic number of significant digits, as large as you wish) results. Under the hood, your expressions will be directed acyclic graphs of lazy generators, each generator coresponding to a mathematical operation or function. Here is a Python library that employs continued fractions to this end: [0]. You can pull successive partial quotients of the result from the root node of the dag. Whenever any node needs more precise input to deliver more precise output, it pulls a partial quotient from its argument(s). Full disclosure: I wrote the original version of the library 13.5 years ago. Here are the slides from my talk about it: [1]. [0] https://github.com/AdamPrzybyla/python-cf https://github.com/AdamPrzybyla/python-cf [1] https://marcinciura.files.wordpress.com/2019/10/cf-slides.pdf https://marcinciura.files.wordpress.com/2019/10/cf-slides.pd...

ben509 6y ago
Very cool. I've seen some libraries around for continued fractions, but this is the only one that's reasonably complete.
enriquto 6y ago
How do you check if two different acyclic graphs of lazy generators represent the same number? I do not see how this can be possible. Wouldn't that amount to prove a lot of hard math theorems (e.g, riemann hypothesis)?
- nextaccountic 6y ago
  You are right that it isn't possible. Equality on real numbers is undecidable.
  - enriquto 6y ago
    Thus if you use such a library, a simple line of code like if (x < 1): may halt, trying to compute x to a higher and higher precision?
    - VMG 6y ago
      I think you meant to say "may not halt"
      - enriquto 6y ago
        Aren't both sentences synonymous? The problem is that the checking a condition "x<0" can take an arbitrarily long time to check, and maybe even be undecidable.
- mci 6y ago
  See slides 43–60 and 72. A node emits ∞ as the partial quotient after 100 resultless iterations. The threshold is configurable. In particular, see lines 184–187 of cf.py: # Idealistically inclined folks, who would prefer their # computations to hang rather than to yield a heuristic result, # can achieve this effect by setting accuracy to a negative # value.
  - enriquto 6y ago
    Seems reasonable, but then this is not "exact" precision as you claim, but "very large" or "dynamic precision". Saying that the precision of a real number is exact is very misleading, as it evokes inevitably an automatic theorem-proving context.
    - mci 6y ago
      Thanks, "dynamic" is a good term. "Very large" would not describe it well: for non-contrived irrational numbers, the chance of an improper rounding to a rational is much smaller than the chance of a meteorite strike in your room within the next five minutes (slide 60).
      - enriquto 6y ago
        but then again, the set of "non-contrived irrational numbers" is certainly of measure zero
        mci 6y ago
        This discussion would really go better if you followed the links. See lines 92–96 of cf.py: By the # Gauss-Kuzmin theorem [5, 6], a partial quotient in the # continued fraction expansion of almost every number exceeds # 1e+31 with probability log2(1+1e-31) =~= 1e-31/ln(2) =~= # 1.5e-31.
        enriquto 6y ago
        I'm somewhat familiar with Gauss-Kuzmin theorem. If I understand it well, it means that large partial quotients are rare in most numbers. This is fairly intuitive, and conforming to the experiences of anybody who has done practical computations of continued fractions, as you certainly have. Notice that this result does not say that most numbers have bounded partial quotients. In fact, a classical result in diophantine approximation theory, if I recall correctly, says that the set of numbers whose partial fractions are bounded (called badly aproximable numbers) is of Lebesgue measure zero. Thus, if your system represents real numbers by sequences of bounded partial quotients, then it can only represent a negligible (but uncountable) set of real numbers. A "random" number in [0,1] will certainly have an unbounded sequence of partial quotients (i.e., with probability 1).
SloopJon 6y ago
I've been noodling with Hans Boehm's constructive reals package since the "Toward an API for the Real Numbers" post: https://news.ycombinator.com/item?id=24700705 https://news.ycombinator.com/item?id=24700705 The Android calculator app. got some nice usability improvements by using a combination of rationals, as described in this story, and recursive (aka constructive or computable) reals. A previous post on Microsoft's calculator brought my attention to an old package it uses called Ratpack (aka ratpak), another implementation of rationals: https://news.ycombinator.com/item?id=19321217 https://news.ycombinator.com/item?id=19321217 It has some nice properties for use in a calculator, but it can be quite slow. When I come across a library with, shall we say, an exotic numeric representation, it's nice to have a library of mathematical functions included. I see that python-cf indeed includes a solid batch.

by mci 6y ago

ben509 6y ago

Very cool. I've seen some libraries around for continued fractions, but this is the only one that's reasonably complete.

enriquto 6y ago

How do you check if two different acyclic graphs of lazy generators represent the same number? I do not see how this can be possible. Wouldn't that amount to prove a lot of hard math theorems (e.g, riemann hypothesis)?

nextaccountic 6y ago
You are right that it isn't possible. Equality on real numbers is undecidable.
- enriquto 6y ago
  Thus if you use such a library, a simple line of code like if (x < 1): may halt, trying to compute x to a higher and higher precision?
  - VMG 6y ago
    I think you meant to say "may not halt"
    - enriquto 6y ago
      Aren't both sentences synonymous? The problem is that the checking a condition "x<0" can take an arbitrarily long time to check, and maybe even be undecidable.
mci 6y ago
See slides 43–60 and 72. A node emits ∞ as the partial quotient after 100 resultless iterations. The threshold is configurable. In particular, see lines 184–187 of cf.py: # Idealistically inclined folks, who would prefer their # computations to hang rather than to yield a heuristic result, # can achieve this effect by setting accuracy to a negative # value.
- enriquto 6y ago
  Seems reasonable, but then this is not "exact" precision as you claim, but "very large" or "dynamic precision". Saying that the precision of a real number is exact is very misleading, as it evokes inevitably an automatic theorem-proving context.
  - mci 6y ago
    Thanks, "dynamic" is a good term. "Very large" would not describe it well: for non-contrived irrational numbers, the chance of an improper rounding to a rational is much smaller than the chance of a meteorite strike in your room within the next five minutes (slide 60).
    - enriquto 6y ago
      but then again, the set of "non-contrived irrational numbers" is certainly of measure zero
      - mci 6y ago
        This discussion would really go better if you followed the links. See lines 92–96 of cf.py: By the # Gauss-Kuzmin theorem [5, 6], a partial quotient in the # continued fraction expansion of almost every number exceeds # 1e+31 with probability log2(1+1e-31) =~= 1e-31/ln(2) =~= # 1.5e-31.
        enriquto 6y ago
        I'm somewhat familiar with Gauss-Kuzmin theorem. If I understand it well, it means that large partial quotients are rare in most numbers. This is fairly intuitive, and conforming to the experiences of anybody who has done practical computations of continued fractions, as you certainly have. Notice that this result does not say that most numbers have bounded partial quotients. In fact, a classical result in diophantine approximation theory, if I recall correctly, says that the set of numbers whose partial fractions are bounded (called badly aproximable numbers) is of Lebesgue measure zero. Thus, if your system represents real numbers by sequences of bounded partial quotients, then it can only represent a negligible (but uncountable) set of real numbers. A "random" number in [0,1] will certainly have an unbounded sequence of partial quotients (i.e., with probability 1).

SloopJon 6y ago

I've been noodling with Hans Boehm's constructive reals package since the "Toward an API for the Real Numbers" post: https://news.ycombinator.com/item?id=24700705 https://news.ycombinator.com/item?id=24700705 The Android calculator app. got some nice usability improvements by using a combination of rationals, as described in this story, and recursive (aka constructive or computable) reals. A previous post on Microsoft's calculator brought my attention to an old package it uses called Ratpack (aka ratpak), another implementation of rationals: https://news.ycombinator.com/item?id=19321217 https://news.ycombinator.com/item?id=19321217 It has some nice properties for use in a calculator, but it can be quite slow. When I come across a library with, shall we say, an exotic numeric representation, it's nice to have a library of mathematical functions included. I see that python-cf indeed includes a solid batch.