9 ms·

> Another biggie is floating point. Converting binary floating point to decimal floating point and vice versa is VERY VERY VERY SLOW, difficult to get right, an

> Another biggie is floating point. Converting binary floating point to decimal floating point and vice versa is VERY VERY VERY SLOW, difficult to get right, and difficult to predict results. I haven't read deeply into IEEE 754-2008 for decimal floating points, but it seems like it should be pretty fast (relative to system calls) to convert binary to decimal because 10 has a factor of 2. > Unfortunately, ieee754 decimal float just isn't getting any adoption, so we're stuck doing these costly conversions every time we deal with text formats or big float implementations. Is there any reason big float implementations should use decimal rather than binary? It seems like it is very straightforward to make a binary big float, and do operations on it. In fact, IEEE 754-2008 specifies interchange formats for all binary floats of bit lengths >= 128 where length is a multiple of 32.

saagarjha 6y ago
> it seems like it should be pretty fast (relative to system calls) to convert binary to decimal because 10 has a factor of 2 I don’t see how this would matter?
- thethirdone 6y ago
  Any binary float is exactly representable in a decimal float with enough digits. This is not true in the other direction. for example 1/5th or 0.2 is 0.001100110011... in binary. So a simple solution for binary to decimal is to express it as a larger decimal float than you intend to show and then crop off digits if it doesn't fit in your destination format.
kstenerud 6y ago
> haven't read deeply into IEEE 754-2008 for decimal floating points, but it seems like it should be pretty fast (relative to system calls) to convert binary to decimal because 10 has a factor of 2. It could be fast, but legacy has doomed us all to a "canonical" conversion of sorts, where any other conversion algorithm will likely yield off-by-a-tiny-amount differences in the binary format (like 1.200000000031 instead of 1.2). There are in fact fairly simple conversions that can be done, but they yield results that are incompatible with printf. > Is there any reason big float implementations should use decimal rather than binary? At the end of the day, we work in decimal. So every binary result we calculate has to be converted to its decimal approximation (the meaning of which is subject to convention). Rounding is also an issue, because you want to keep your number of significant digits within reason to avoid false precision errors. Doing all of this in a different base that can't be 1:1 converted adds a whole slew of bug opportunities and corner cases.
- thethirdone 6y ago
  > It could be fast, but legacy has doomed us all to a "canonical" conversion of sorts, where any other conversion algorithm will likely yield off-by-a-tiny-amount differences in the binary format (like 1.200000000031 instead of 1.2). There are in fact fairly simple conversions that can be done, but they yield results that are incompatible with printf. I would argue that the issue here is not the binary -> decimal conversion. People expect when they write "1.2" they get that exact value, but that is not representable with binary floats. So the weird value you get is the closest value that is representable. I definitely agree that there aren't good options to make a round trip fast and intuitive. > At the end of the day, we work in decimal. So every binary result we calculate has to be converted to its decimal approximation (the meaning of which is subject to convention). Rounding also is an issue, because you want to keep your number of significant digits within reason to avoid false precision errors. Doing all of this in a different base that can't be 1:1 converted adds a whole slew of bug opportunities and corner cases. If you are keeping track of significant digits, you can definitely work in binary and render the binary value to the significant decimal digits. In particular for scientific work, if you cannot handle the issues with binary floating point, you probably are not handling uncertainty well enough. The corner cases you would hit would already have been bugs, but you just wouldn't have noticed. One particular setup I am a fan of is keeping track of an upper and lower bound for all of your numbers which allows your computations to introduce a small amount of error , but you will still have objectively true statements when converting back to decimal to read. For example "1.2" would be converted to the range "1.001-1.010" in binary with 4 significant figs which when converted back would be the range "1.125-1.25". Its not perfect, but it steps around a lot of typical floating point problems.
- enriquto 6y ago
  > At the end of the day, we work in decimal. What? No. I have spent much of my life working with floating point numbers and never ever had to resort to anything decimal for serious purposes (that is, except for some occasional printing of a number for debugging).
  - smabie 6y ago
    Are you telling me that you do math with a pen and paper in binary? everything is decimal. Computers aren't, but almost everyone tries to paper over that fact as much as possible.
Someone 6y ago
“it seems like it should be pretty fast (relative to system calls) to convert binary to decimal because 10 has a factor of 2“ The problem isn’t to find a decimal representation, it’s to find one that round-trips and, among those, the ‘best’ one, and do that fast. With best, people typically mean that the IEEE float closest to ⅒ prints as “0.1”, the one closest to 42/100 as “0.42”, etc. In general, you want to produce all “0.x”, “0.xx”, “0.xxx”, etc. until you run out of IEEE numbers in (0,1). It took surprisingly long for _any_ implementation to get there (I think it was Steele, around 1980, published in 1990) http://www.ryanjuckett.com/programming/printing-floating-point-numbers/ http://www.ryanjuckett.com/programming/printing-floating-poi... has a good introduction to the problem, insofar as I am qualified to judge that.
- thethirdone 6y ago
  I definitely agree that that is a much harder problem than faithfully converting a binary float to a decimal one. But doing it correctly shouldn't be too slow. Some rough psuedo-code for what I would do without looking at any references: - convert the binary float one higher and lower than the given binary float. - find the point at which they diverge - Generate the given value rounded to that digit + 1 That probably is off by a digit in some case, but it should be reasonably fast, and is pretty simple.
  - klodolph 6y ago
    The algorithms in question are off by a digit in no cases at all, they are correct for all inputs. If you actually start putting your pseudocode into real code you’ll see how quickly it can go wrong, if you want to correctly convert all inputs. For example, once you get past 10^22, you can no longer do a simple division or multiplication to get the leading digit, because 10^22 cannot be represented as a double. For numbers 10^22 or below, you can just use ordinary division or multiplication and rely on the fact that this will be rounded correctly. It’s a fun exercise to write an exact converter that works in the range -10^22..+10^22, though. It doesn’t require much code.
  - jcranmer 6y ago
    Recall that the input to your algorithm gives you a binary mantissa and a binary exponent, and you need to convert this to a decimal. The Ryu paper outlines the process as follows: * Extract e and m from the float, and normalize the next-smallest and next-largest numbers to handle subnormal and largest/smallest mantissa for a given exponent cases. * Convert the adjusted mantissas to base-10 mantissas by multiplying by a power of 2, or by multiplying by a power of 1/5. * Print out all of the common prefix of the smallest and largest values. Except it turns out that doing the last two steps naively is actually quite slow: you need bignum support to do step 2 correctly, and bignum div/mod to do step 3 correctly. What Ryu does to speed it up is it uses a lookup table to work out a bound on the prefix size to skip several iterations of "find the common prefix", proves that everything can be done with just 128-bit (for doubles)/64-bit (for floats) math, and then precomputes the necessary multiplications of 2^a/5^b via a lookup table.

saagarjha 6y ago

> it seems like it should be pretty fast (relative to system calls) to convert binary to decimal because 10 has a factor of 2 I don’t see how this would matter?

thethirdone 6y ago
Any binary float is exactly representable in a decimal float with enough digits. This is not true in the other direction. for example 1/5th or 0.2 is 0.001100110011... in binary. So a simple solution for binary to decimal is to express it as a larger decimal float than you intend to show and then crop off digits if it doesn't fit in your destination format.

kstenerud 6y ago

> haven't read deeply into IEEE 754-2008 for decimal floating points, but it seems like it should be pretty fast (relative to system calls) to convert binary to decimal because 10 has a factor of 2. It could be fast, but legacy has doomed us all to a "canonical" conversion of sorts, where any other conversion algorithm will likely yield off-by-a-tiny-amount differences in the binary format (like 1.200000000031 instead of 1.2). There are in fact fairly simple conversions that can be done, but they yield results that are incompatible with printf. > Is there any reason big float implementations should use decimal rather than binary? At the end of the day, we work in decimal. So every binary result we calculate has to be converted to its decimal approximation (the meaning of which is subject to convention). Rounding is also an issue, because you want to keep your number of significant digits within reason to avoid false precision errors. Doing all of this in a different base that can't be 1:1 converted adds a whole slew of bug opportunities and corner cases.

thethirdone 6y ago
> It could be fast, but legacy has doomed us all to a "canonical" conversion of sorts, where any other conversion algorithm will likely yield off-by-a-tiny-amount differences in the binary format (like 1.200000000031 instead of 1.2). There are in fact fairly simple conversions that can be done, but they yield results that are incompatible with printf. I would argue that the issue here is not the binary -> decimal conversion. People expect when they write "1.2" they get that exact value, but that is not representable with binary floats. So the weird value you get is the closest value that is representable. I definitely agree that there aren't good options to make a round trip fast and intuitive. > At the end of the day, we work in decimal. So every binary result we calculate has to be converted to its decimal approximation (the meaning of which is subject to convention). Rounding also is an issue, because you want to keep your number of significant digits within reason to avoid false precision errors. Doing all of this in a different base that can't be 1:1 converted adds a whole slew of bug opportunities and corner cases. If you are keeping track of significant digits, you can definitely work in binary and render the binary value to the significant decimal digits. In particular for scientific work, if you cannot handle the issues with binary floating point, you probably are not handling uncertainty well enough. The corner cases you would hit would already have been bugs, but you just wouldn't have noticed. One particular setup I am a fan of is keeping track of an upper and lower bound for all of your numbers which allows your computations to introduce a small amount of error , but you will still have objectively true statements when converting back to decimal to read. For example "1.2" would be converted to the range "1.001-1.010" in binary with 4 significant figs which when converted back would be the range "1.125-1.25". Its not perfect, but it steps around a lot of typical floating point problems.
enriquto 6y ago
> At the end of the day, we work in decimal. What? No. I have spent much of my life working with floating point numbers and never ever had to resort to anything decimal for serious purposes (that is, except for some occasional printing of a number for debugging).
- smabie 6y ago
  Are you telling me that you do math with a pen and paper in binary? everything is decimal. Computers aren't, but almost everyone tries to paper over that fact as much as possible.

Someone 6y ago

“it seems like it should be pretty fast (relative to system calls) to convert binary to decimal because 10 has a factor of 2“ The problem isn’t to find a decimal representation, it’s to find one that round-trips and, among those, the ‘best’ one, and do that fast. With best, people typically mean that the IEEE float closest to ⅒ prints as “0.1”, the one closest to 42/100 as “0.42”, etc. In general, you want to produce all “0.x”, “0.xx”, “0.xxx”, etc. until you run out of IEEE numbers in (0,1). It took surprisingly long for _any_ implementation to get there (I think it was Steele, around 1980, published in 1990) http://www.ryanjuckett.com/programming/printing-floating-point-numbers/ http://www.ryanjuckett.com/programming/printing-floating-poi... has a good introduction to the problem, insofar as I am qualified to judge that.

thethirdone 6y ago
I definitely agree that that is a much harder problem than faithfully converting a binary float to a decimal one. But doing it correctly shouldn't be too slow. Some rough psuedo-code for what I would do without looking at any references: - convert the binary float one higher and lower than the given binary float. - find the point at which they diverge - Generate the given value rounded to that digit + 1 That probably is off by a digit in some case, but it should be reasonably fast, and is pretty simple.
- klodolph 6y ago
  The algorithms in question are off by a digit in no cases at all, they are correct for all inputs. If you actually start putting your pseudocode into real code you’ll see how quickly it can go wrong, if you want to correctly convert all inputs. For example, once you get past 10^22, you can no longer do a simple division or multiplication to get the leading digit, because 10^22 cannot be represented as a double. For numbers 10^22 or below, you can just use ordinary division or multiplication and rely on the fact that this will be rounded correctly. It’s a fun exercise to write an exact converter that works in the range -10^22..+10^22, though. It doesn’t require much code.
- jcranmer 6y ago
  Recall that the input to your algorithm gives you a binary mantissa and a binary exponent, and you need to convert this to a decimal. The Ryu paper outlines the process as follows: * Extract e and m from the float, and normalize the next-smallest and next-largest numbers to handle subnormal and largest/smallest mantissa for a given exponent cases. * Convert the adjusted mantissas to base-10 mantissas by multiplying by a power of 2, or by multiplying by a power of 1/5. * Print out all of the common prefix of the smallest and largest values. Except it turns out that doing the last two steps naively is actually quite slow: you need bignum support to do step 2 correctly, and bignum div/mod to do step 3 correctly. What Ryu does to speed it up is it uses a lookup table to work out a bound on the prefix size to skip several iterations of "find the common prefix", proves that everything can be done with just 128-bit (for doubles)/64-bit (for floats) math, and then precomputes the necessary multiplications of 2^a/5^b via a lookup table.