[musl] DTOA: question about rendering / code pointer

[musl] DTOA: question about rendering / code pointer

[newbie nullzwei]

( apologize - re-tweet - 'plain text', hope that will work better | 
apologize - re-tweet - now 'subscribed' - got the impression my
mails didn't make it through to the list while not subscribed? ) 
 
hello @ all, 
 
gnumeric uses musl dtoa for rendering, and a self constructed 
'brute force' concept to find 'shortet round tripping' figures mostly 
similar to https://www.exploringbinary.com/the-shortest-decimal-string-that-round-trips-may-not-be-the-nearest/ 
 
we face the same issue as mentioned there, some powers of two 
miss to get the shortest 'round tripping' string, but have assigned 
another one digit longer string. Forcing to one digit less produces a 
string one decimal off in last position, and not tripping back to 
the original double. 
 
Example: 0x1p-44 ( 2^-44 ) is rendered to 

5.6843418860808015E-14 when allowed 17 digits, for 
16 digits it switches to 5.68434188608080**1**E-14, which is 
not too bad as the 'exact' decimal weight of the binary representative 
is ~5.684341886080801486969E-14, thus undershot to ~15, but! 
it points to a different double, and 5.68434188608080**2**E-14 
would be a better choice as it round trips to the originating double 
value. Affected ~46 integral powers of two in doubles, many more 
with long doubles.   
 
Is there any hope musl could change that? provide it as an option? 
Or can anyone give a code pointer or nearer explanation to enable 
us to patch it for our 'exotic' use? 
 
best regards, TIA for any help. 
 
b. 

Re: [musl] DTOA: question about rendering / code pointer

[Rich Felker]

On Tue, May 16, 2023 at 08:49:11PM +0200, newbie nullzwei wrote:
> ( apologize - re-tweet - 'plain text', hope that will work better | 
> apologize - re-tweet - now 'subscribed' - got the impression my
> mails didn't make it through to the list while not subscribed? ) 
>  
> hello @ all, 
>  
> gnumeric uses musl dtoa for rendering, and a self constructed 
> 'brute force' concept to find 'shortet round tripping' figures mostly 
> similar to https://www.exploringbinary.com/the-shortest-decimal-string-that-round-trips-may-not-be-the-nearest/ 
>  
> we face the same issue as mentioned there, some powers of two 
> miss to get the shortest 'round tripping' string, but have assigned 
> another one digit longer string. Forcing to one digit less produces a 
> string one decimal off in last position, and not tripping back to 
> the original double. 
>  
> Example: 0x1p-44 ( 2^-44 ) is rendered to 
> 
> 5.6843418860808015E-14 when allowed 17 digits, for 
> 16 digits it switches to 5.68434188608080**1**E-14, which is 
> not too bad as the 'exact' decimal weight of the binary representative 
> is ~5.684341886080801486969E-14, thus undershot to ~15, but! 
> it points to a different double, and 5.68434188608080**2**E-14 
> would be a better choice as it round trips to the originating double 
> value. Affected ~46 integral powers of two in doubles, many more 
> with long doubles.   
>  
> Is there any hope musl could change that? provide it as an option? 
> Or can anyone give a code pointer or nearer explanation to enable 
> us to patch it for our 'exotic' use? 

musl always, and very intentionally, performs correct rounding
according to the current rounding direction for all conversions
to/from decimal. Getting the shortest decimal string that round-trips
is a somewhat different problem, and not one libc has any API for. But
if what you want is shortest string which round-trips, I think there
are faster approaches than what musl does; ensuring exactness like we
do is more work.

Rich

Re: [musl] DTOA: question about rendering / code pointer

[alice]

On Tue May 16, 2023 at 9:36 PM CEST, Rich Felker wrote:
> On Tue, May 16, 2023 at 08:49:11PM +0200, newbie nullzwei wrote:
> > ( apologize - re-tweet - 'plain text', hope that will work better | 
> > apologize - re-tweet - now 'subscribed' - got the impression my
> > mails didn't make it through to the list while not subscribed? ) 
> >  
> > hello @ all, 
> >  
> > gnumeric uses musl dtoa for rendering, and a self constructed 
> > 'brute force' concept to find 'shortet round tripping' figures mostly 
> > similar to https://www.exploringbinary.com/the-shortest-decimal-string-that-round-trips-may-not-be-the-nearest/ 
> >  
> > we face the same issue as mentioned there, some powers of two 
> > miss to get the shortest 'round tripping' string, but have assigned 
> > another one digit longer string. Forcing to one digit less produces a 
> > string one decimal off in last position, and not tripping back to 
> > the original double. 
> >  
> > Example: 0x1p-44 ( 2^-44 ) is rendered to 
> > 
> > 5.6843418860808015E-14 when allowed 17 digits, for 
> > 16 digits it switches to 5.68434188608080**1**E-14, which is 
> > not too bad as the 'exact' decimal weight of the binary representative 
> > is ~5.684341886080801486969E-14, thus undershot to ~15, but! 
> > it points to a different double, and 5.68434188608080**2**E-14 
> > would be a better choice as it round trips to the originating double 
> > value. Affected ~46 integral powers of two in doubles, many more 
> > with long doubles.   
> >  
> > Is there any hope musl could change that? provide it as an option? 
> > Or can anyone give a code pointer or nearer explanation to enable 
> > us to patch it for our 'exotic' use? 
>
> musl always, and very intentionally, performs correct rounding
> according to the current rounding direction for all conversions
> to/from decimal. Getting the shortest decimal string that round-trips
> is a somewhat different problem, and not one libc has any API for. But
> if what you want is shortest string which round-trips, I think there
> are faster approaches than what musl does; ensuring exactness like we
> do is more work.

dragonbox/schubfach is probably exactly what you're looking for, for which
a (c++) reference implementation is at
https://github.com/jk-jeon/dragonbox

afaik libreoffice now uses this for the same usecase(?).

>
> Rich

Aw: Re: [musl] DTOA: question about rendering / code pointer

[newbie nullzwei]

@Rich: thank you for fast comment,

> musl always, and very intentionally, performs correct rounding
according to the current rounding direction for all conversions
to/from decimal.

yes, there is a tension if and where 'correctly rounded' is still or
no longer useful. From a decimal point of view, and thus that of
many users, it loses usefulness at the point where it prefers the
inaccuracy of the binary representation over the decimal 'equivalent'.

> Getting the shortest decimal string that round-trips
is a somewhat different problem, and not one libc has any API for.

Accordingly, it is a weakness for decimal <-> binary compatibility
if libraries, API's ... do not take 'SRT' into account. Similar to
the even IEEE rounding mode 'ties to evil' ( where 'ties away from
zero' is often mentioned but not implemented except in round()
- and there insufficient ). This is also a huge buzzkill to get
decimal acceptable results with binary placeholder math.

> But if what you want is shortest string which round-trips, I think
there are faster approaches than what musl does; ensuring exactness
like wedo is more work.

I have also considered and researched alternatives, but it would
be a bigger change, and brings new, e.g. licensing difficulties.
The current best SRT solutions are not simpler, see ryu, Schubfach,
SwiftDtoa ... they are really clobbering to be accurate and fast,
I was positively surprised that musl added with trial and error
afterburner can keep up well.
If there is a version of your code with more comments, or if you can
explain to me where the last digit is constructed / rounded and which
variables mean what there, I would like to try to patch it. ( I know,
professionals read such like a shopping list, I unfortunately do not ).

@alice: thank you for fast comment,

> dragonbox/schubfach is probably exactly what you're looking for,
for which a (c++) reference implementation is at
https://github.com/jk-jeon/dragonbox

thanks for the hint, had already looked there, C++ is not an option
for gnumeric, and I didn't get all alternatives to work and test,
- ryu I have mostly ready, is difficult / somewhat slow for long
doubles, I couldn't yet convince the maintainer,
- SwiftDtoa - popped very well working out of the box, but there are
questions that Swits Apache License isn't compatible with GNU GPL2
which gnumeric wants to keep.

> afaik libreoffice now uses this for the same usecase(?).

I am surprised and happy that LibreOffice uses reasonable solutions,
but I am afraid that all profit will be lost in their unrestrained
prettyfying.

Re: Re: [musl] DTOA: question about rendering / code pointer

[Rich Felker]

On Wed, May 17, 2023 at 09:41:03AM +0200, newbie nullzwei wrote:
> 
> @Rich: thank you for fast comment,
> 
> > musl always, and very intentionally, performs correct rounding
> according to the current rounding direction for all conversions
> to/from decimal.
> 
> yes, there is a tension if and where 'correctly rounded' is still or
> no longer useful. From a decimal point of view, and thus that of
> many users, it loses usefulness at the point where it prefers the
> inaccuracy of the binary representation over the decimal 'equivalent'.

There is no inaccuracy of the binary representation. It's an exact
number. The calculation that led to it might have been exact, but
floating point represents particular exact diadic rational numbers.
The musl list is not really the venue to argue over a philosophy that
they should be interpreted differently than how they're specified.

> I have also considered and researched alternatives, but it would
> be a bigger change, and brings new, e.g. licensing difficulties.
> The current best SRT solutions are not simpler, see ryu, Schubfach,
> SwiftDtoa ... they are really clobbering to be accurate and fast,
> I was positively surprised that musl added with trial and error
> afterburner can keep up well.
> If there is a version of your code with more comments, or if you can
> explain to me where the last digit is constructed / rounded and which
> variables mean what there, I would like to try to patch it. ( I know,
> professionals read such like a shopping list, I unfortunately do not ).

I don't have particular knowledge/experience with the algorithms to
get shortest-round-trip forms. The implementations we have for
conversion are largely straightforward decimal (base-1-billion) bignum
with only a scaling operation (by powers of two) implemented on each.
The decimal to binary direction in particular has comments explaining
the steps.

Identifying what changes you would have to make to code like this to
get the behavior you want seems like a nontrivial math problem. You're
welcome to pursue it for your purposes in reusing the code, but I
still think you'd be better off finding a suitably-licensed and
suitable-language implementation of a known-good algorithm for what
you want, or reading some of the literature to figure out how to write
your own.

Rich