5 ms·

The COMPUTABLE-REALS [0] package from the article is interesting because it lets you change the precision even after a computation is “performed”. It basically

The COMPUTABLE-REALS [0] package from the article is interesting because it lets you change the precision even after a computation is “performed”. It basically builds up lazy representations of computations that can (internally) recompute to any precision specified. You do all of your arithmetic as normal and only until you need to do something with an actual decimal representation do you “request” it. You grab the actual approximation as a decimal number with the APPROX-R function, which provides as many digits as you please. There is no need to re-run all of your code which produced the (computable) number in the first place to reapproximate at higher precision. This all directly falls out of a mathematical formalism called “computable real numbers” [1] which are the (countable!) set of real numbers for which an algorithm exists to compute the digits to any desired precision. (Usually binary digits are the standard way to write out the definition of a computable number.) [0] https://github.com/stylewarning/computable-reals https://github.com/stylewarning/computable-reals [1] https://en.m.wikipedia.org/wiki/Computable_number https://en.m.wikipedia.org/wiki/Computable_number

chipguy 7y ago
That's interesting because that's how humans actually do algebra. Who cares about the decimal expansion of some irrational if in the end we divide it by itself for example.
- gjm11 7y ago
  Unfortunately, most infinite-precision real-number implementations (including the one here, I bet, but I haven't checked) will not recognize that you're dividing something by itself. So you'll get a super-inefficient implementation of the number 1 :-). [EDITED to add:] I checked; the implementation here indeed won't recognize that you're dividing something by itself. For the avoidance of doubt, nor do I think trying to recognize such things would be an improvement. (Also, if you ask for e.g. the digit immediately preceding the decimal point, you will wait for ever because no amount of precision will enable the implementation to tell whether your number is just less than 1 or 1 or just over. So don't ask it for that, ask it for a very close approximation and draw your own conclusions.)
  - jjnoakes 7y ago
    Also note that dividing something by itself is not necessarily 1.
    - jgalt212 7y ago
      I dunno, I think 0/0 is 1, but I cannot be sure. https://www.wolframalpha.com/input/?i=lim+x%2Fx+as+x-%3E0 https://www.wolframalpha.com/input/?i=lim+x%2Fx+as+x-%3E0
      - jolmg 7y ago
        You can say 0/0 is 1, but it's also 2 and 3 and every other number, since x*0=0 for any x. That's why it's undefined.
        all2 7y ago
        Could we define it as a one to many function that maps from 0/0 to the set of all Complex numbers? If 0/0 = Q, then 0 = 0 × Q. So, we get to define this operation. If we treat 0 as an integer, then we could treat Q (a set) like a 1 x inf. matrix and we have scalar multiplication. But 0 × Q = [0]' × Q So 0 can be an infinite set of 0. This is cyclical, I know. This cyclical nature leads to an interesting effect if we also define integer division. Try this around 0 in Q. We could also define the × as an inner (dot) product, or as a cross product. This is fun!
        ngcc_hk 7y ago
        Is there a number set larger than a complex number? If so you can’t map to any concrete thing as it is really anything. And I guess it is easy to define one more dimension of number.
  - reikonomusha 7y ago
    The notion of "by itself" is dubious in this context at best. You can only check up to finite precision that two numbers are equal. For something more, you need computer algebra, which is a tall order. Even if you have computer algebra, math says it's not possible to check that arbitrary expressions are equal. It's an undecidable problem. So with that, I don't fault a computable reals package not being able to detect that x == y in an expression x/y.
jolmg 7y ago
Sounds similar to how Haskell does all number computations by default. When you do 1/3 for example it leaves the types generic/ambiguous using typeclasses until it finds something to refine them. 1/3 could be a floating-point number, or a fixed-point number, or a rational (datatype holding the numerator and denominator), or any other user-defined datatype. You could put these computations in a library, keeping their types generic with typeclasses, and a user of your library can use their own number datatypes. Your library would automatically support that datatype in your number computations.
- nestorD 7y ago
  No really, computable real store the AST of the computation to lazily compute digits as they are needed (which is an interesting idea but memory hungry at scale) while Haskell approach is more akind to a form of general type deduction. Note that I first meet computable numbers in Haskell : https://wiki.haskell.org/Applications_and_libraries/Mathematics#Dynamic_precision_by_lazy_evaluation https://wiki.haskell.org/Applications_and_libraries/Mathemat...
  - mbrock 7y ago
    http://hackage.haskell.org/package/exact-real-0.12.2 http://hackage.haskell.org/package/exact-real-0.12.2 I’ve used this package to get exact real computations in Haskell which get evaluated at n bits when needed for printing or equality checking etc.
mehrdadn 7y ago
I don't understand how this is supposed to work. For one thing iterative code wouldn't even do the same number of iterations when you change the desired precision, so merely plugging in higher precision numbers wouldn't give the higher precision approximation you'd be looking for. You'd have to actually re-execute the entire code with higher precision numbers so that intermediate control flow decisions use those numbers instead too, right?
- Veedrac 7y ago
  Generally, precision is pulled on-demand, as it is needed. If you compare two values as x < y, x and y will be evaluated to higher and higher precision until the answer is unambiguous. This can be an issue if the values are equal, since they often cannot be proven to be equal, so the evaluation may just outright fail to terminate.
  - mehrdadn 7y ago
    That doesn't address the situation I outlined?
    - rocqua 7y ago
      You store the expression. Because that expression is a computable real, you can calculate it to arbitrary precision. This is quite inefficient for things like summing over a list. Or really, any kind of accumulation.
- reikonomusha 7y ago
  If you made decisions based off of precision at some point in time, then you’re right. You’ve “baked” into the number some aspect about a precision decision you’ve previously made. That doesn’t invalidate the number, as it reflects precisely the number you asked for, it just means you’re expressing your computation in a dubious manner. Sometimes it’s unavoidable though, such as when checking equality where you have to call it quits at some point at some precision.
rocqua 7y ago
Interesting caveat to the computable reals. Equality is hard. I need to look into this but I'm pretty sure it's undecidable. Edit: looking into it was just reading futher on wikipedia. Even ordering is undecidable.
- empath75 7y ago
  Undecidable in principle but I wonder how much it comes up in practice.
  - reikonomusha 7y ago
    In practice, you get guarantees “up to precision”. This is totally reasonable. If you’re doubtful, you can either prove theorems, or bump up the precision. In general this works well.
  - rocqua 7y ago
    Good point. It's not worse than floating point numbers.

chipguy 7y ago

That's interesting because that's how humans actually do algebra. Who cares about the decimal expansion of some irrational if in the end we divide it by itself for example.

gjm11 7y ago
Unfortunately, most infinite-precision real-number implementations (including the one here, I bet, but I haven't checked) will not recognize that you're dividing something by itself. So you'll get a super-inefficient implementation of the number 1 :-). [EDITED to add:] I checked; the implementation here indeed won't recognize that you're dividing something by itself. For the avoidance of doubt, nor do I think trying to recognize such things would be an improvement. (Also, if you ask for e.g. the digit immediately preceding the decimal point, you will wait for ever because no amount of precision will enable the implementation to tell whether your number is just less than 1 or 1 or just over. So don't ask it for that, ask it for a very close approximation and draw your own conclusions.)
- jjnoakes 7y ago
  Also note that dividing something by itself is not necessarily 1.
  - jgalt212 7y ago
    I dunno, I think 0/0 is 1, but I cannot be sure. https://www.wolframalpha.com/input/?i=lim+x%2Fx+as+x-%3E0 https://www.wolframalpha.com/input/?i=lim+x%2Fx+as+x-%3E0
    - jolmg 7y ago
      You can say 0/0 is 1, but it's also 2 and 3 and every other number, since x*0=0 for any x. That's why it's undefined.
      - all2 7y ago
        Could we define it as a one to many function that maps from 0/0 to the set of all Complex numbers? If 0/0 = Q, then 0 = 0 × Q. So, we get to define this operation. If we treat 0 as an integer, then we could treat Q (a set) like a 1 x inf. matrix and we have scalar multiplication. But 0 × Q = [0]' × Q So 0 can be an infinite set of 0. This is cyclical, I know. This cyclical nature leads to an interesting effect if we also define integer division. Try this around 0 in Q. We could also define the × as an inner (dot) product, or as a cross product. This is fun!
        ngcc_hk 7y ago
        Is there a number set larger than a complex number? If so you can’t map to any concrete thing as it is really anything. And I guess it is easy to define one more dimension of number.
- reikonomusha 7y ago
  The notion of "by itself" is dubious in this context at best. You can only check up to finite precision that two numbers are equal. For something more, you need computer algebra, which is a tall order. Even if you have computer algebra, math says it's not possible to check that arbitrary expressions are equal. It's an undecidable problem. So with that, I don't fault a computable reals package not being able to detect that x == y in an expression x/y.

jolmg 7y ago

Sounds similar to how Haskell does all number computations by default. When you do 1/3 for example it leaves the types generic/ambiguous using typeclasses until it finds something to refine them. 1/3 could be a floating-point number, or a fixed-point number, or a rational (datatype holding the numerator and denominator), or any other user-defined datatype. You could put these computations in a library, keeping their types generic with typeclasses, and a user of your library can use their own number datatypes. Your library would automatically support that datatype in your number computations.

nestorD 7y ago
No really, computable real store the AST of the computation to lazily compute digits as they are needed (which is an interesting idea but memory hungry at scale) while Haskell approach is more akind to a form of general type deduction. Note that I first meet computable numbers in Haskell : https://wiki.haskell.org/Applications_and_libraries/Mathematics#Dynamic_precision_by_lazy_evaluation https://wiki.haskell.org/Applications_and_libraries/Mathemat...
- mbrock 7y ago
  http://hackage.haskell.org/package/exact-real-0.12.2 http://hackage.haskell.org/package/exact-real-0.12.2 I’ve used this package to get exact real computations in Haskell which get evaluated at n bits when needed for printing or equality checking etc.

mehrdadn 7y ago

I don't understand how this is supposed to work. For one thing iterative code wouldn't even do the same number of iterations when you change the desired precision, so merely plugging in higher precision numbers wouldn't give the higher precision approximation you'd be looking for. You'd have to actually re-execute the entire code with higher precision numbers so that intermediate control flow decisions use those numbers instead too, right?

Veedrac 7y ago
Generally, precision is pulled on-demand, as it is needed. If you compare two values as x < y, x and y will be evaluated to higher and higher precision until the answer is unambiguous. This can be an issue if the values are equal, since they often cannot be proven to be equal, so the evaluation may just outright fail to terminate.
- mehrdadn 7y ago
  That doesn't address the situation I outlined?
  - rocqua 7y ago
    You store the expression. Because that expression is a computable real, you can calculate it to arbitrary precision. This is quite inefficient for things like summing over a list. Or really, any kind of accumulation.
reikonomusha 7y ago
If you made decisions based off of precision at some point in time, then you’re right. You’ve “baked” into the number some aspect about a precision decision you’ve previously made. That doesn’t invalidate the number, as it reflects precisely the number you asked for, it just means you’re expressing your computation in a dubious manner. Sometimes it’s unavoidable though, such as when checking equality where you have to call it quits at some point at some precision.

rocqua 7y ago

Interesting caveat to the computable reals. Equality is hard. I need to look into this but I'm pretty sure it's undecidable. Edit: looking into it was just reading futher on wikipedia. Even ordering is undecidable.

empath75 7y ago
Undecidable in principle but I wonder how much it comes up in practice.
- reikonomusha 7y ago
  In practice, you get guarantees “up to precision”. This is totally reasonable. If you’re doubtful, you can either prove theorems, or bump up the precision. In general this works well.
- rocqua 7y ago
  Good point. It's not worse than floating point numbers.