{"action":"opened","issue":{"url":"https://api.github.com/repos/dotnet/corefx/issues/33053","repository_url":"https://api.github.com/repos/dotnet/corefx","labels_url":"https://api.github.com/repos/dotnet/corefx/issues/33053/labels{/name}","comments_url":"https://api.github.com/repos/dotnet/corefx/issues/33053/comments","events_url":"https://api.github.com/repos/dotnet/corefx/issues/33053/events","html_url":"https://github.com/dotnet/corefx/issues/33053","id":374123588,"node_id":"MDU6SXNzdWUzNzQxMjM1ODg=","number":33053,"title":"[Discussion] Fixing up the double parser to be IEEE compliant","user":{"login":"tannergooding","id":10487869,"node_id":"MDQ6VXNlcjEwNDg3ODY5","avatar_url":"https://avatars3.githubusercontent.com/u/10487869?v=4","gravatar_id":"","url":"https://api.github.com/users/tannergooding","html_url":"https://github.com/tannergooding","followers_url":"https://api.github.com/users/tannergooding/followers","following_url":"https://api.github.com/users/tannergooding/following{/other_user}","gists_url":"https://api.github.com/users/tannergooding/gists{/gist_id}","starred_url":"https://api.github.com/users/tannergooding/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tannergooding/subscriptions","organizations_url":"https://api.github.com/users/tannergooding/orgs","repos_url":"https://api.github.com/users/tannergooding/repos","events_url":"https://api.github.com/users/tannergooding/events{/privacy}","received_events_url":"https://api.github.com/users/tannergooding/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-10-25T20:40:56Z","updated_at":"2018-10-25T20:40:56Z","closed_at":null,"author_association":"MEMBER","body":"### Summary\r\n\r\nToday, the `System.Double` and `System.Single` parser will return incorrect values for various inputs. This is tracked by a number of issues, such as: https://github.com/dotnet/coreclr/issues/17467, https://github.com/dotnet/coreclr/issues/1316, and https://github.com/dotnet/coreclr/issues/19802.\r\n\r\nAfter have done some research, reviewing the IEEE spec, etc; I believe I know the path forward but it will be a bit more involved than initially expected. There are a lot of resources about IEEE compliance around the web, but one of the most cited and well-put together collections is the \"Exploring Binary\" blog. Another point of reference is the \"Correctly Rounded Binary-Decimal and Decimal-Binary Conversions\" paper by David M. Gay (which is generally considered to be the \"gold standard\" implementation).\r\n\r\n### Today's Implementation\r\n\r\nToday, we have almost all the relevant parsing/formatting code under `System.Number` in System.Private.Corelib (the class itself is split into multiple files). One of the `core` types is `NumberBuffer` which is shared between both the formatting and parsing code. However, this type will only consider at most 50 significant digits and for the IEEE double (binary64) type, you must consider at most 768 digits to correctly round. This many digits are needed because you must be able to process the largest \"exact\" string for the smallest representable denormal value plus a rounding digit (which will control whether you actually return the smallest representable denormal or the next value above it).\r\n\r\n### Proposal\r\n\r\nI propose we split `NumberBuffer` into two types. The first is an `IntegerBuffer`, which is identical to the current layout and can be used to process integer values, which always require less than 50 digits (even `Int128`, if we were to support it, only requires 39 digits). The other type would be a buffer which is used to support floating-point values, and would consist of most of the same fields, but would track the unbiased-exponent (rather than the scale) and would have a linked-list of 50 digit character buffers (due to the assumption that most input strings will be less than 50 digits long, and more than that is only needed for edge cases).\r\n* The MSVCRT implementation uses a \"fixed-sized\" buffer of 768 characters here, so I don't believe stack size will be a concern, and such space will only be used/needed to support the \"worst case scenario\".\r\n* An alternative to using linked lists would be to just fallback to `StringBuilder` for the edge cases, which would also allow us to support `Quad` eventually (which requires at most 11564 digits to be processed)\r\n\r\nWe can then look into updating the rest of the parsing code to be \"correct\" and performant. The code we have today is already correct and generally fast for a number of inputs, as it attempts to use a well-known shortcut and multiply the mantissa by the exponent to compute the correct result. However, this is only valid for a number of inputs (generally speaking those that compute a result containing less than 16 digits) and you must fallback to BigInteger arithmetic for the outliers (in the worst case we need 464 bytes in this BigInteger to process the smallest denormal double value).\r\n\r\n### Some Numbers\r\n\r\nTo compute the number of significant digits in the smallest representable denormal value you do:\r\n```\r\nx = d + floor(log10((2^m - 1) / 2^d)) + 2\r\nwhere d = absolute value of the minimum exponent + explicit mantissa bits\r\nwhere m = implicit mantissa bits\r\nwhere x = max significant digits required (includes rounding digit)\r\n```\r\n\r\nThen to compute the number of big integer bits needed to process the smallest representable denormal value you do:\r\n```\r\ny = d + floor(log2(10^x)) + 1 + 32\r\nwhere d = absolute value of the minimum exponent + explicit mantissa bits\r\nwhere x = max significant digits required\r\nwhere y = max bits needed in a big integer\r\n```\r\n\r\nType   | Implicit Mantissa Bits | Maximum Exponent | Maximum Digits\r\n------ | ---------------------- | ---------------- | --------------\r\nHalf   | 11                     | 15               | 22\r\nSingle | 24                     | 127              | 113\r\nDouble | 53                     | 1023             | 768\r\nQuad   | 113                    | 16383            | 11564\r\n\r\nThe explicit mantissa bits is `(implicit - 1)`\r\nThe minimum exponent is `(1 - max)`"}}
{"actor":{"display_login":"tannergooding"}}