4 ms·

Good job! Though I would have added a unit test to iterate over complete 2^64 set of values and compare the output to Double.parseDouble().

haberman 6y ago
Even if you could parse a double in a single cycle, it would take 292 years to run through 2^64 cases on a 2GHz machine. https://www.google.com/search?q=2**64+%2F+2GHz&oq=2**64+%2F+2GHz https://www.google.com/search?q=2**64+%2F+2GHz&oq=2**64+%2F+... Also, while there are only 2^64 distinct double values, there are many more string representations than that. For example, "1" and "1.0" are the same underlying value, but a parser needs to be able to handle both.
- java-man 6y ago
  My point is about comparing accelerated code behavior to the standard java Double.
  - stefs 6y ago
    your point is still invalid because it's pointless to attempt what you're suggesting. and that's not how unit tests work. unit testing doesn't mean that all possible values have to be tested. usually it's about code paths, i.e. standard, error and edge cases.
    - java-man 6y ago
      My point is based on experience. Yes, it's probably too much to ask to test all 2^64 cases, but I've been dealing with code in production that was failing precisely because some values lead to code paths that gave incorrect results. In this particular case, I would have tested 2^N where N>32 random, unique values, at a minimum. Of course, it depends on who the customer is. Some customers can tolerate a few bugs here and there; and some would incur million dollar losses.
    - dodobirdlord 6y ago
      The successes of fuzzing projects like oss-fuzz have demonstrated significant shortcomings to hand-curating test cases in the manner you describe. Testing every 64bit float value is unrealistic, but testing a huge number of randomly selected values by cross-comparison with other libraries is a very good idea for code like this. https://github.com/google/oss-fuzz https://github.com/google/oss-fuzz
titzer 6y ago
That doesn't cover the entire space of possibilities, because the input can be an arbitrarily long decimal number. A correct implementation must (in the limit) expand the entire binary representation of that number and correctly round (using round-to-nearest, ties-to-even), even if the tie-breaking bit is a million places down.
- cozzyd 6y ago
  Is there a provable limit to the maximum depth of the tie-breaking bit? Otherwise sounds like a potential DOS vector?
  - titzer 6y ago
    It's only limited by the number of decimal digits (after the decimal point) input by the user; computing and storing that is linear in the input size. It's no more a DOS vector than just an enormous source file.

haberman 6y ago

Even if you could parse a double in a single cycle, it would take 292 years to run through 2^64 cases on a 2GHz machine. https://www.google.com/search?q=2**64+%2F+2GHz&oq=2**64+%2F+2GHz https://www.google.com/search?q=2**64+%2F+2GHz&oq=2**64+%2F+... Also, while there are only 2^64 distinct double values, there are many more string representations than that. For example, "1" and "1.0" are the same underlying value, but a parser needs to be able to handle both.

java-man 6y ago
My point is about comparing accelerated code behavior to the standard java Double.
- stefs 6y ago
  your point is still invalid because it's pointless to attempt what you're suggesting. and that's not how unit tests work. unit testing doesn't mean that all possible values have to be tested. usually it's about code paths, i.e. standard, error and edge cases.
  - java-man 6y ago
    My point is based on experience. Yes, it's probably too much to ask to test all 2^64 cases, but I've been dealing with code in production that was failing precisely because some values lead to code paths that gave incorrect results. In this particular case, I would have tested 2^N where N>32 random, unique values, at a minimum. Of course, it depends on who the customer is. Some customers can tolerate a few bugs here and there; and some would incur million dollar losses.
  - dodobirdlord 6y ago
    The successes of fuzzing projects like oss-fuzz have demonstrated significant shortcomings to hand-curating test cases in the manner you describe. Testing every 64bit float value is unrealistic, but testing a huge number of randomly selected values by cross-comparison with other libraries is a very good idea for code like this. https://github.com/google/oss-fuzz https://github.com/google/oss-fuzz

titzer 6y ago

That doesn't cover the entire space of possibilities, because the input can be an arbitrarily long decimal number. A correct implementation must (in the limit) expand the entire binary representation of that number and correctly round (using round-to-nearest, ties-to-even), even if the tie-breaking bit is a million places down.

cozzyd 6y ago
Is there a provable limit to the maximum depth of the tie-breaking bit? Otherwise sounds like a potential DOS vector?
- titzer 6y ago
  It's only limited by the number of decimal digits (after the decimal point) input by the user; computing and storing that is linear in the input size. It's no more a DOS vector than just an enormous source file.