5 ms·

> Complete representation of all real numbers using a finite number of bits He's 1/3 of the way to three impossible things before breakfast by slide 15.

dnautics 11y ago
All real numbers are representable, but not necessarily to arbitrary precision. You should really read the book. A lot of the atomic operations seem cumbersome, because the unum doesn't have a fixed size representation, but you just get over that when you remember that the real problem is shuttling data over buses. More compute transistors is not a problem.
- stephencanon 11y ago
  No. The set of "representable" (i.e. computable) numbers is countable (because the set of programs is countable), so in fact almost all real numbers cannot be represented.
  - yoklov 11y ago
    I got the impression that the unum explicitly modeled a range of values, so I'm not sure that applies. Not an expert here though.
    - stephencanon 11y ago
      That's fine, but then you're representing dyadic intervals, not real numbers. Simple question: what's unum[sqrt(2)]?
      - dnautics 11y ago
        Rougly speaking It would be 1.414... + plus a bit that indicates the result is between two adjacent exact values. This bit would not be set if the result were exact. It's not the same as dyadic interval math, it's kind of a hybrid.
        davisourus 11y ago
        And you could set the environmental variables to be as precise as you need. If you need 29 digits of precision, you can quickly show that you know 1.4142135623730950488016887242 and nothing more. A reasonable metaphor would be that you cannot draw all of the Mandelbrot diagram, but you can render any piece of it to any resolution you choose. Being able to describe it precisely, and to know the limits of your accuracy, is useful.
    - Lawtonfogle 11y ago
      Regardless if it is representing number, ranges, or a mix of both, there are still 2^n maximum possible representations for n bits. Perhaps you could create a mix of numbers and ranges equal to (2^n)-2 and then add one range that is from the lowest number represented to negative infinity and add another that does the same for positives. But I can do that system with -, 0, +, NAN. See, I just represented all numbers. It isn't as useful, but boy are there savings on storage, cost, and computation time. Unums shouldn't be seen as better than ints, longs, floats, or doubles anymore than a double is seen as better than an int. They have different uses and strengths, and there are problems where none are a good choice. Perhaps unums are the best choice for some problems. Perhaps they are clearly and significantly better in some areas. But they should be thought of as an alternative to the existing formats and not a superior replacement.
      - methodOverdrive 11y ago
        I would argue that unums are a "superior replacement" for doubles in many cases, though: in the case that you support unums that are "wide" enough, you can represent doubles exactly, plus you have additional values, plus some nice rules about when approximation error occurs/is propagated and not as many bits need to be stored or moved around on buses. It'll be a while before there's an implementation anywhere near as fast as existing FPUs, but Gustafson makes a good argument for his format. Personally, I'm more interested in the correctness benefits than the space/power/time savings - even if unums are never faster than 64-bit floats, they present an interesting way to do real-number arithmetic and my brief exposure to them leaves me much more confident that I could write numerical algorithms correctly than with doubles - I do numerical/statistical algorithms with doubles in my work, and it's really a pain to reason about things that the "uncertain" (open-inverval) values of the unum format would greatly simplify. They're also an inferior replacement in the case that you want to take advantage of highly-optimized hardware, and that getting a correct answer doesn't really matter. I don't see unums replacing floats for, say, video game graphics. But for numerical computation, it seems like the only real flaw with unums compared to doubles is the nonexistence of a hardware implementation, and the existing popularity of doubles.
        11y ago
- Lawtonfogle 11y ago
  If I had a number system of -100, 0, and 100, could I claim all real numbers are represented, just not to arbitrary precision? With n bits, there are 2^n possible representations max. If you can say all real numbers are represented for n around 30, or 60, or even 1,000,000, then can't you say the same for n equal to 1 or 2? Now I think we can say some representations are better than others (at least for certain applications). It may even be possible that some representation with a given n can be better in all cases than a representation with a larger n. So an n equals 1 system will obviously be terrible compared to many systems with n around 30 or 60. But I'm not really concerned with that point, just the claim of being able to represent all real numbers.
  - dnautics 11y ago
    Sure, you can claim that but it doesn't mean squat unless your underlying circuits correctly process operations (*,+,/etc) on the representation in a way that is faithful to your claim. In the book he talks about a simple unum with values -inf, less than -2, -2, between -2 ... -1, -1, between -1 ... 0, 0, 0...1, 1, 1...2, 2, > 2, and inf, also intervals like 0...2, -2...0 etc 1...inf, emerge when you intentionally use less precision. This is a mathematically closed system that represents all real numbers and is even useful!
- deleted 11y ago
  [deleted]
bmh100 11y ago
I am not sure that I understand what you're saying. Given a charitable reading of the presentation, the author seems to be saying that his standard explicitly specifies range of values, as opposed to the IEEE Float. It did not seem like he was saying that he could explicitly represent an infinite amount of exact, distinct values using a finite number of bits. Low level data structures are not my area of expertise, so did I misunderstand what he was saying or what you are saying?
- stephencanon 11y ago
  Under that reading, he's saying nothing: just represent the interval [-inf, inf] as "0" and call it a day. So assuming that he's saying anything at all, he's at least being imprecise, and the actually claim should be something like "represent any dyadic interval using a finite number of bits".
  - deleted 11y ago
    [deleted]
  - methodOverdrive 11y ago
    He's a bit showy about the format. Wish he would just put out a technical paper. Anyway, I guess his motivation might be "you can represent any real number (with finite bits, and therefore finite precision)". In the book, he presents an interesting case: little 4-bit versions of the Unum that can represent: -inf, (-inf, -2), -2, (-2, -1), (-1, -1/2), -1/2, (-1/2, -0), -0, 0, (0, 1/2), 1/2, (1/2, 1), 1, (1, 2), 2, (2, inf), inf. Putting together a pair of them, the book outlines simple interval arithmetic (where pairs of numbers can represent any interval between numbers on the line above, and single numbers can represent some of the closed intervals as above). The reason these are kind of neat is that using the standard Unum algorithms (without any fudging), you can get "correct" (albeit terribly imprecise) results for many real number computations. Questions like "is there a number satisfying a numerical predicate in some range?" or the value of a trigonmetric or exponential expression will come out "correct" (but you might get an answer like (-inf, inf)). If things work out as well as he claims (and demonstrates for some cases), then you can basically do the math to figure out how precise you want to be and choose an appropriate specialization of the format - or take advantage of the format's flexibility and do computations starting at a low precision and increasing precision until you are satisfied. In particular, it's kind of cool that you can do computations with little 8-bit intervals, and possibly circumvent doing more expensive computations (e.g. if you test if a property will hold anywhere in the Unum range and it won't hold anywhere, assuming you (and Gustafson) have done the math right, you can avoid doing more expensive checks with increased precision). Anyway, point is, the presentations are kind of flashy and misleading - and you're right, you can't represent any real number (just finitely representable dyadic intervals)... but the format itself _does_ seem promising...

dnautics 11y ago

All real numbers are representable, but not necessarily to arbitrary precision. You should really read the book. A lot of the atomic operations seem cumbersome, because the unum doesn't have a fixed size representation, but you just get over that when you remember that the real problem is shuttling data over buses. More compute transistors is not a problem.

stephencanon 11y ago
No. The set of "representable" (i.e. computable) numbers is countable (because the set of programs is countable), so in fact almost all real numbers cannot be represented.
- yoklov 11y ago
  I got the impression that the unum explicitly modeled a range of values, so I'm not sure that applies. Not an expert here though.
  - stephencanon 11y ago
    That's fine, but then you're representing dyadic intervals, not real numbers. Simple question: what's unum[sqrt(2)]?
    - dnautics 11y ago
      Rougly speaking It would be 1.414... + plus a bit that indicates the result is between two adjacent exact values. This bit would not be set if the result were exact. It's not the same as dyadic interval math, it's kind of a hybrid.
      - davisourus 11y ago
        And you could set the environmental variables to be as precise as you need. If you need 29 digits of precision, you can quickly show that you know 1.4142135623730950488016887242 and nothing more. A reasonable metaphor would be that you cannot draw all of the Mandelbrot diagram, but you can render any piece of it to any resolution you choose. Being able to describe it precisely, and to know the limits of your accuracy, is useful.
  - Lawtonfogle 11y ago
    Regardless if it is representing number, ranges, or a mix of both, there are still 2^n maximum possible representations for n bits. Perhaps you could create a mix of numbers and ranges equal to (2^n)-2 and then add one range that is from the lowest number represented to negative infinity and add another that does the same for positives. But I can do that system with -, 0, +, NAN. See, I just represented all numbers. It isn't as useful, but boy are there savings on storage, cost, and computation time. Unums shouldn't be seen as better than ints, longs, floats, or doubles anymore than a double is seen as better than an int. They have different uses and strengths, and there are problems where none are a good choice. Perhaps unums are the best choice for some problems. Perhaps they are clearly and significantly better in some areas. But they should be thought of as an alternative to the existing formats and not a superior replacement.
    - methodOverdrive 11y ago
      I would argue that unums are a "superior replacement" for doubles in many cases, though: in the case that you support unums that are "wide" enough, you can represent doubles exactly, plus you have additional values, plus some nice rules about when approximation error occurs/is propagated and not as many bits need to be stored or moved around on buses. It'll be a while before there's an implementation anywhere near as fast as existing FPUs, but Gustafson makes a good argument for his format. Personally, I'm more interested in the correctness benefits than the space/power/time savings - even if unums are never faster than 64-bit floats, they present an interesting way to do real-number arithmetic and my brief exposure to them leaves me much more confident that I could write numerical algorithms correctly than with doubles - I do numerical/statistical algorithms with doubles in my work, and it's really a pain to reason about things that the "uncertain" (open-inverval) values of the unum format would greatly simplify. They're also an inferior replacement in the case that you want to take advantage of highly-optimized hardware, and that getting a correct answer doesn't really matter. I don't see unums replacing floats for, say, video game graphics. But for numerical computation, it seems like the only real flaw with unums compared to doubles is the nonexistence of a hardware implementation, and the existing popularity of doubles.
      - 11y ago
Lawtonfogle 11y ago
If I had a number system of -100, 0, and 100, could I claim all real numbers are represented, just not to arbitrary precision? With n bits, there are 2^n possible representations max. If you can say all real numbers are represented for n around 30, or 60, or even 1,000,000, then can't you say the same for n equal to 1 or 2? Now I think we can say some representations are better than others (at least for certain applications). It may even be possible that some representation with a given n can be better in all cases than a representation with a larger n. So an n equals 1 system will obviously be terrible compared to many systems with n around 30 or 60. But I'm not really concerned with that point, just the claim of being able to represent all real numbers.
- dnautics 11y ago
  Sure, you can claim that but it doesn't mean squat unless your underlying circuits correctly process operations (*,+,/etc) on the representation in a way that is faithful to your claim. In the book he talks about a simple unum with values -inf, less than -2, -2, between -2 ... -1, -1, between -1 ... 0, 0, 0...1, 1, 1...2, 2, > 2, and inf, also intervals like 0...2, -2...0 etc 1...inf, emerge when you intentionally use less precision. This is a mathematically closed system that represents all real numbers and is even useful!
deleted 11y ago
[deleted]

bmh100 11y ago

I am not sure that I understand what you're saying. Given a charitable reading of the presentation, the author seems to be saying that his standard explicitly specifies range of values, as opposed to the IEEE Float. It did not seem like he was saying that he could explicitly represent an infinite amount of exact, distinct values using a finite number of bits. Low level data structures are not my area of expertise, so did I misunderstand what he was saying or what you are saying?

stephencanon 11y ago
Under that reading, he's saying nothing: just represent the interval [-inf, inf] as "0" and call it a day. So assuming that he's saying anything at all, he's at least being imprecise, and the actually claim should be something like "represent any dyadic interval using a finite number of bits".
- deleted 11y ago
  [deleted]
- methodOverdrive 11y ago
  He's a bit showy about the format. Wish he would just put out a technical paper. Anyway, I guess his motivation might be "you can represent any real number (with finite bits, and therefore finite precision)". In the book, he presents an interesting case: little 4-bit versions of the Unum that can represent: -inf, (-inf, -2), -2, (-2, -1), (-1, -1/2), -1/2, (-1/2, -0), -0, 0, (0, 1/2), 1/2, (1/2, 1), 1, (1, 2), 2, (2, inf), inf. Putting together a pair of them, the book outlines simple interval arithmetic (where pairs of numbers can represent any interval between numbers on the line above, and single numbers can represent some of the closed intervals as above). The reason these are kind of neat is that using the standard Unum algorithms (without any fudging), you can get "correct" (albeit terribly imprecise) results for many real number computations. Questions like "is there a number satisfying a numerical predicate in some range?" or the value of a trigonmetric or exponential expression will come out "correct" (but you might get an answer like (-inf, inf)). If things work out as well as he claims (and demonstrates for some cases), then you can basically do the math to figure out how precise you want to be and choose an appropriate specialization of the format - or take advantage of the format's flexibility and do computations starting at a low precision and increasing precision until you are satisfied. In particular, it's kind of cool that you can do computations with little 8-bit intervals, and possibly circumvent doing more expensive computations (e.g. if you test if a property will hold anywhere in the Unum range and it won't hold anywhere, assuming you (and Gustafson) have done the math right, you can avoid doing more expensive checks with increased precision). Anyway, point is, the presentations are kind of flashy and misleading - and you're right, you can't represent any real number (just finitely representable dyadic intervals)... but the format itself _does_ seem promising...