4 ms·

I was hoping the author went full circle to reinventing floating point, but this is a great writeup of the process. Really good motivation.

by nimish 8y ago

tomxor 8y ago
Re-inventing floating point format would be missing the point (edit: i honestly did not see that pun sorry).. floating point formats cannot represent all of the rational numbers that a fraction could using the equivalent bits e.g 1/10 can be represented in base 10 decimals but not in base 2 float (where it has a repeating significand much like 1/3 in base 10), which becomes a problem when doing further math on it, try: 1/10 + 2/10). Both methods result in "holes" bellow zero (necessarily of course), but they do not fit inside each other. However within a limited set of operations, rational numbers (within a capable format, and with necessary operators) have some interesting properties over floating point math that makes them desirable, i.e not loosing precision (unless overflow due to encountering large primes), and they are less expensive (built on integer math). What he did do, is make a rational number bit format (floating bar) which stores everything as fractions, it's quite elegant really and anyone familiar with IEEE754 will see the similarities.
- Veedrac 8y ago
  Floating point is also built on integer math, and cheaper operations at that.
  - tomxor 8y ago
    Ultimately yes, but I'd be interested in a side by side comparison, without FPUs. Also as explained in the article, divide (which is expensive float operation) is as cheap as integer multiplies with fractions.
    - Veedrac 8y ago
      It's very rare not to need GCD reduction, though; multiplying values burns through bits extremely fast. Only doing factor-2 reduction isn't infeasible but you'd be further damaging an already iffy type.
      - tomxor 8y ago
        > It's very rare not to need GCD reduction, though Yes good point, I did wonder this... it's easy to look at the individual operations and think "that's cheap" but holistically, the GCD which I assume is expensive could make the overall performance benefits moot. It might be optimisable to not do it unnecessarily after _every_ operation though? Perhaps then the only advantage in terms of hardware use is that it can be implemented on a CPU with only ints e.g small micro-controllers with no FPU or int divide. I think that by comparison implementing a soft FPU would be impractical, still niche I guess.
        Veedrac 8y ago
        I'm not sure, but I suspect your best alternative to 32-bit floats/floating-bar-rationals or 64-bit rationals when you have no FPU is a 64-bit fixed-point value with compressed floating-point representations if you need to store it compactly in memory.

I was hoping the author went full circle to reinventing floating point, but this is a great writeup of the process. Really good motivation.

by nimish 8y ago

I was hoping the author went full circle to reinventing floating point, but this is a great writeup of the process. Really good motivation.

tomxor 8y ago

Re-inventing floating point format would be missing the point (edit: i honestly did not see that pun sorry).. floating point formats cannot represent all of the rational numbers that a fraction could using the equivalent bits e.g 1/10 can be represented in base 10 decimals but not in base 2 float (where it has a repeating significand much like 1/3 in base 10), which becomes a problem when doing further math on it, try: 1/10 + 2/10). Both methods result in "holes" bellow zero (necessarily of course), but they do not fit inside each other. However within a limited set of operations, rational numbers (within a capable format, and with necessary operators) have some interesting properties over floating point math that makes them desirable, i.e not loosing precision (unless overflow due to encountering large primes), and they are less expensive (built on integer math). What he did do, is make a rational number bit format (floating bar) which stores everything as fractions, it's quite elegant really and anyone familiar with IEEE754 will see the similarities.

Veedrac 8y ago
Floating point is also built on integer math, and cheaper operations at that.
- tomxor 8y ago
  Ultimately yes, but I'd be interested in a side by side comparison, without FPUs. Also as explained in the article, divide (which is expensive float operation) is as cheap as integer multiplies with fractions.
  - Veedrac 8y ago
    It's very rare not to need GCD reduction, though; multiplying values burns through bits extremely fast. Only doing factor-2 reduction isn't infeasible but you'd be further damaging an already iffy type.
    - tomxor 8y ago
      > It's very rare not to need GCD reduction, though Yes good point, I did wonder this... it's easy to look at the individual operations and think "that's cheap" but holistically, the GCD which I assume is expensive could make the overall performance benefits moot. It might be optimisable to not do it unnecessarily after _every_ operation though? Perhaps then the only advantage in terms of hardware use is that it can be implemented on a CPU with only ints e.g small micro-controllers with no FPU or int divide. I think that by comparison implementing a soft FPU would be impractical, still niche I guess.
      - Veedrac 8y ago
        I'm not sure, but I suspect your best alternative to 32-bit floats/floating-bar-rationals or 64-bit rationals when you have no FPU is a 64-bit fixed-point value with compressed floating-point representations if you need to store it compactly in memory.