4 ms·

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.

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.
- thethirdone 6y ago
  > 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. I don't doubt that my naive solution would be slow relative (probably at least x4) to an ideal one, but I think it would be fast relative to system calls. My naive implementation would not use a bignum for step two. I would just use a use a integer with size large enough to fit maximum mantissa * 5^log_2(maximum mantissa) which can be rounded up to a number with 4 x the number of bits as the binary mantissa (1 for maximum mantissa and 3 for the multiplication with 5). So a 128 bit number is definitely enough for a 32 bit float. And with that you can still use a normal modulus and divide for step 3. > 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. It definitely seems like there are some optimizations that I had not considered. I will probably give a close look into the algorithm at some point. It does also seem like the given algorithm roughly follows my psuedo-code though. My psuedo-code lumped your steps 1 and 2 into step 1 and then would include an extra digit rather than stop at the common prefix. This means my algorithm would show 1.2 for the float closest to 1.2 (0x3F99999A) whereas that algorithm would show 1. Its possible (and probable) I am misunderstanding your simplification of step 3 from the Ryu paper.
  - jcranmer 6y ago
    > I would just use a use a integer with size large enough to fit maximum mantissa * 5^log_2(maximum mantissa) It should be mantissa * 5^O(maximum binary exponent), not O(log mantissa).

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.

thethirdone 6y ago
> 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. I don't doubt that my naive solution would be slow relative (probably at least x4) to an ideal one, but I think it would be fast relative to system calls. My naive implementation would not use a bignum for step two. I would just use a use a integer with size large enough to fit maximum mantissa * 5^log_2(maximum mantissa) which can be rounded up to a number with 4 x the number of bits as the binary mantissa (1 for maximum mantissa and 3 for the multiplication with 5). So a 128 bit number is definitely enough for a 32 bit float. And with that you can still use a normal modulus and divide for step 3. > 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. It definitely seems like there are some optimizations that I had not considered. I will probably give a close look into the algorithm at some point. It does also seem like the given algorithm roughly follows my psuedo-code though. My psuedo-code lumped your steps 1 and 2 into step 1 and then would include an extra digit rather than stop at the common prefix. This means my algorithm would show 1.2 for the float closest to 1.2 (0x3F99999A) whereas that algorithm would show 1. Its possible (and probable) I am misunderstanding your simplification of step 3 from the Ryu paper.
- jcranmer 6y ago
  > I would just use a use a integer with size large enough to fit maximum mantissa * 5^log_2(maximum mantissa) It should be mantissa * 5^O(maximum binary exponent), not O(log mantissa).