Search
Page
Decimal string to floating point conversion with correct half-to-even rounding
Jun 21, 2020
9il
Jun 22, 2020
Dukc
Jun 22, 2020
9il
Jun 22, 2020
9il
Jun 22, 2020
Dukc
Jul 04, 2020
Walter Bright
Jul 05, 2020
9il
Jul 05, 2020
Walter Bright
Jul 05, 2020
9il
Jul 05, 2020
Walter Bright
Jul 05, 2020
9il
Jul 05, 2020
9il
Jul 05, 2020
Walter Bright
Jul 05, 2020
Walter Bright
Jul 05, 2020
9il
Jul 05, 2020
IGotD-
Jul 06, 2020
Jacob Carlborg
Jul 07, 2020
Walter Bright
Jul 07, 2020
Guillaume Piolat
Jul 07, 2020
9il
Jul 07, 2020
Guillaume Piolat
Jul 07, 2020
jmh530
Jul 07, 2020
jmh530
Jul 07, 2020
9il
Jul 07, 2020
9il
Jul 08, 2020
Walter Bright
Jul 07, 2020
9il
Jul 07, 2020
9il
Aug 08, 2020
Avrina
Aug 08, 2020
Bruce Carneal
Aug 09, 2020
Bruce Carneal
Jul 07, 2020
Jul 07, 2020
Jul 07, 2020
John Colvin
Jul 07, 2020
H. S. Teoh
Jul 07, 2020
H. S. Teoh
Jul 07, 2020
9il
Jul 07, 2020
Jul 11, 2020
Dibyendu Majumdar
Jul 07, 2020
kinke
Jul 07, 2020
9il
Jul 07, 2020
kinke
Jul 08, 2020
9il
Jul 11, 2020
Walter Bright
```Hey everyone,

So excited to finally announce we can correctly parse floating-point numbers according to IEEE round half-to-even (bankers) rule like in C/C++, Rust, and others.

@nogc, optionally nothrow API is provided as part of Mir Algorithm v3.9.0 [0].
The documentation is available [1].

In case you are surprised, you can be sure that neither D compilers can correctly parse decimal FP literals [2, 3, 4], nor Phobos can correctly parse decimal FP strings [6].

Mir decimal parsing supports up-to quadruple precision.

The conversion error is 0 ULP for normal numbers.

Subnormal numbers with a decimal exponent greater than or equal to -512 have upper error bound equal to 1 ULP. Zero error bound for subnormal numbers can be supported in the future when Mir Ion, the ASDF successor, is ready.

The implementation is based on the paper [7].

The error bounds above are valid for LDC. DMD may have slightly larger errors because of the wrong code generation for ulong to double conversion [5].

This work has been sponsored by Symmetry Investments and Kaleidic Associates.

Best regards,
Ilya

[0] https://github.com/libmir/mir-algorithm
[1] http://mir-algorithm.libmir.org/mir_parse.html#.fromString[2] https://issues.dlang.org/show_bug.cgi?id=20951
[3] https://issues.dlang.org/show_bug.cgi?id=20952
[4] https://issues.dlang.org/show_bug.cgi?id=20953
[5] https://issues.dlang.org/show_bug.cgi?id=20963
[6] https://issues.dlang.org/show_bug.cgi?id=20967
```
```On Sunday, 21 June 2020 at 15:24:14 UTC, 9il wrote:
> Hey everyone,
>
> So excited to finally announce we can correctly parse floating-point numbers according to IEEE round half-to-even (bankers) rule like in C/C++, Rust, and others.

Finally a worthy alternative to Vladimir Panteleevs parser [1]. A few months back I went looking for a `nothrow` parser that can handle errors reliably, and I was surprised that I could find only one that was better than my simple custom-made one.

Can mir_parse handle other bases than decimal?

```
```On Monday, 22 June 2020 at 10:53:02 UTC, Dukc wrote:
> On Sunday, 21 June 2020 at 15:24:14 UTC, 9il wrote:
> Can mir_parse handle other bases than decimal?

No, only the decimal basis is supported for now. Support for hexadecimal FP/integer parsing can be added though.

The basic stuff for correct FP hexadecimal parsing is done: we can convert a big integer view to FP number with half-to-even rounding.

So the algorithm would look like:
2. Parse exponent
3. Cast big integer to `Fp` with a specific number of meaningful bits (its already implemented)
4. Add exponent to `Fp`'s exponent, and cast the result to a hardware floating point type.

```
```On Monday, 22 June 2020 at 12:04:13 UTC, 9il wrote:
> On Monday, 22 June 2020 at 10:53:02 UTC, Dukc wrote:
>> On Sunday, 21 June 2020 at 15:24:14 UTC, 9il wrote:
>> Can mir_parse handle other bases than decimal?
>
> No, only the decimal basis is supported for now. Support for hexadecimal FP/integer parsing can be added though.
>
> The basic stuff for correct FP hexadecimal parsing is done: we can convert a big integer view to FP number with half-to-even rounding.
>
> So the algorithm would look like:
> 1. Parse hexadecimal big integer
> 2. Parse exponent
> 3. Cast big integer to `Fp` with a specific number of meaningful bits (its already implemented)
> 4. Add exponent to `Fp`'s exponent, and cast the result to a hardware floating point type.

http://mir-algorithm.libmir.org/mir_bignum_low_level_view.html#.BigUIntView.fromHexStringImpl

So, each part of the algorithm above is implemented. Maybe we need to rework fromHexStringImpl to make it return a boolean value.
```
```On Monday, 22 June 2020 at 12:07:26 UTC, 9il wrote:
> On Monday, 22 June 2020 at 12:04:13 UTC, 9il wrote:
>> So the algorithm would look like:
>> 1. Parse hexadecimal big integer
>> 2. Parse exponent
>> 3. Cast big integer to `Fp` with a specific number of meaningful bits (its already implemented)
>> 4. Add exponent to `Fp`'s exponent, and cast the result to a hardware floating point type.
>
>
> http://mir-algorithm.libmir.org/mir_bignum_low_level_view.html#.BigUIntView.fromHexStringImpl
>

So only a bit left to go. Great!

> So, each part of the algorithm above is implemented. Maybe we need to rework fromHexStringImpl to make it return a boolean value.

Good idea. It should pay back when one wants to parse a big amount of strings that are likely to contain a lot of non-integers.
```
```On 6/21/2020 8:24 AM, 9il wrote:
> So excited to finally announce we can correctly parse floating-point numbers according to IEEE round half-to-even (bankers) rule like in C/C++, Rust, and others.

Great work! Would you like to add it to dmd?
```
```On Saturday, 4 July 2020 at 20:35:48 UTC, Walter Bright wrote:
> On 6/21/2020 8:24 AM, 9il wrote:
>> So excited to finally announce we can correctly parse floating-point numbers according to IEEE round half-to-even (bankers) rule like in C/C++, Rust, and others.
>
> Great work! Would you like to add it to dmd?

Thank you! Yes.

It would be very much appreciated to preserve the `mir.` namespace for the `parse` module, the required `bignum` package*. Also, whenever the code will be located I would like to have control over it. Will you agree?

* - `mir.bignum` is 6K LOC and it is expected to grow up to 20K LOC if finished. The package includes abstract views for big integers, decimal, and binary FP numbers; stack-allocated big integers; midsize unsigned integers; software FP numbers with extended precision.

```
```On 7/4/2020 8:09 PM, 9il wrote:
> On Saturday, 4 July 2020 at 20:35:48 UTC, Walter Bright wrote:
>> On 6/21/2020 8:24 AM, 9il wrote:
>>> So excited to finally announce we can correctly parse floating-point numbers according to IEEE round half-to-even (bankers) rule like in C/C++, Rust, and others.
>>
>> Great work! Would you like to add it to dmd?
>
> Thank you! Yes.
>
> It would be very much appreciated to preserve the `mir.` namespace for the `parse` module, the required `bignum` package*. Also, whenever the code will be located I would like to have control over it. Will you agree?
>
> * - `mir.bignum` is 6K LOC and it is expected to grow up to 20K LOC if finished. The package includes abstract views for big integers, decimal, and binary FP numbers; stack-allocated big integers; midsize unsigned integers; software FP numbers with extended precision.
>

Does the float parsing code require bignum?

I'm also not sure I know what you mean by control. Contributions to dmd would need to be Boost Licensed, which means anyone can do what they like with them.
```
```On Sunday, 5 July 2020 at 06:23:35 UTC, Walter Bright wrote:
> On 7/4/2020 8:09 PM, 9il wrote:
>> On Saturday, 4 July 2020 at 20:35:48 UTC, Walter Bright wrote:
>>> On 6/21/2020 8:24 AM, 9il wrote:
>>>> So excited to finally announce we can correctly parse floating-point numbers according to IEEE round half-to-even (bankers) rule like in C/C++, Rust, and others.
>>>
>>> Great work! Would you like to add it to dmd?
>>
>> Thank you! Yes.
>>
>> It would be very much appreciated to preserve the `mir.` namespace for the `parse` module, the required `bignum` package*. Also, whenever the code will be located I would like to have control over it. Will you agree?
>>
>> * - `mir.bignum` is 6K LOC and it is expected to grow up to 20K LOC if finished. The package includes abstract views for big integers, decimal, and binary FP numbers; stack-allocated big integers; midsize unsigned integers; software FP numbers with extended precision.
>>
>
> Does the float parsing code require bignum?

Yes. The decimal float parsing requires big integer arithmetic and software floating-point multiplication with extended precision (128-bit mantissa).

> I'm also not sure I know what you mean by control. Contributions to dmd would need to be Boost Licensed, which means anyone can do what they like with them.

We need not only literals parsing but also library text parsing. So the code should be available for users and for the compiler. I see two possible solutions that look good to me.

The first one is to add mir-algorithm package or its part as an external dependency for DMD. It is preferable and either way. If you will accept the PR, I will do it.

The second solution is to move `mir.bignum` and `mir.parse` to DRuntime/Phobos. In this case, I would like to preserve the `mir.` namespace and the same authority and veto right for this part of the codebase as I have at Mir Org.

I mean the following. Your voice has a veto right for DMD and Dlang evaluation. Andrei has a veto right for Phobos. Atila seems to have almost the same veto right as Andrei and you and blocks required Dlang features for Mir [1, 2]. Furthermore, if you and Andrei really want to add or change something you will force it to happen. I want the same veto right for evaluation of the Mir parts in case you think they should be moved to DRuntime/Phobos. Also, the code under `mir.` namespace should be less constrained then `core`/`std` code in terms of API changes.

[1] https://github.com/dlang/dmd/pull/9778
[2] https://github.com/dlang/DIPs/blob/master/DIPs/other/DIP1023.md
```
```On 7/5/2020 12:24 AM, 9il wrote:
> On Sunday, 5 July 2020 at 06:23:35 UTC, Walter Bright wrote:
>> On 7/4/2020 8:09 PM, 9il wrote:
>> Does the float parsing code require bignum?
> Yes. The decimal float parsing requires big integer arithmetic and software

Arbitrary precision or simply a fixed amount of more precision?

> floating-point multiplication with extended precision (128-bit mantissa).

Some of that is already done in dmd.

Essentially, just enough to get this specific use to work.

>> I'm also not sure I know what you mean by control. Contributions to dmd would need to be Boost Licensed, which means anyone can do what they like with them.
>
>
> We need not only literals parsing but also library text parsing. So the code should be available for users and for the compiler. I see two possible solutions that look good to me.
>
> The first one is to add mir-algorithm package or its part as an external dependency for DMD. It is preferable and either way. If you will accept the PR, I will do it.
>
> The second solution is to move `mir.bignum` and `mir.parse` to DRuntime/Phobos. In this case, I would like to preserve the `mir.` namespace and the same authority and veto right for this part of the codebase as I have at Mir Org.
>
> I mean the following. Your voice has a veto right for DMD and Dlang evaluation. Andrei has a veto right for Phobos. Atila seems to have almost the same veto right as Andrei and you and blocks required Dlang features for Mir [1, 2]. Furthermore, if you and Andrei really want to add or change something you will force it to happen. I want the same veto right for evaluation of the Mir parts in case you think they should be moved to DRuntime/Phobos. Also, the code under `mir.` namespace should be less constrained then `core`/`std` code in terms of API changes.
>
>
> [1] https://github.com/dlang/dmd/pull/9778
> [2] https://github.com/dlang/DIPs/blob/master/DIPs/other/DIP1023.md

It doesn't work quite like that. The D Language Foundation controls it. Andrei, Atila, and myself control it only as far as we DLF empowers us to, which can change. Official parts of the DMD distribution have to be controlled by the DLF. It's unworkable otherwise.

```
« First   ‹ Prev