4 ms·

Isn't this yet another implementation of interval arithmetic? What am I missing? Calling his book "The End of Error" seems a bit much.

Someone 11y ago
No, it is making a distinction between exact and inexact numbers, and uses arbitrary precision. I don't see it gain wide acceptance. If your problem is fixed-num, use a bignum library. If it is not, chances are you will meet a number that isn't representable in this format very, very soon (1/3, 1/5, sqrt(2), PI, etc.) The moment you do, you will have to decide to how many bits of precision you want to compute that inexact number. Problem is that you cannot make that choice, unless you know exactly what you intend to do with the number. I bet most users will choose a format that their hardware handles natively: IEEE. There may be edge cases in numerical computing that benefit from this, especially when problems are ill-conditioned, but even there, I expect people to convert to conventional IEEE on the outside of their API. Also, I'm not sure there is much room in this space below quad-width floats (but I am not an expert)
- barsonme 11y ago
  wouldn't most of the issues be solved with use of bcd/dcd? you get the speed (compared to arbitrary-precision), fixed-precision, and exact answers up to the precision limit?
  - bsder 11y ago
    Unfortunately, no. BCD as "binary coded decimal" is, effectively, useless. Even arbitrary precision libraries tend to be faster than BCD. "decimal floating point", which is what I think you meant, just changes what isn't representable. Instead of 1/5 causing a problem, 1/3 causes a problem. The "classic" problem about this is matrix operations. Specifically, matrix inversion. You can use interval arithmetic on matrix inversion, and you find that the intervals blow up to almost infinity after just a couple of operations even though the center of the interval is actually pretty close to the solution. Of course, the reverse also holds: while most matricies invert relatively cleanly, there are always pathological cases that really do need humungous precision to invert. PS: Don't know why you were getting downvoted as you asked a legitimate question.
    - barsonme 11y ago
      Thank you the answer! It was very insightful. Also, no big deal about downvotes. Can't please everybody.
lfowles 11y ago
Not especially. Just floating point without fixed size significand and exponent. I do like the idea of having an "exact representation" bit carried along though.. Edit: Link has been changed to a more in depth ACM interview! I suppose this is a floating point format that makes the intervals more explicit by changing size to account for significant digits.
- Someone 11y ago
  I don't see big benefits for the 'exact' bit. There's only a fixed (in theory, countably infinite and infinitely dense) set of numbers that can be represented exactly. If you want to go for such a set of exactly-representable numbers, wouldn't the rationals be the better choice? That allows you, for example, to do dollar accounting in exact arithmetic. Also, to enable round-tripping with string representations, your printf/scanf pair has to discriminate between exact and inexact versions of, for example, 3/4. If you don't, every string you read in (e.g. from XML (including reading modern spreadsheet data), json, or from user input, will have to have the 'exact' bit cleared. I guess so many numbers will be inexact that it turns out to have close to zero information content (in other words: adding it to your numbers is a waste of space)
  - Maken 11y ago
    It avoids error whenever possible. For example, if you are working with pure fractions the result will be exactly representable and you'll end with 1/3 + 1/3 + 1/3 = 1 instead of some approximation.
    - Someone 11y ago
      That would be nice, but 1/3 isn't exactly representable in this representation. Or are you suggesting that, when computing 1/3, this number format picks the best representation for a given number of bits, keeping the 'exact' bit, for 1/3, and then magically decides that, say, 85/256 and 'exact' must be 1/3, and not 85/256, or whatever other expression that could be computed exactly gets close to it?
chriswarbo 11y ago
> A unum has three additional fields that make the number self-descriptive: The "ubit" that marks whether a number is exact or in between exact values, the size of the exponent in bits, and the size of the fraction in bits. So not only does the binary point float, the number of significant digits also floats. There is something called "significance arithmetic" that does a crude version of what the unum representation does, but unum math overcomes some serious drawbacks of both significance arithmetic and interval arithmetic. These "unums" have been posted before, e.g. https://news.ycombinator.com/item?id=11410349 https://news.ycombinator.com/item?id=11410349
oleks 11y ago
More importantly, the book fails to mention affine arithmetic.

Someone 11y ago

No, it is making a distinction between exact and inexact numbers, and uses arbitrary precision. I don't see it gain wide acceptance. If your problem is fixed-num, use a bignum library. If it is not, chances are you will meet a number that isn't representable in this format very, very soon (1/3, 1/5, sqrt(2), PI, etc.) The moment you do, you will have to decide to how many bits of precision you want to compute that inexact number. Problem is that you cannot make that choice, unless you know exactly what you intend to do with the number. I bet most users will choose a format that their hardware handles natively: IEEE. There may be edge cases in numerical computing that benefit from this, especially when problems are ill-conditioned, but even there, I expect people to convert to conventional IEEE on the outside of their API. Also, I'm not sure there is much room in this space below quad-width floats (but I am not an expert)

barsonme 11y ago
wouldn't most of the issues be solved with use of bcd/dcd? you get the speed (compared to arbitrary-precision), fixed-precision, and exact answers up to the precision limit?
- bsder 11y ago
  Unfortunately, no. BCD as "binary coded decimal" is, effectively, useless. Even arbitrary precision libraries tend to be faster than BCD. "decimal floating point", which is what I think you meant, just changes what isn't representable. Instead of 1/5 causing a problem, 1/3 causes a problem. The "classic" problem about this is matrix operations. Specifically, matrix inversion. You can use interval arithmetic on matrix inversion, and you find that the intervals blow up to almost infinity after just a couple of operations even though the center of the interval is actually pretty close to the solution. Of course, the reverse also holds: while most matricies invert relatively cleanly, there are always pathological cases that really do need humungous precision to invert. PS: Don't know why you were getting downvoted as you asked a legitimate question.
  - barsonme 11y ago
    Thank you the answer! It was very insightful. Also, no big deal about downvotes. Can't please everybody.

lfowles 11y ago

Not especially. Just floating point without fixed size significand and exponent. I do like the idea of having an "exact representation" bit carried along though.. Edit: Link has been changed to a more in depth ACM interview! I suppose this is a floating point format that makes the intervals more explicit by changing size to account for significant digits.

Someone 11y ago
I don't see big benefits for the 'exact' bit. There's only a fixed (in theory, countably infinite and infinitely dense) set of numbers that can be represented exactly. If you want to go for such a set of exactly-representable numbers, wouldn't the rationals be the better choice? That allows you, for example, to do dollar accounting in exact arithmetic. Also, to enable round-tripping with string representations, your printf/scanf pair has to discriminate between exact and inexact versions of, for example, 3/4. If you don't, every string you read in (e.g. from XML (including reading modern spreadsheet data), json, or from user input, will have to have the 'exact' bit cleared. I guess so many numbers will be inexact that it turns out to have close to zero information content (in other words: adding it to your numbers is a waste of space)
- Maken 11y ago
  It avoids error whenever possible. For example, if you are working with pure fractions the result will be exactly representable and you'll end with 1/3 + 1/3 + 1/3 = 1 instead of some approximation.
  - Someone 11y ago
    That would be nice, but 1/3 isn't exactly representable in this representation. Or are you suggesting that, when computing 1/3, this number format picks the best representation for a given number of bits, keeping the 'exact' bit, for 1/3, and then magically decides that, say, 85/256 and 'exact' must be 1/3, and not 85/256, or whatever other expression that could be computed exactly gets close to it?

chriswarbo 11y ago

> A unum has three additional fields that make the number self-descriptive: The "ubit" that marks whether a number is exact or in between exact values, the size of the exponent in bits, and the size of the fraction in bits. So not only does the binary point float, the number of significant digits also floats. There is something called "significance arithmetic" that does a crude version of what the unum representation does, but unum math overcomes some serious drawbacks of both significance arithmetic and interval arithmetic. These "unums" have been posted before, e.g. https://news.ycombinator.com/item?id=11410349 https://news.ycombinator.com/item?id=11410349

oleks 11y ago

More importantly, the book fails to mention affine arithmetic.