4 ms·

What is the advantage of fixed point arithmetic over rational arithmetic? Rational arithmetic seems to include fixed point arithmetic as a subset (in fixed poin

What is the advantage of fixed point arithmetic over rational arithmetic? Rational arithmetic seems to include fixed point arithmetic as a subset (in fixed point arithmetic the denominator is always a power of the base).

the_gorilla 2y ago
It has to run on a computer. How would you simulate rational arithmetic?
- mikequinlan 2y ago
  Rational arithmetic represents numbers as a numerator and denominator (rational numbers). There are hundreds (at least) of libraries that implement rational arithmetic on a computer. https://www.google.com/search?q=rational+arithmetic+library https://www.google.com/search?q=rational+arithmetic+library
  - the_gorilla 2y ago
    I meant run on the cpu itself. Most processors have floating-point support, and fixed-point just uses integer operations. All those heavy libraries require an arbitrary amount of memory for their calculations.
    - dzaima 2y ago
      The article here is about hardware without native FP already; that said, rationals (even before getting to the need of bigints) are quite bad regardless, likely requiring division & gcd around basic arith, which are slow both in software and in hardware.
codr7 2y ago
As stated: rationals are more general purpose, hence more complicated.
Isognoviastoma 2y ago
- after few operations denominator exceeds 64-bit range, so you either need bigint, or make fractions approximate, what is in affect fixed point - often you use decimal fraction on output and input anyway - it's slower, even slower with bigint - no square root, sin, and so on with rationals
- crabbone 2y ago
  > no square root, sin, and so on with rationals Are you thinking about a specific library? You aren't the only person who commented this way. But, the truth is that root, sin and so on don't "work" with floats either. In fact, there are common ways to implement these functions by either using tables (which are approximate) or algebraic approximations (that give you... drum roll: rationals!) But, really, there isn't any way (except symbolically) to represent transcendental functions in computers. It doesn't matter what kind of number you choose to do it.
  - Isognoviastoma 2y ago
    √2 with floating point is obviously closest representable number. With fixed point it is obviously closest representable number as well. With rationals, you need to arbitrarily limit precision, and the point of using rational was to use exact values.
    - User23 2y ago
      Rational approximation is a thing. 22/7 and all that.
    - NL807 2y ago
      I don't think that's a big deal though. You deliberately choose to use a rational system, because you understand the problem domain, which could greatly benefit from such a representation. If you throw a rational system at every math problem as a catch-all representation, then you are doing it wrong.
- lifthrasiir 2y ago
tliltocatl 2y ago
Unless you allow the denominator to grow unbound, rational have no real advantage over FP and are much slower. If you allow unbound denominator, you will run out of memory after perhaps a few thousand operations (and having to dynamically allocate memory will kill performance even further). And then there are transcendent functions which cannot be represented by rationals anyway.
- crabbone 2y ago
  > And then there are transcendent functions which cannot be represented by rationals anyway. They cannot be represented by floats either. So this doesn't matter.
  - dzaima 2y ago
    The meaningful difference with irrational computations on rationals vs floats is that in floats you have some inherent, expected, and well-understood imprecision that applies evenly over results of add/mul/div/sqrt/sin/etc, whereas in unbounded rationals add/mul/div are all infinitely precise always (and presumably this property is why one would want rationals over floats) but has no such possible equivalent for sqrt/sin (at which point your options are either just giving up, or capping the required precision, at which point you could just use floats).
    - wakawaka28 2y ago
      Floating point operations also run in constant-bounded time. You can't say that about any arbitrary-precision format.
    - crabbone 2y ago
      > well-understood imprecision that applies evenly over results I'm sorry, I have some bad news for you... especially the "evenly" part. I had a friend who worked at IBM research on the problem of "normalizing" some matrix multiplication irregularities which occur due to numerical underflow or overflow. And, it's anything but a solved or an easy problem.
deleted 2y ago
[deleted]
jcranmer 2y ago
In fixed-point arithmetic, your basic operations come out to a multiply and a divide (which is a shift, if it's binary fixed-point) in the worst case. For rational arithmetic, you need to do two multiplies and a gcd-like algorithm to normalize the result (which is probably at least as expensive as a divider, even if implemented with hardware acceleration) in the best case, and three multiplies and an addition (and the gcd-like algorithm for normalization) for a simple addition. Rational arithmetic operations are just plain slow, and there isn't a lot of magic that can fix that.
- dzaima 2y ago
  There is some magic that may somewhat help - delaying normalization to when it's actually necessary or the numbers get too large, and skipping steps if denominators are equal. But even then it'll be quite bad relative to floats, especially so on software implementations due to likely having unpredictable branches.
  - adrian_b 2y ago
    Delaying normalization is much more likely to work well when you use big numbers, e.g. 64-bit or bigger integers. With 32-bit integers, overflows caused by omitting the normalization step may be so frequent as to remove any advantage from delaying the normalization. It is probably best to have a fixed-point operation library that implements both options for normalization, so you may test an application with both delayed and immediate normalization, and choose which is better.
magicalhippo 2y ago
Floats are essentially just rationals, but with the denominators limited to powers of two. The advantage of fixed point is that you avoid all the complications of a changing denominator by having a fixed denominator.
- jonathrg 2y ago
  For simple applications, yes. In practical applications you often need to shift the "fixed" point around manually to maintain the appropriate dynamic range.
  - magicalhippo 2y ago
    Right, but still fixed at compile-time.
15155 2y ago
On a small microcontroller without a hard FPU and a very small quantity of meaningful memory: performance.

the_gorilla 2y ago

It has to run on a computer. How would you simulate rational arithmetic?

mikequinlan 2y ago
Rational arithmetic represents numbers as a numerator and denominator (rational numbers). There are hundreds (at least) of libraries that implement rational arithmetic on a computer. https://www.google.com/search?q=rational+arithmetic+library https://www.google.com/search?q=rational+arithmetic+library
- the_gorilla 2y ago
  I meant run on the cpu itself. Most processors have floating-point support, and fixed-point just uses integer operations. All those heavy libraries require an arbitrary amount of memory for their calculations.
  - dzaima 2y ago
    The article here is about hardware without native FP already; that said, rationals (even before getting to the need of bigints) are quite bad regardless, likely requiring division & gcd around basic arith, which are slow both in software and in hardware.

codr7 2y ago

As stated: rationals are more general purpose, hence more complicated.

Isognoviastoma 2y ago

- after few operations denominator exceeds 64-bit range, so you either need bigint, or make fractions approximate, what is in affect fixed point - often you use decimal fraction on output and input anyway - it's slower, even slower with bigint - no square root, sin, and so on with rationals

crabbone 2y ago
> no square root, sin, and so on with rationals Are you thinking about a specific library? You aren't the only person who commented this way. But, the truth is that root, sin and so on don't "work" with floats either. In fact, there are common ways to implement these functions by either using tables (which are approximate) or algebraic approximations (that give you... drum roll: rationals!) But, really, there isn't any way (except symbolically) to represent transcendental functions in computers. It doesn't matter what kind of number you choose to do it.
- Isognoviastoma 2y ago
  √2 with floating point is obviously closest representable number. With fixed point it is obviously closest representable number as well. With rationals, you need to arbitrarily limit precision, and the point of using rational was to use exact values.
  - User23 2y ago
    Rational approximation is a thing. 22/7 and all that.
  - NL807 2y ago
    I don't think that's a big deal though. You deliberately choose to use a rational system, because you understand the problem domain, which could greatly benefit from such a representation. If you throw a rational system at every math problem as a catch-all representation, then you are doing it wrong.
lifthrasiir 2y ago

tliltocatl 2y ago

Unless you allow the denominator to grow unbound, rational have no real advantage over FP and are much slower. If you allow unbound denominator, you will run out of memory after perhaps a few thousand operations (and having to dynamically allocate memory will kill performance even further). And then there are transcendent functions which cannot be represented by rationals anyway.

crabbone 2y ago
> And then there are transcendent functions which cannot be represented by rationals anyway. They cannot be represented by floats either. So this doesn't matter.
- dzaima 2y ago
  The meaningful difference with irrational computations on rationals vs floats is that in floats you have some inherent, expected, and well-understood imprecision that applies evenly over results of add/mul/div/sqrt/sin/etc, whereas in unbounded rationals add/mul/div are all infinitely precise always (and presumably this property is why one would want rationals over floats) but has no such possible equivalent for sqrt/sin (at which point your options are either just giving up, or capping the required precision, at which point you could just use floats).
  - wakawaka28 2y ago
    Floating point operations also run in constant-bounded time. You can't say that about any arbitrary-precision format.
  - crabbone 2y ago
    > well-understood imprecision that applies evenly over results I'm sorry, I have some bad news for you... especially the "evenly" part. I had a friend who worked at IBM research on the problem of "normalizing" some matrix multiplication irregularities which occur due to numerical underflow or overflow. And, it's anything but a solved or an easy problem.

deleted 2y ago

[deleted]

jcranmer 2y ago

In fixed-point arithmetic, your basic operations come out to a multiply and a divide (which is a shift, if it's binary fixed-point) in the worst case. For rational arithmetic, you need to do two multiplies and a gcd-like algorithm to normalize the result (which is probably at least as expensive as a divider, even if implemented with hardware acceleration) in the best case, and three multiplies and an addition (and the gcd-like algorithm for normalization) for a simple addition. Rational arithmetic operations are just plain slow, and there isn't a lot of magic that can fix that.

dzaima 2y ago
There is some magic that may somewhat help - delaying normalization to when it's actually necessary or the numbers get too large, and skipping steps if denominators are equal. But even then it'll be quite bad relative to floats, especially so on software implementations due to likely having unpredictable branches.
- adrian_b 2y ago
  Delaying normalization is much more likely to work well when you use big numbers, e.g. 64-bit or bigger integers. With 32-bit integers, overflows caused by omitting the normalization step may be so frequent as to remove any advantage from delaying the normalization. It is probably best to have a fixed-point operation library that implements both options for normalization, so you may test an application with both delayed and immediate normalization, and choose which is better.

magicalhippo 2y ago

Floats are essentially just rationals, but with the denominators limited to powers of two. The advantage of fixed point is that you avoid all the complications of a changing denominator by having a fixed denominator.

jonathrg 2y ago
For simple applications, yes. In practical applications you often need to shift the "fixed" point around manually to maintain the appropriate dynamic range.
- magicalhippo 2y ago
  Right, but still fixed at compile-time.

15155 2y ago

On a small microcontroller without a hard FPU and a very small quantity of meaningful memory: performance.