Jump to page: 1 2
Thread overview
Boost licensed implementation of Fabian Loitsch's Grisu-algorithm
Jan 04
kdevel
Jan 05
Basile B.
Jan 05
tipdbmp
January 04
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
January 04
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

January 04
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.
January 04
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

January 04
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
January 04
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!
January 05
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

January 05
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.
January 05
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



January 06
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
« First   ‹ Prev
1 2