6 ms·

It's interesting to point out that you can compute with exact real numbers. But this is of course going to be less efficient than using something crude and fast

It's interesting to point out that you can compute with exact real numbers. But this is of course going to be less efficient than using something crude and fast like floating point numbers. There's also an argument that imprecision from your physical sensors is probably going to be more significant than the rounding errors that come with floating point. Apart from greater speed, floating point numbers don't really have any advantages over exact real numbers. Problems like the inability to compute discontinuous functions over the real numbers manifest as even worse problems over the floating point numbers. I'm also a believer that anything beautiful is probably going to end up useful. I think exact real computation (as described in Type Two Computability Theory) is one such thing. Automatic differentiation was another thing I found beautiful, before I found out about its applications to neural networks.

sn41 8y ago
Type-two theory has a huge disadvantage: it elevates the type of all operations by a level. For example, real numbers become functions. Hence addition becomes a type 2 functional. Integration becomes type 3. It is very hard to reason about the efficiency (and computability, come to think of it) of type 3 functionals. There's some esoteric example involving the fan functional [1]. The complexity theory of type-2 functionals is a theory which is natural to ask for, but after results by Cook, Bellantoni, Kapron, Seth, Pezzoli and others, has come to an impasse and now seems abandoned. [1] https://pdfs.semanticscholar.org/3888/cc2d3c44fb051067581e3947c3b9f9af1d5c.pdf https://pdfs.semanticscholar.org/3888/cc2d3c44fb051067581e39...
- man-and-laptop 8y ago
  They effectively change the structure of your code. Every time you do an operation on a real number, it essentially launches a new process that runs indefinitely in the background. I would file that under speed problems. To control the speed penalty, you need to make deep changes to your code. I think Andrej Bauer came to this conclusion. Regarding computability, it's not so bad. Basically a continuous operator is usually computable. Example: Integration is continuous, hence (likely, and in this case actually) computable.
Const-me 8y ago
> floating point numbers don't really have any advantages over exact real numbers. With floating point numbers, you can solve quadratic equations, calculate sin/cos, calculate log/exp. These things have lots of applications.
- man-and-laptop 8y ago
  I never said that they don't have applications. And you can do all those things with real numbers. What's your point?
  - Const-me 8y ago
    > you can do all those things with real numbers. No you can't. > What's your point? Floats really have lots of advantages over exact real numbers. Being able to compute transcendental functions is one of them. There're others. They're freaking fast, my cheap laptop with integrated GPU can do almost 1 TFlops. They're fixed size i.e. you can handle them without dynamic memory allocations.
    - deleted 8y ago
      [deleted]
    - gjm11 8y ago
      I think you may be misunderstanding what the other guy means by exact real numbers: not rationals (for which indeed you can't do things like square roots) but real numbers expressed, say, as functions that deliver arbitrarily close rational approximations. With these you can compute e.g. square roots just fine. They have disadvantages of their own, though: for instance, y if two of these are equal then in general you can't determine that they are in finite time.
      - man-and-laptop 8y ago
        > if two of these are equal then in general you can't determine that they are in finite time. This is arguably a problem with floating point as well. Two computations F and G which ought to produce the same result can end up differing because of rounding errors. So equality testing is not advisable to do over floating point. Also, inequality of real numbers is still semi-decidable, which is useful. People keep bringing up these problems around not being able to compute discontinuous functions, but those problems still manifest themselves over the floating point numbers, in the sense that a small rounding error in the input can drastically affect the output. This obviously isn't a problem over the rational numbers, but a lot of operations like square-root are not possible over the rational numbers.

sn41 8y ago

Type-two theory has a huge disadvantage: it elevates the type of all operations by a level. For example, real numbers become functions. Hence addition becomes a type 2 functional. Integration becomes type 3. It is very hard to reason about the efficiency (and computability, come to think of it) of type 3 functionals. There's some esoteric example involving the fan functional [1]. The complexity theory of type-2 functionals is a theory which is natural to ask for, but after results by Cook, Bellantoni, Kapron, Seth, Pezzoli and others, has come to an impasse and now seems abandoned. [1] https://pdfs.semanticscholar.org/3888/cc2d3c44fb051067581e3947c3b9f9af1d5c.pdf https://pdfs.semanticscholar.org/3888/cc2d3c44fb051067581e39...

man-and-laptop 8y ago
They effectively change the structure of your code. Every time you do an operation on a real number, it essentially launches a new process that runs indefinitely in the background. I would file that under speed problems. To control the speed penalty, you need to make deep changes to your code. I think Andrej Bauer came to this conclusion. Regarding computability, it's not so bad. Basically a continuous operator is usually computable. Example: Integration is continuous, hence (likely, and in this case actually) computable.

Const-me 8y ago

> floating point numbers don't really have any advantages over exact real numbers. With floating point numbers, you can solve quadratic equations, calculate sin/cos, calculate log/exp. These things have lots of applications.

man-and-laptop 8y ago
I never said that they don't have applications. And you can do all those things with real numbers. What's your point?
- Const-me 8y ago
  > you can do all those things with real numbers. No you can't. > What's your point? Floats really have lots of advantages over exact real numbers. Being able to compute transcendental functions is one of them. There're others. They're freaking fast, my cheap laptop with integrated GPU can do almost 1 TFlops. They're fixed size i.e. you can handle them without dynamic memory allocations.
  - deleted 8y ago
    [deleted]
  - gjm11 8y ago
    I think you may be misunderstanding what the other guy means by exact real numbers: not rationals (for which indeed you can't do things like square roots) but real numbers expressed, say, as functions that deliver arbitrarily close rational approximations. With these you can compute e.g. square roots just fine. They have disadvantages of their own, though: for instance, y if two of these are equal then in general you can't determine that they are in finite time.
    - man-and-laptop 8y ago
      > if two of these are equal then in general you can't determine that they are in finite time. This is arguably a problem with floating point as well. Two computations F and G which ought to produce the same result can end up differing because of rounding errors. So equality testing is not advisable to do over floating point. Also, inequality of real numbers is still semi-decidable, which is useful. People keep bringing up these problems around not being able to compute discontinuous functions, but those problems still manifest themselves over the floating point numbers, in the sense that a small rounding error in the input can drastically affect the output. This obviously isn't a problem over the rational numbers, but a lot of operations like square-root are not possible over the rational numbers.