www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Boost licensed implementation of Fabian Loitsch's Grisu-algorithm

reply Andre Pany <andre s-e-a-p.de> writes:
Hi,

This implementation of Fabian Loitsch's Grisu-algorithm is now 
boost licensed.

https://github.com/night-shift/fpconv

Can we add it to druntime/phobos for
Compile time float to string conversion?

Kind regards
Andre
Jan 04 2019
next sibling parent reply kdevel <kdevel vogtner.de> writes:
On Friday, 4 January 2019 at 17:41:19 UTC, Andre Pany wrote:

 This implementation of Fabian Loitsch's Grisu-algorithm


"[...] we propose a variant, Grisu3, that detects (and
aborts) when its output may not be the shortest. As a consequence
Grisu3 is incomplete and will fail for some percentage of its 
input.
Given 11 extra bits roughly 99.5% are processed correctly and
are thus guaranteed to be optimal (with respect to shortness and
rounding). The remaining 0.5% are rejected and need to be printed
by another printing algorithm (like Dragon4)." [1]

[...]


 Can we add it to druntime/phobos for
 Compile time float to string conversion?


What kind of source code could benefit from speeding up this 
conversion?

[1] Florian Loitsch: Printing Floating-Point Numbers Quickly and 
Accurately
     with Integers. In Proceedings of the 2010 ACM SIGPLAN
     Conference on Programming Language Design and Implementation, 
PLDI 2010
Jan 04 2019
next sibling parent Andre Pany <andre s-e-a-p.de> writes:
On Friday, 4 January 2019 at 19:38:36 UTC, kdevel wrote:

 On Friday, 4 January 2019 at 17:41:19 UTC, Andre Pany wrote:

 This implementation of Fabian Loitsch's Grisu-algorithm


 "[...] we propose a variant, Grisu3, that detects (and
 aborts) when its output may not be the shortest. As a 
 consequence
 Grisu3 is incomplete and will fail for some percentage of its 
 input.
 Given 11 extra bits roughly 99.5% are processed correctly and
 are thus guaranteed to be optimal (with respect to shortness and
 rounding). The remaining 0.5% are rejected and need to be 
 printed
 by another printing algorithm (like Dragon4)." [1]

 [...]


 Can we add it to druntime/phobos for
 Compile time float to string conversion?


 What kind of source code could benefit from speeding up this 
 conversion?

 [1] Florian Loitsch: Printing Floating-Point Numbers Quickly 
 and Accurately
     with Integers. In Proceedings of the 2010 ACM SIGPLAN
     Conference on Programming Language Design and 
 Implementation, PLDI 2010


My understanding is that std.conv: to isn't available at compile 
time because of the missing float to string implementation.

In another thread ketmar mentioned that with a D implementation 
the formatting will be consistent for all platforms.
https://forum.dlang.org/post/22429a6afdfd4633bf5723a12dd2917d chiroptera

Kind regards
Andre
Jan 04 2019
prev sibling parent Basile B. <b2.temp gmx.com> writes:
On Friday, 4 January 2019 at 19:38:36 UTC, kdevel wrote:

 On Friday, 4 January 2019 at 17:41:19 UTC, Andre Pany wrote:

 This implementation of Fabian Loitsch's Grisu-algorithm


 "[...] we propose a variant, Grisu3, that detects (and
 aborts) when its output may not be the shortest. As a 
 consequence
 Grisu3 is incomplete and will fail for some percentage of its 
 input.
 Given 11 extra bits roughly 99.5% are processed correctly and
 are thus guaranteed to be optimal (with respect to shortness and
 rounding). The remaining 0.5% are rejected and need to be 
 printed
 by another printing algorithm (like Dragon4)." [1]

 [...]


 Can we add it to druntime/phobos for
 Compile time float to string conversion?


 What kind of source code could benefit from speeding up this 
 conversion?


It's not only about speed. It's also about being consistent 
across platforms. Currently DMD for win32 uses an ancillary 
method that sometimes gives slightly different results than the 
other C libraries (see [1]). Then it's also about CTFE then only 
comes the speed criterion i think, as a bonus.

NB he admitted this himself [2].

[1]: 
https://github.com/DigitalMars/dmc/blob/9a774f3f2b3227fd416ec3a83cb9eb8f8751425f/src/core/strtold.c
[2]: https://issues.dlang.org/show_bug.cgi?id=5229#c6
Jan 05 2019
prev sibling next sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Friday, 4 January 2019 at 17:41:19 UTC, Andre Pany wrote:

 Hi,

 This implementation of Fabian Loitsch's Grisu-algorithm is now 
 boost licensed.

 https://github.com/night-shift/fpconv

 Can we add it to druntime/phobos for
 Compile time float to string conversion?

 Kind regards
 Andre


We could ... I ported it a few days ago :)

https://github.com/UplinkCoder/fpconv

But I'd like it to go into druntime rather than phobos.
Jan 04 2019
next sibling parent Andre Pany <andre s-e-a-p.de> writes:
On Friday, 4 January 2019 at 19:43:19 UTC, Stefan Koch wrote:

 On Friday, 4 January 2019 at 17:41:19 UTC, Andre Pany wrote:

 Hi,

 This implementation of Fabian Loitsch's Grisu-algorithm is now 
 boost licensed.

 https://github.com/night-shift/fpconv

 Can we add it to druntime/phobos for
 Compile time float to string conversion?

 Kind regards
 Andre


 We could ... I ported it a few days ago :)

 https://github.com/UplinkCoder/fpconv

 But I'd like it to go into druntime rather than phobos.


You did a great work. The missing piece was the MIT license. In 
the meantime the license was changed;)

Kind regards
Andre
Jan 04 2019
prev sibling parent reply Andre Pany <andre s-e-a-p.de> writes:
On Friday, 4 January 2019 at 19:43:19 UTC, Stefan Koch wrote:

 On Friday, 4 January 2019 at 17:41:19 UTC, Andre Pany wrote:

 Hi,

 This implementation of Fabian Loitsch's Grisu-algorithm is now 
 boost licensed.

 https://github.com/night-shift/fpconv

 Can we add it to druntime/phobos for
 Compile time float to string conversion?

 Kind regards
 Andre


 We could ... I ported it a few days ago :)

 https://github.com/UplinkCoder/fpconv

 But I'd like it to go into druntime rather than phobos.


Do you plan to create a pull request for druntime to add your 
port (independent from new ctfe engine)? If not, would you mind 
if I create an issue to get it merged?

Kind regards
Andre
Jan 06 2019
parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Sunday, 6 January 2019 at 09:41:30 UTC, Andre Pany wrote:

 On Friday, 4 January 2019 at 19:43:19 UTC, Stefan Koch wrote:

 On Friday, 4 January 2019 at 17:41:19 UTC, Andre Pany wrote:

 Hi,

 This implementation of Fabian Loitsch's Grisu-algorithm is 
 now boost licensed.

 https://github.com/night-shift/fpconv

 Can we add it to druntime/phobos for
 Compile time float to string conversion?

 Kind regards
 Andre


 We could ... I ported it a few days ago :)

 https://github.com/UplinkCoder/fpconv

 But I'd like it to go into druntime rather than phobos.


 Do you plan to create a pull request for druntime to add your 
 port (independent from new ctfe engine)? If not, would you mind 
 if I create an issue to get it merged?

 Kind regards
 Andre


I wanted to polish it a little before proposing the inclusion.

I'll send a PR shortly.

Regards,
Stefan
Jan 06 2019
parent Andre Pany <andre s-e-a-p.de> writes:
On Sunday, 6 January 2019 at 17:10:15 UTC, Stefan Koch wrote:

 On Sunday, 6 January 2019 at 09:41:30 UTC, Andre Pany wrote:

 On Friday, 4 January 2019 at 19:43:19 UTC, Stefan Koch wrote:


 I wanted to polish it a little before proposing the inclusion.

 I'll send a PR shortly.

 Regards,
 Stefan


Fantastic, thanks a lot!

Kind regards
Andre
Jan 06 2019
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/4/19 12:41 PM, Andre Pany wrote:

 Hi,
 
 This implementation of Fabian Loitsch's Grisu-algorithm is now boost 
 licensed.
 
 https://github.com/night-shift/fpconv
 
 Can we add it to druntime/phobos for
 Compile time float to string conversion?
 
 Kind regards
 Andre


That would be gladly considered!
Jan 04 2019
parent reply tipdbmp <email example.com> writes:
Have you considered Ulf Adams' Ryu float-to-string algorithm that 
uses only fixed-size integer operations?

https://dl.acm.org/citation.cfm?id=3192369
https://github.com/ulfjack/ryu
Jan 05 2019
parent Stefan Koch <uplink.coder googlemail.com> writes:
On Saturday, 5 January 2019 at 12:34:44 UTC, tipdbmp wrote:

 Have you considered Ulf Adams' Ryu float-to-string algorithm 
 that uses only fixed-size integer operations?

 https://dl.acm.org/citation.cfm?id=3192369
 https://github.com/ulfjack/ryu


So does grisu.

ryu is a minor improvement of grisu2.
Just the paper is much more confusing then the grisu2 one is.
Jan 05 2019