<p>Given a new language, how best should we convert decimal to binary floating point? And please don't just say &quot;use strtod(3)&quot;: The venerable C function supports a baroque variety of weird formats I might prefer to reject. Of course one option is to transform an input string into something C can deal with, but shouldn't there be a more direct way?</p>
<p>Let me credit David Gay with <a href="https://www.netlib.org/fp/dtoa.c" rel="noreferrer">this monstrosity</a>. It supports everything newer than Univac but contains many thousands of lines of of static data tables, conditional compilation, and otherwise-peculiar C code.</p>
<p>The <a href="https://www.ampl.com/archive/first-website/REFS/rounding.pdf" rel="noreferrer">associated paper</a> begins by suggesting a straightforward procedure: Build an integer from up to the first 17 significant decimal digits, then multiply or divide by a suitable power of ten, which presumably the hardware can easily produce for you. And then the paper promptly gets much more difficult to understand, or to filter out the historical noise about hokey formats and ancient hardware.</p>
<p>Can anyone put a modern spin on this devilish detail of implementation? Is this really something no human should undertake? Or can this be done properly in drastically less code, assuming only a modern machine?</p>

<standard-library><floating-point>
Reading Floating Point, perhaps without libc/msvcrt
CC BY-SA 4.0
2023-11-22T05:12:06.930Z
It’s not obvious to me why `strtod` accepting formats you prefer to reject presents a problem; you’re only going to feed valid tokens of the language into it, which by definition are in formats you do want to accept.
Michael Homer
CC BY-SA 4.0
2023-11-22T06:32:32.903Z
@MichaelHomer I suppose if strtod accepts a superset of what you want, it's not too crazy. Say you allow underscores between groups of digits: Now you've some string munging to do. It's entirely feasible but also indirect. It would be quite straightforward to work out a mantissa and exponent in one pass through the string. The question becomes under what circumstances the obvious code breaks down, and how to detect / correct it without truckloads of static magic data.
Beth
CC BY-SA 4.0
2023-11-22T07:02:38.680Z
But that is the exact opposite of `strtod` accepting formats you prefer to reject, isn’t it? I don’t think that single-pass token construction is generally a concern for a typical language,  in any case, so it would probably be good to outline the circumstances that will make it a necessity for this one. The real-world answer is almost certainly “use `strtod`” (e.g. [Python here](https://github.com/python/cpython/blob/fde8fe50e495b66c397c6ce147ca3af2e7d9b289/Python/pystrtod.c#L126), which is still doing work around it), but there could still be situations where that’s available but unsuitable.
Michael Homer
CC BY-SA 4.0
2023-11-22T16:25:30.113Z
Do you also need to format floating points, or only to parse them? The former is extremely hairy -- at least if aiming for a round-trip.
Matthieu M.
CC BY-SA 4.0
2023-11-22T19:07:21.933Z
@MichaelHomer I read that code and I find it rather depressing. All those gymnastics to transform a Python number into a `strtod` number (including locale concerns) by which time you almost might as well just finish the job. This suggests that `strtod` is the wrong abstraction: too "stringly-typed" in a sense for how e.g. Python wishes to represent numbers.
Beth
CC BY-SA 4.0
2023-11-22T19:26:47.957Z
I don't know if this would actually work out, but I would probably consider the following approach, and then try to use some kind of fusion optimization to eliminate the intermediate data structure at compile-time: First, convert to an infinite-precision rational number (and put this into canonical form). This should be straightforward because we can just multiply each digit by its place value and add them up, without losing precision. Then, convert this to floating point by dividing the numerator by the denominator. The main question, I think, is: can the optimization actually work for this?
David Young
CC BY-SA 4.0
2023-11-22T19:57:12.110Z
One further consideration is compile-time and runtime compatibility — getting the same binary representation from the same string at these two different times.  Very easy to have subtle (e.g. 1-bit) differences via different algorithms.  This then goes to using the same mechanism at compile time as is used at runtime (and vice versa).
Erik Eidt
CC BY-SA 4.0
2023-11-23T09:24:27.673Z
@ErikEidt There is no ambiguity. Any given (finite) decimal has exactly one correctly-rounded binary-floating-point representation (for given precision). You can be off by one ulp and comply with the IEEE mandate from 1985 at least, but absolutely precise implementations do exist so there's no excuse to get it wrong.
Beth
CC BY-SA 4.0
2023-11-23T09:36:57.977Z
@DavidYoung that is essentially the technique. When numerator and denominator both have exact FP representations, then the problem is trivial. When you get outside that well-behaved range, current practice seems to be you start with the FP approximation and then correct for the error term using arbitrary-precision arithmetic.
Beth
CC BY-SA 4.0
2023-11-23T16:26:44.597Z
@Ian, Not sure the perceived ambiguity that isn't present.  Can you clarify?  Also, are you saying that any two algorithms, even home grown, will produce the same results, or that it doesn't matter if compile time and runtime work differently by 1-bit or so on the same string input ?
Erik Eidt
CC BY-SA 4.0
2023-11-25T04:41:09.607Z
@ErikEidt any two *correct* algorithms will agree on what to make of any given input. Apparently the 1985 version of the standard allowed *compliant* algorithms to disagree by one ULP, but the 2008 version says you can be wrong by at most 1/1000 ulp if I read this right.
Beth
<blockquote>
<p>Is this really something no human should undertake?</p>
</blockquote>
<p>Answering your question literally, it is something humans have undertaken and may well have to undertake again. But more importantly, should <em>you</em> do it? Or perhaps, <em>when</em> should you do it?</p>
<p>You've proposed wanting to reject formats that the existing implementation would accept. In practice this isn't an issue, because the rejection of tokens which are invalid according to your language's lexical syntax, is something that should happen before you call out to a third-party library to determine the meaning of those tokens. That is, your language's lexer should already be rejecting invalid number literals. Likewise, if you're parsing numbers dynamically at runtime (i.e. your standard library's parsing function, rather than your language's lexer), then you can check the string's format before calling out to the library. So this isn't a reason to avoid an existing implementation.</p>
<p>As you say, you may need to transform the string into a format accepted by the existing implementation, e.g. if your syntax allows underscores within number literals and the existing implementation doesn't accept them, then you'll need to strip them out first. But this is easy to do*, and not a reason to avoid the existing implementation.</p>
<p>One reason I can think of to implement your own conversion from decimal strings to binary fractional numbers, is if you need to support a different binary representation than standard floating-point. For example, your language might have a built-in arbitrary-precision number type, and allow literals of that type, in which case parsing as a fixed-width floating-point type isn't going to cut it. However, even in this case it would still make more sense to use an existing library, if there is an acceptable one for your host language.</p>
<p>On the other hand, there are two very good reasons to avoid &quot;rolling your own&quot; solution when an existing, tried and tested solution is available:</p>
<ul>
<li>Your code could have a bug which gives incorrect parses in a rare case, and this would be hard to spot particularly if the error in the resulting value is small.</li>
<li>Your code could have a bug causing an infinite loop in a rare case, like <a href="https://bugs.php.net/bug.php?id=53632" rel="nofollow noreferrer">this one in PHP</a>. Because the same parsing function was being used at runtime, the fallout of that bug was that almost any web application written in PHP was vulnerable to a denial of service attack, simply by the user entering the string <code>2.2250738585072011e-308</code> anywhere a number was expected.</li>
</ul>
<p>Given the stakes of getting this wrong, then, you should only attempt this both when no existing battle-tested implementation could meet your needs, and also when you have the capability to verify the correctness of your implementation to a very high degree of confidence (e.g. formal verification or fuzz-testing).</p>
<hr />
<p><sup>*In the comments it's been noted that this is not, in fact, easy for Python (<a href="https://github.com/python/cpython/blob/fde8fe50e495b66c397c6ce147ca3af2e7d9b289/Python/pystrtod.c#L126" rel="nofollow noreferrer">source link</a>), since a transformation is required to convert a string into the locale expected by <code>strtod</code>. But the same logic applies: prefer a tried-and-tested existing library that already does this (or doesn't need to), and only write your own as a last resort.</sup></p>

CC BY-SA 4.0
2023-11-22T19:01:04.087Z
2023-11-23T17:54:42.810Z
2023-11-23T17:54:42.810Z
kaya3
CC BY-SA 4.0
2023-11-23T05:20:17.423Z
It’s not *Python* that handles locales there, it’s *`strtod`* that inherently uses the locale radix separator under POSIX (controlled by LC_NUMERIC), so Python has to replace source-text `.` with the locale-specific separator before passing the string in. Something like this would be required for any `strtod`-based implementation. (e.g. try `tcc -run - <<<$'#include <stdio.h>\n#include <locale.h>\n#include <stdlib.h>\nint main() { setlocale(LC_ALL, "en_DK.utf8");\nprintf("%f\\n", strtod("1234.5", NULL));}'` and see the wrong output).
Michael Homer
CC BY-SA 4.0
2023-11-23T17:52:55.627Z
@MichaelHomer Ah! I'll edit to fix. Surely there is a pre-existing float parser that doesn't depend on global state, though?
kaya3
<p>It depends whether you consider programming to be a kind of engineering or a kind of politics.</p>
<ol>
<li><p>If you rely on <code>strtod</code> or anything else that someone else has written, then for any bug that appears in it, on any platform far into the future, all you can tell your users is “yes it’s a bug but it is not my fault”. To a potential customer that is unacceptable.</p>
</li>
<li><p>You will have to accept all the decisions made by people you don’t know and have no control or influence over, some of which are unknowable until you discover them. For instance if they decide that numeric conversions ought to depend on (a) where the user is or (b) where the user says he is or (c) where the creators of <code>strtod</code> say the user ought to be - the decimal-point-or-comma is an example – then you and your customers are hostages to politics and their software will work or not work for political reasons. After all, the Unicode character set already has some characters that are not permitted to be displayed in China. Who knows if some country, some day, won’t decide that certain numbers carry a hidden message and are unacceptable?</p>
</li>
</ol>
<p>The only responsible way out is to adopt the policy “all the bugs are my own” and keep to it from the very beginning.</p>
<p>Either write your own conversion routine (which you can test to death against a standard implementation) or take the source code of something like <code>strtod</code> and make it your own. So it won’t change from platform to platform, decade to decade, unless you want it to; and if anything goes wrong with it, you can correct it.</p>

CC BY-SA 4.0
2023-11-24T08:17:07.560Z
2023-11-24T08:17:07.560Z
Martin Kochanski
<p>This is going to be a single-reference answer, but this classic paper is a &quot;must read&quot; for anyone writing a standard library:</p>
<p>William D. Clinger, <em><a href="https://dl.acm.org/doi/abs/10.1145/93548.93557" rel="nofollow noreferrer">How to read floating point numbers accurately</a></em>, ACM SIGPLAN Notices 25:6, Jun 1990, pp 92–101.</p>
<p>There is some <a href="https://onlinelibrary.wiley.com/doi/10.1002/spe.2984" rel="nofollow noreferrer">more</a> <a href="https://onlinelibrary.wiley.com/doi/10.1002/spe.3198" rel="nofollow noreferrer">recent</a> work by Daniel Lemire <em>et al</em> that is worth checking out for a more modern approach, but the first one is still worth it.</p>

CC BY-SA 4.0
2023-11-25T10:34:38.510Z
2023-11-25T10:34:38.510Z
Pseudonym
CC BY-SA 4.0
2023-11-26T01:51:54.957Z
Accepting because it *actually answers the question* even though it may not be the *wisest* plan for most people.
Beth
CC BY-SA 4.0
2023-11-28T22:29:47.897Z
"Most people" perhaps, but part of the reason we write this stuff down is so that institutional knowledge isn't lost. It would warm my heart if someone in this community takes it upon themselves to implement a high quality floating point reader from scratch, if only as a learning exercise.
Pseudonym
# Reading Floating Point, perhaps without libc/msvcrt
Posted by: username_0 on 2023-11-22
Given a new language, how best should we convert decimal to binary floating point? And please don't just say "use strtod(3)": The venerable C function supports a baroque variety of weird formats I might prefer to reject. Of course one option is to transform an input string into something C can deal with, but shouldn't there be a more direct way?

Let me credit David Gay with [this monstrosity](https://www.netlib.org/fp/dtoa.c). It supports everything newer than Univac but contains many thousands of lines of of static data tables, conditional compilation, and otherwise-peculiar C code.

The [associated paper](https://www.ampl.com/archive/first-website/REFS/rounding.pdf) begins by suggesting a straightforward procedure: Build an integer from up to the first 17 significant decimal digits, then multiply or divide by a suitable power of ten, which presumably the hardware can easily produce for you. And then the paper promptly gets much more difficult to understand, or to filter out the historical noise about hokey formats and ancient hardware.

Can anyone put a modern spin on this devilish detail of implementation? Is this really something no human should undertake? Or can this be done properly in drastically less code, assuming only a modern machine?
**Tags:** standard-library floating-point
> **Comments:**
> **username_1**: It’s not obvious to me why `strtod` accepting formats you prefer to reject presents a problem; you’re only going to feed valid tokens of the language into it, which by definition are in formats you do want to accept.  
> **username_0**: @MichaelHomer I suppose if strtod accepts a superset of what you want, it's not too crazy. Say you allow underscores between groups of digits: Now you've some string munging to do. It's entirely feasible but also indirect. It would be quite straightforward to work out a mantissa and exponent in one pass through the string. The question becomes under what circumstances the obvious code breaks down, and how to detect / correct it without truckloads of static magic data.  
> **username_1**: But that is the exact opposite of `strtod` accepting formats you prefer to reject, isn’t it? I don’t think that single-pass token construction is generally a concern for a typical language,  in any case, so it would probably be good to outline the circumstances that will make it a necessity for this one. The real-world answer is almost certainly “use `strtod`” (e.g. [Python here](https://github.com/python/cpython/blob/fde8fe50e495b66c397c6ce147ca3af2e7d9b289/Python/pystrtod.c#L126), which is still doing work around it), but there could still be situations where that’s available but unsuitable.  
> **username_2**: Do you also need to format floating points, or only to parse them? The former is extremely hairy -- at least if aiming for a round-trip.  
> **username_0**: @MichaelHomer I read that code and I find it rather depressing. All those gymnastics to transform a Python number into a `strtod` number (including locale concerns) by which time you almost might as well just finish the job. This suggests that `strtod` is the wrong abstraction: too "stringly-typed" in a sense for how e.g. Python wishes to represent numbers.  
> **username_3**: I don't know if this would actually work out, but I would probably consider the following approach, and then try to use some kind of fusion optimization to eliminate the intermediate data structure at compile-time: First, convert to an infinite-precision rational number (and put this into canonical form). This should be straightforward because we can just multiply each digit by its place value and add them up, without losing precision. Then, convert this to floating point by dividing the numerator by the denominator. The main question, I think, is: can the optimization actually work for this?  
> **username_4**: One further consideration is compile-time and runtime compatibility — getting the same binary representation from the same string at these two different times.  Very easy to have subtle (e.g. 1-bit) differences via different algorithms.  This then goes to using the same mechanism at compile time as is used at runtime (and vice versa).  
> **username_0**: @ErikEidt There is no ambiguity. Any given (finite) decimal has exactly one correctly-rounded binary-floating-point representation (for given precision). You can be off by one ulp and comply with the IEEE mandate from 1985 at least, but absolutely precise implementations do exist so there's no excuse to get it wrong.  
> **username_0**: @DavidYoung that is essentially the technique. When numerator and denominator both have exact FP representations, then the problem is trivial. When you get outside that well-behaved range, current practice seems to be you start with the FP approximation and then correct for the error term using arbitrary-precision arithmetic.  
> **username_4**: @Ian, Not sure the perceived ambiguity that isn't present.  Can you clarify?  Also, are you saying that any two algorithms, even home grown, will produce the same results, or that it doesn't matter if compile time and runtime work differently by 1-bit or so on the same string input ?  
> **username_0**: @ErikEidt any two *correct* algorithms will agree on what to make of any given input. Apparently the 1985 version of the standard allowed *compliant* algorithms to disagree by one ULP, but the 2008 version says you can be wrong by at most 1/1000 ulp if I read this right.  
---
## 3 answers
### Answer by username_7 on 2023-11-25. Score: 4 | Accepted answer
This is going to be a single-reference answer, but this classic paper is a "must read" for anyone writing a standard library:

William D. Clinger, *[How to read floating point numbers accurately](https://dl.acm.org/doi/abs/10.1145/93548.93557)*, ACM SIGPLAN Notices 25:6, Jun 1990, pp 92–101.

There is some [more](https://onlinelibrary.wiley.com/doi/10.1002/spe.2984) [recent](https://onlinelibrary.wiley.com/doi/10.1002/spe.3198) work by Daniel Lemire *et al* that is worth checking out for a more modern approach, but the first one is still worth it.
> **Comments:**
> **username_0** (2023-11-26): Accepting because it *actually answers the question* even though it may not be the *wisest* plan for most people.  
> **username_7** (2023-11-28): "Most people" perhaps, but part of the reason we write this stuff down is so that institutional knowledge isn't lost. It would warm my heart if someone in this community takes it upon themselves to implement a high quality floating point reader from scratch, if only as a learning exercise.  
---
### Answer by username_5 on 2023-11-22. Score: 5
> Is this really something no human should undertake?

Answering your question literally, it is something humans have undertaken and may well have to undertake again. But more importantly, should *you* do it? Or perhaps, *when* should you do it?

You've proposed wanting to reject formats that the existing implementation would accept. In practice this isn't an issue, because the rejection of tokens which are invalid according to your language's lexical syntax, is something that should happen before you call out to a third-party library to determine the meaning of those tokens. That is, your language's lexer should already be rejecting invalid number literals. Likewise, if you're parsing numbers dynamically at runtime (i.e. your standard library's parsing function, rather than your language's lexer), then you can check the string's format before calling out to the library. So this isn't a reason to avoid an existing implementation.

As you say, you may need to transform the string into a format accepted by the existing implementation, e.g. if your syntax allows underscores within number literals and the existing implementation doesn't accept them, then you'll need to strip them out first. But this is easy to do\*, and not a reason to avoid the existing implementation.

One reason I can think of to implement your own conversion from decimal strings to binary fractional numbers, is if you need to support a different binary representation than standard floating-point. For example, your language might have a built-in arbitrary-precision number type, and allow literals of that type, in which case parsing as a fixed-width floating-point type isn't going to cut it. However, even in this case it would still make more sense to use an existing library, if there is an acceptable one for your host language.

On the other hand, there are two very good reasons to avoid "rolling your own" solution when an existing, tried and tested solution is available:

* Your code could have a bug which gives incorrect parses in a rare case, and this would be hard to spot particularly if the error in the resulting value is small.
* Your code could have a bug causing an infinite loop in a rare case, like [this one in PHP](https://bugs.php.net/bug.php?id=53632). Because the same parsing function was being used at runtime, the fallout of that bug was that almost any web application written in PHP was vulnerable to a denial of service attack, simply by the user entering the string `2.2250738585072011e-308` anywhere a number was expected.

Given the stakes of getting this wrong, then, you should only attempt this both when no existing battle-tested implementation could meet your needs, and also when you have the capability to verify the correctness of your implementation to a very high degree of confidence (e.g. formal verification or fuzz-testing).

---

\*In the comments it's been noted that this is not, in fact, easy for Python ([source link](https://github.com/python/cpython/blob/fde8fe50e495b66c397c6ce147ca3af2e7d9b289/Python/pystrtod.c#L126)), since a transformation is required to convert a string into the locale expected by `strtod`. But the same logic applies: prefer a tried-and-tested existing library that already does this (or doesn't need to), and only write your own as a last resort.
> **Comments:**
> **username_1** (2023-11-23): It’s not *Python* that handles locales there, it’s *`strtod`* that inherently uses the locale radix separator under POSIX (controlled by LC_NUMERIC), so Python has to replace source-text `.` with the locale-specific separator before passing the string in. Something like this would be required for any `strtod`-based implementation. (e.g. try `tcc -run - <<<$'#include <stdio.h>\n#include <locale.h>\n#include <stdlib.h>\nint main() { setlocale(LC_ALL, "en_DK.utf8");\nprintf("%f\\n", strtod("1234.5", NULL));}'` and see the wrong output).  
> **username_5** (2023-11-23): @MichaelHomer Ah! I'll edit to fix. Surely there is a pre-existing float parser that doesn't depend on global state, though?  
---
### Answer by username_6 on 2023-11-24. Score: -2
It depends whether you consider programming to be a kind of engineering or a kind of politics.

1. If you rely on `strtod` or anything else that someone else has written, then for any bug that appears in it, on any platform far into the future, all you can tell your users is “yes it’s a bug but it is not my fault”. To a potential customer that is unacceptable.
2. You will have to accept all the decisions made by people you don’t know and have no control or influence over, some of which are unknowable until you discover them. For instance if they decide that numeric conversions ought to depend on (a) where the user is or (b) where the user says he is or (c) where the creators of `strtod` say the user ought to be - the decimal-point-or-comma is an example – then you and your customers are hostages to politics and their software will work or not work for political reasons. After all, the Unicode character set already has some characters that are not permitted to be displayed in China. Who knows if some country, some day, won’t decide that certain numbers carry a hidden message and are unacceptable?

The only responsible way out is to adopt the policy “all the bugs are my own” and keep to it from the very beginning.

Either write your own conversion routine (which you can test to death against a standard implementation) or take the source code of something like `strtod` and make it your own. So it won’t change from platform to platform, decade to decade, unless you want it to; and if anything goes wrong with it, you can correct it.
---
