3 ms·

Rational arithmetic needs better matrix libraries. No loss of precision then.

klodolph 5y ago
People have got to stop suggesting this. It doesn't make any sense and it's usually a waste of time. First of all, the example in the article is computing eigenvalues. Let me ask you: how do you expect to calculate eigenvalues using rational numbers? As a refresher, if it's been years since you took a look at linear algebra, the eigenvalues of a matrix are the roots of the matrix's characteristic polynomial, and we remember from high-school algebra that the roots of a polynomial are often not rational numbers, even if the coefficients are rational. Therefore, using rational arithmetic here is a complete non-starter. It's just not even possible, right from the very start. However, let's suppose that the particular problem that we are interested in solving does admit a rational solution. What then? Well, our real-world experience tells us that we often need an excessive amount computational resources and memory for exact, rational answers to linear algebra problems even of modest size. As you perform more computations on rational numbers, the memory required continues to grow.
- thechao 5y ago
  Floating point numbers are a particular way to represent (and modestly compress) rational numbers. I'm against rational number libraries because they use non-power-of-2 denominators and are, thus, fundamentally less efficient with respect to the actual cost of calculation.
  - ogogmad 5y ago
    > Floating point numbers are a particular way to represent (and modestly compress) rational numbers No no no no no no. Rational arithmetic satisfies (a+b)+c=a+(b+c); floating point arithmetic does not. Therefore floats are not a subset of rationals.
    - thechao 5y ago
      Rational arithmetic on a computer does not satisfy this property, either, for the exact same reason floating point does not: there is a finite amount of memory. Floating point embraces this edge-case in a rigorous way that none of the rational arithmetic libraries I've used have ever even attempted.
    - klodolph 5y ago
      > Rational arithmetic satisfies (a+b)+c=a+(b+c); floating point arithmetic does not. Therefore floats are not a subset of rationals. This reasoning is not sound. The conclusion is only correct by accident. The reason floats are not a subset of the rationals is because floats distinguish positive and negative zero, and because floats represent non-finite values (NaN and infinity). The fact that floating-point operations are not commutative is a consequence of the fact that floating-point numbers are not a "subring" of the rational numbers, not a consequence of the fact that the floating-point numbers are not a subset of the rationals. You could easily take a subset of the floating-point numbers that is also a subset of the rationals, it would still not be associative (assuming it contains at least two different elements). Here is the concept you are looking for: https://en.wikipedia.org/wiki/Subring https://en.wikipedia.org/wiki/Subring
      - deleted 5y ago
        [deleted]
- throwaway858 5y ago
  I agree with this from a practical perspective. But it is worth pointing out that it is actually possible to maintain "perfect" accuracy when doing arithmetic even when sqrts (or other irrational numbers) are involved. The idea is to store numbers as an AST consisting of an expression. Then you can perform any arithmetic on them by growing the AST. After each operation you simplify as much as you can. Once you have your final result you can evaluate the AST up to any precision that you need (and sometimes your final AST will already be a rational number because sqrts cancelled out)
  - aSanchezStern 5y ago
    I believe you're basically referring to the computable reals; for the curious, here's the wikipedia page (kind of abstract): https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number and here's the paper where they implement them programmatically, including for the android calculator application (I believe this is how the android calculator works now): https://dl.acm.org/doi/abs/10.1145/3385412.3386037 https://dl.acm.org/doi/abs/10.1145/3385412.3386037
- irchans 5y ago
  I still like to occasionally use rational number arithmetic because I "know" that the answer is correct. It is very true that it can be horribly slow, but if it does finish, then you do have a correct answer. I have only rarely used it in production code. In those rare cases, I think that I would have checked to make sure that the running time was acceptable.
  - klodolph 5y ago
    In this case, we know it would be incorrect (in general) because eigenvalues are often irrational. In other cases, there are often better ways to figure out that the answer is correct. Figuring out that the answer is correct using rational arithmetic is often just too inefficient, compared to doing a bit of numerical analysis or figuring out a way to validate the answer you got. That is, unless the problem is very small.
kadoban 5y ago
True, but then they run arbitrarily slowly, and it's trivial to reach cases where this actually happens. And anything without a rational result you're stuck again.
- irchans 5y ago
  Often you can bound the running time --- certainly if there are no loops and you only use + - * and / operations. But, you are often screwed if there is a sin, cos, sqrt or other function that gives irrational results. You can sometimes get around sqrt function or other root functions by using an extension field, but I think I could count on one hand how many times I've done that.

People have got to stop suggesting this. It doesn't make any sense and it's usually a waste of time. First of all, the example in the article is computing eigenvalues. Let me ask you: how do you expect to calculate eigenvalues using rational numbers? As a refresher, if it's been years since you took a look at linear algebra, the eigenvalues of a matrix are the roots of the matrix's characteristic polynomial, and we remember from high-school algebra that the roots of a polynomial are often not rational numbers, even if the coefficients are rational. Therefore, using rational arithmetic here is a complete non-starter. It's just not even possible, right from the very start. However, let's suppose that the particular problem that we are interested in solving does admit a rational solution. What then? Well, our real-world experience tells us that we often need an excessive amount computational resources and memory for exact, rational answers to linear algebra problems even of modest size. As you perform more computations on rational numbers, the memory required continues to grow.

thechao 5y ago
Floating point numbers are a particular way to represent (and modestly compress) rational numbers. I'm against rational number libraries because they use non-power-of-2 denominators and are, thus, fundamentally less efficient with respect to the actual cost of calculation.
- ogogmad 5y ago
  > Floating point numbers are a particular way to represent (and modestly compress) rational numbers No no no no no no. Rational arithmetic satisfies (a+b)+c=a+(b+c); floating point arithmetic does not. Therefore floats are not a subset of rationals.
  - thechao 5y ago
    Rational arithmetic on a computer does not satisfy this property, either, for the exact same reason floating point does not: there is a finite amount of memory. Floating point embraces this edge-case in a rigorous way that none of the rational arithmetic libraries I've used have ever even attempted.
  - klodolph 5y ago
    > Rational arithmetic satisfies (a+b)+c=a+(b+c); floating point arithmetic does not. Therefore floats are not a subset of rationals. This reasoning is not sound. The conclusion is only correct by accident. The reason floats are not a subset of the rationals is because floats distinguish positive and negative zero, and because floats represent non-finite values (NaN and infinity). The fact that floating-point operations are not commutative is a consequence of the fact that floating-point numbers are not a "subring" of the rational numbers, not a consequence of the fact that the floating-point numbers are not a subset of the rationals. You could easily take a subset of the floating-point numbers that is also a subset of the rationals, it would still not be associative (assuming it contains at least two different elements). Here is the concept you are looking for: https://en.wikipedia.org/wiki/Subring https://en.wikipedia.org/wiki/Subring
    - deleted 5y ago
      [deleted]
throwaway858 5y ago
I agree with this from a practical perspective. But it is worth pointing out that it is actually possible to maintain "perfect" accuracy when doing arithmetic even when sqrts (or other irrational numbers) are involved. The idea is to store numbers as an AST consisting of an expression. Then you can perform any arithmetic on them by growing the AST. After each operation you simplify as much as you can. Once you have your final result you can evaluate the AST up to any precision that you need (and sometimes your final AST will already be a rational number because sqrts cancelled out)
- aSanchezStern 5y ago
  I believe you're basically referring to the computable reals; for the curious, here's the wikipedia page (kind of abstract): https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number and here's the paper where they implement them programmatically, including for the android calculator application (I believe this is how the android calculator works now): https://dl.acm.org/doi/abs/10.1145/3385412.3386037 https://dl.acm.org/doi/abs/10.1145/3385412.3386037
irchans 5y ago
I still like to occasionally use rational number arithmetic because I "know" that the answer is correct. It is very true that it can be horribly slow, but if it does finish, then you do have a correct answer. I have only rarely used it in production code. In those rare cases, I think that I would have checked to make sure that the running time was acceptable.
- klodolph 5y ago
  In this case, we know it would be incorrect (in general) because eigenvalues are often irrational. In other cases, there are often better ways to figure out that the answer is correct. Figuring out that the answer is correct using rational arithmetic is often just too inefficient, compared to doing a bit of numerical analysis or figuring out a way to validate the answer you got. That is, unless the problem is very small.

kadoban 5y ago

True, but then they run arbitrarily slowly, and it's trivial to reach cases where this actually happens. And anything without a rational result you're stuck again.

irchans 5y ago
Often you can bound the running time --- certainly if there are no loops and you only use + - * and / operations. But, you are often screwed if there is a sin, cos, sqrt or other function that gives irrational results. You can sometimes get around sqrt function or other root functions by using an extension field, but I think I could count on one hand how many times I've done that.