4 ms·

Binary representation of floating-point numbers

49 points by trekhleb 5y ago

etaioinshrdlu 5y ago
After reading up on Posits I'm convinced we would be better off if we switched to them wholesale: https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/posits/ https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/posits... Right after we finish rewriting everything in Rust, of course.
- Traster 5y ago
  I tried reading up on that, but that article is very hard to follow: >At the heavenly North of the circle, symbolizing the Alpha and Omega, Our Father to which we solemly pray, lies the glorious positive and negative infinity. At its opposite, the wicked, immoral South of the circle, lies nothing of value, the value 000. Meanwhile, on the earthly plane, God's children enjoy free will, where they choose between positive one at the East and negative one at the West. Who thought it would be a good idea to throw weirds jokes into a description of a number system? I'll probably just file posits next to Tensors in my mental model of the world (Tensors are just matrices for people with egos).
  - MisterTea 5y ago
    > Who thought it would be a good idea to throw weirds jokes into a description of a number system? What were you expecting from an author who titled the article "The Cult of Posits"? > I'll probably just file posits next to Tensors in my mental model of the world (Tensors are just matrices for people with egos). You forgot to add Rust to that list >:-)
- nightcracker 5y ago
  In my opinion two things are very important for your core real number type: 1. Closed operations without exceptions; 2. a total strict ordering. Additionally, being able to represent positive and negative infinity is convenient and makes closing the operations easier without having to resort too much to the catch-all nan/undefined value. So rather than a single point at positive/negative infinity in posits, which would once again introduce the mistake of a non-total or non-strict order and lack of exception-free math, I would much prefer this (for the 4-bit posit, listed in ascending order): 1001 -> -111 -> -inf 1010 -> -110 -> -4 1011 -> -101 -> -2 1100 -> -100 -> -1 1101 -> -011 -> -1/2 1110 -> -010 -> -1/4 1111 -> -001 -> -1/16 1000 -> -000 -> undefined 0000 -> +000 -> 0 0001 -> +001 -> 1/16 0010 -> +010 -> 1/4 0011 -> +011 -> 1/2 0100 -> +100 -> 1 0101 -> +101 -> 2 0110 -> +110 -> 4 0111 -> +111 -> inf And yes, in this scheme 'undefined' would compare smaller than zero but bigger than any negative number. It is a bit arbitrary but much better than not having a total order. Any operation involving undefined would be undefined. EDIT: it seems that the original posit definition is also workable, where there is never any overflow and instead just rounding to the nearest number. The unfortunate thing is how the +/-inf value is labelled: it should just be called 'nan' or 'undefined' or 'indeterminate' or something similar. It can never be generated by overflowing operations. There should definitely be a total strict ordering however, so I do still recommend placing the undefined value right next to zero.
  - nwatson 5y ago
    This scheme leaves out "-0" aka "negative zero" which apparently might be important in some contexts. Incomplete view : https://softwareengineering.stackexchange.com/questions/280648/why-is-negative-zero-important https://softwareengineering.stackexchange.com/questions/2806...
    - nightcracker 5y ago
      I'm not convinced by this argument, and would favour x/0 to return 'undefined' rather than an infinity.
      - hvdijk 5y ago
        You wrote: > Additionally, being able to represent positive and negative infinity is convenient and makes closing the operations easier without having to resort too much to the catch-all nan/undefined value. Which operations were you thinking about if not x/0?
        nightcracker 5y ago
        Mainly for detecting overflow in an exception-free manner. Perhaps for consistency there should also be two infinitesimal constants for detecting underflow: 1001 -> -111 -> -inf 1010 -> -110 -> -4 1011 -> -101 -> -2 1100 -> -100 -> -1 1101 -> -011 -> -1/2 1110 -> -010 -> -1/4 1111 -> -001 -> -1/inf 1000 -> -000 -> undefined 0000 -> +000 -> 0 0001 -> +001 -> 1/inf 0010 -> +010 -> 1/4 0011 -> +011 -> 1/2 0100 -> +100 -> 1 0101 -> +101 -> 2 0110 -> +110 -> 4 0111 -> +111 -> inf Then 1/0 would still remain undefined but 1/(1/inf) would be inf. In particular the operations would be (in case of ambiguity first rule applies, s is a sign variable, x, y are arbitrary variables, i, j are infinity or infinitesimal variables): undef + x = undef undef * x = undef undef / x = undef x / undef = undef x / 0 = undef inf + -inf = undef 1/inf + -1/inf = undef s*inf + x = s*inf s*1/inf + x = x i*i = i i*j = undef i*x = i i/j = undef i/x = i x/(s*inf) = s*1/inf x/(s*1/inf) = s*inf Then finally the infinities would get introduced by overflow, and infinitesimals by underflow.
- bertr4nd 5y ago
  I find this post to be more instructive, with more detail and no quasi-religious goofiness: https://www.johndcook.com/blog/2018/04/11/anatomy-of-a-posit-number/ https://www.johndcook.com/blog/2018/04/11/anatomy-of-a-posit...
ithkuil 5y ago
Isn't the ability to distinguish negative infinity from positive infinity a good thing?
hoseja 5y ago
The representation of negatives is funny. Integers use two's complement, floats use sign bit and float exponents use bias.
- tonyedgecombe 5y ago
  I think it's interesting that some of the fundamental types we rely on (numbers, strings, dates and times) are full of complexity and ready to trip up the unwary.
tromp 5y ago
The 16 bit float example fails to show that IEEE754 uses an implicitly set most significant bit on the fraction. The reason being that if the most significant bit were 0, then the fraction could be shifted left and the exponent lowered by 1 to compensate, until the msb is 1, a process called normalization.
gautamcgoel 5y ago
It seems to me that we should use fixed point arithmetic to represent real numbers. The two key advantages are 1) we can reuse integer ALUs to implement this arithmetic, with no need for dedicated FP units, 2) fixed point arithmetic is simple and easy to reason about and 3) conversion to and from integer types becomes trivial.
kofejnik 5y ago
as someone not very familiar with ieee-754 I played with the linked interactive tool, and 0000000000000000 evaluates to 0.000030517578125 (2^-15), as biased exponent is -15 and mantissa is 0. So how do you represent 0 then?
- detaro 5y ago
  that's a special case not covered in that tool, all zeros in exponent and mantissa is defined to be 0. (it distinguishes between 0 and -0, so the sign bit still applies)

49 points by trekhleb 5y ago

After reading up on Posits I'm convinced we would be better off if we switched to them wholesale: https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/posits/ https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/posits... Right after we finish rewriting everything in Rust, of course.

Traster 5y ago
I tried reading up on that, but that article is very hard to follow: >At the heavenly North of the circle, symbolizing the Alpha and Omega, Our Father to which we solemly pray, lies the glorious positive and negative infinity. At its opposite, the wicked, immoral South of the circle, lies nothing of value, the value 000. Meanwhile, on the earthly plane, God's children enjoy free will, where they choose between positive one at the East and negative one at the West. Who thought it would be a good idea to throw weirds jokes into a description of a number system? I'll probably just file posits next to Tensors in my mental model of the world (Tensors are just matrices for people with egos).
- MisterTea 5y ago
  > Who thought it would be a good idea to throw weirds jokes into a description of a number system? What were you expecting from an author who titled the article "The Cult of Posits"? > I'll probably just file posits next to Tensors in my mental model of the world (Tensors are just matrices for people with egos). You forgot to add Rust to that list >:-)
nightcracker 5y ago
In my opinion two things are very important for your core real number type: 1. Closed operations without exceptions; 2. a total strict ordering. Additionally, being able to represent positive and negative infinity is convenient and makes closing the operations easier without having to resort too much to the catch-all nan/undefined value. So rather than a single point at positive/negative infinity in posits, which would once again introduce the mistake of a non-total or non-strict order and lack of exception-free math, I would much prefer this (for the 4-bit posit, listed in ascending order): 1001 -> -111 -> -inf 1010 -> -110 -> -4 1011 -> -101 -> -2 1100 -> -100 -> -1 1101 -> -011 -> -1/2 1110 -> -010 -> -1/4 1111 -> -001 -> -1/16 1000 -> -000 -> undefined 0000 -> +000 -> 0 0001 -> +001 -> 1/16 0010 -> +010 -> 1/4 0011 -> +011 -> 1/2 0100 -> +100 -> 1 0101 -> +101 -> 2 0110 -> +110 -> 4 0111 -> +111 -> inf And yes, in this scheme 'undefined' would compare smaller than zero but bigger than any negative number. It is a bit arbitrary but much better than not having a total order. Any operation involving undefined would be undefined. EDIT: it seems that the original posit definition is also workable, where there is never any overflow and instead just rounding to the nearest number. The unfortunate thing is how the +/-inf value is labelled: it should just be called 'nan' or 'undefined' or 'indeterminate' or something similar. It can never be generated by overflowing operations. There should definitely be a total strict ordering however, so I do still recommend placing the undefined value right next to zero.
- nwatson 5y ago
  This scheme leaves out "-0" aka "negative zero" which apparently might be important in some contexts. Incomplete view : https://softwareengineering.stackexchange.com/questions/280648/why-is-negative-zero-important https://softwareengineering.stackexchange.com/questions/2806...
  - nightcracker 5y ago
    I'm not convinced by this argument, and would favour x/0 to return 'undefined' rather than an infinity.
    - hvdijk 5y ago
      You wrote: > Additionally, being able to represent positive and negative infinity is convenient and makes closing the operations easier without having to resort too much to the catch-all nan/undefined value. Which operations were you thinking about if not x/0?
      - nightcracker 5y ago
        Mainly for detecting overflow in an exception-free manner. Perhaps for consistency there should also be two infinitesimal constants for detecting underflow: 1001 -> -111 -> -inf 1010 -> -110 -> -4 1011 -> -101 -> -2 1100 -> -100 -> -1 1101 -> -011 -> -1/2 1110 -> -010 -> -1/4 1111 -> -001 -> -1/inf 1000 -> -000 -> undefined 0000 -> +000 -> 0 0001 -> +001 -> 1/inf 0010 -> +010 -> 1/4 0011 -> +011 -> 1/2 0100 -> +100 -> 1 0101 -> +101 -> 2 0110 -> +110 -> 4 0111 -> +111 -> inf Then 1/0 would still remain undefined but 1/(1/inf) would be inf. In particular the operations would be (in case of ambiguity first rule applies, s is a sign variable, x, y are arbitrary variables, i, j are infinity or infinitesimal variables): undef + x = undef undef * x = undef undef / x = undef x / undef = undef x / 0 = undef inf + -inf = undef 1/inf + -1/inf = undef s*inf + x = s*inf s*1/inf + x = x i*i = i i*j = undef i*x = i i/j = undef i/x = i x/(s*inf) = s*1/inf x/(s*1/inf) = s*inf Then finally the infinities would get introduced by overflow, and infinitesimals by underflow.
bertr4nd 5y ago
I find this post to be more instructive, with more detail and no quasi-religious goofiness: https://www.johndcook.com/blog/2018/04/11/anatomy-of-a-posit-number/ https://www.johndcook.com/blog/2018/04/11/anatomy-of-a-posit...

ithkuil 5y ago

Isn't the ability to distinguish negative infinity from positive infinity a good thing?

hoseja 5y ago

The representation of negatives is funny. Integers use two's complement, floats use sign bit and float exponents use bias.

tonyedgecombe 5y ago
I think it's interesting that some of the fundamental types we rely on (numbers, strings, dates and times) are full of complexity and ready to trip up the unwary.

tromp 5y ago

The 16 bit float example fails to show that IEEE754 uses an implicitly set most significant bit on the fraction. The reason being that if the most significant bit were 0, then the fraction could be shifted left and the exponent lowered by 1 to compensate, until the msb is 1, a process called normalization.

gautamcgoel 5y ago

It seems to me that we should use fixed point arithmetic to represent real numbers. The two key advantages are 1) we can reuse integer ALUs to implement this arithmetic, with no need for dedicated FP units, 2) fixed point arithmetic is simple and easy to reason about and 3) conversion to and from integer types becomes trivial.

kofejnik 5y ago

as someone not very familiar with ieee-754 I played with the linked interactive tool, and 0000000000000000 evaluates to 0.000030517578125 (2^-15), as biased exponent is -15 and mantissa is 0. So how do you represent 0 then?

detaro 5y ago
that's a special case not covered in that tool, all zeros in exponent and mantissa is defined to be 0. (it distinguishes between 0 and -0, so the sign bit still applies)