Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #141469

Re: A final word on casting.

Show all headers | View raw

On Tuesday, February 26, 2019 at 8:42:12 AM UTC-5, James Kuyper wrote:
> On Tuesday, February 26, 2019 at 2:26:25 AM UTC-5, Tim Rentsch wrote:
> > James Kuyper <jameskuyper@alumni.caltech.edu> writes:
> > 
> > > On 1/3/19 22:27, Richard Damon wrote:
> ...
> > >> The 1000 bit value was someones calculation of the number of bits you
> > >> needed to be computing in to get absolute exact rounding of a floating
> > >> point number to double precision, i.e. the difference between the
> > >> rounded representation and the exact value represented by the string is
> > >> less than 0.50000000000000... ULP.
> > >>
> > >> I haven't looked up the math to compute that, and while at first thought
> > >> it seems high, I am not so sure as to say it must be too high.  'Random'
> > >> numbers may not get you anywhere close to the needed value, as you are
> > >> looking for the pathalogical case which gets you to looking for a
> > >> difference between something like .4999999999999999 and .50000000000
> > >> where that small difference affects the final rounding.
> > >
> > > The most difficult case to handle is a decimal string representing a
> > > value that is almost exactly halfway between two representable values,
> > > when the current rounding mode is "round to nearest".  Such a string must
> > > be processed until you can determine whether it's above, below, or equal
> > > to that half-way value.
> > >
> > > On my system, the smallest representable value greater than 1.0 is 1.0 +
> > > 2^-52, which can be represented exactly in decimal as
> > > 1.0000000000000002220446049250313080847263336181640625
> > > The halfway point between that and 1.0 is therefore
> > > 1.00000000000000011102230246251565404236316680908203125
> > >
> > > If you process a digit string that starts with
> > > "1.00000000000000011102230246251565404236316680908203124", there's no
> > > need to process any further, it's guaranteed that the closest
> > > representable value is 1.0.
> > > If you process a digit string that starts with
> > > "1.00000000000000011102230246251565404236316680908203125", as soon as
> > > you've processed that part of the string, you only need to check whether
> > > any of the subsequent digits is non-zero.  If so, it rounds up to
> > > 1.0000000000000002220446049250313080847263336181640625
> > > otherwise, it rounds however you handle the halfway value.  If
> > > __STDC_IEC_559__ is pre#defined by the implementaiton, than the rules of
> > > IEC/ISO 60559 (== IEEE 754) apply, which require that the half-way point
> > > be rounded to set the last bit to 0, which would correspond to 1.0 in
> > > this case.
> > >
> > > Either way, there's never any need to store any data after processing
> > > the first 54 significant digits.  Handling the first 54 digits might
> > > require storing a lot more than 80 bits (I'm not sure whether there's a
> > > shortcut that would allow it to be done using only a little more than 52
> > > bits), but it requires a lot less than 1000+ bits.
> > >
> > > I can't imagine what the argument might be that calls for 1000+ bits -
> > > [...]
> > 
> > On my system, the smallest representable value greater than
> > 4503599627370496.0 is 4503599627370496.0 + 1.0, which can be
> > represented exactly in decimal as 4503599627370497.0.  The halfway
> > point between that and 4503599627370496.0 is therefore
> > 4503599627370496.5.
> > 
> > If you process a digit string that starts with "4503599627370496.4",
> > there's no need to process any further;  it's guaranteed that the
> > closest representable value is 4503599627370496.0.  If you process a
> > digit string that starts with "4503599627370496.5", as soon as
> > you've processed that part of the string, you only need to check
> > whether any of the subsequent digits is non-zero.  If so, it rounds
> > up to 4503599627370497.0;  otherwise, it rounds however you handle
> > the halfway value.  As __STDC_IEC_559__ is predefined by my
> > implementation, the rules of IEC/ISO 60559 (== IEEE 754) apply,
> > which require that the half-way point be rounded to set the last bit
> > to 0, which would correspond to 4503599627370496.0 in this case.
> > 
> > Either way, there's never any need to store any data after processing
> > the first 17 significant digits.  Handling the first 17 digits might
> > require storing a lot more than 80 bits, but it requires a lot less
> > than 1000+ bits.
> > 
> > ================
> > 
> > What is wrong with the above reasoning?
> 
> Well, lets apply that to the case I described above. The first 17
> significant digits of
> 1.00000000000000011102230246251565404236316680908203125 are
> 1.0000000000000001. But, depending upon the rounding mode,
> 1.00000000000000011102230246251565404236316680908203124 must be rounded
> to 1.0, while 1.00000000000000011102230246251565404236316680908203126
> must be rounded to
> 1.0000000000000002220446049250313080847263336181640625. What is the
> algorithm that allows you to determine the correct rounding of such a
> digit string without storing anything past the 17th digit? Checking
> whether any of the subsequent digits is non-zero is NOT the right
> criterion.
> 
> The key fact is that an exact decimal representation of 2^N for positive
> N requires ceil(N*log10(2))) digits, while an exact decimal
> representation of 2^N when N is negative requires -N digits. Therefore,
> the worst case isn't one where the bracketing representable numbers are
> integers, but rather one where the differ by a number much smaller than
> 1.0.
> 
> I didn't claim to have identified the exact worst case, I merely
> described a feature that I believe must apply to the worst case, and
> gave an example with that feature that requires significantly more than
> 17 significant digits to resolve. All you gave was another example, that
> also has that feature, but only requires 17 digits to resolve. As
> examples, when the question is identifying the worst case, the example
> that is worst sets a lower bound for the true worst case, so my example
> trumps yours.
> Thinking about it some more in response to your question, I suspect that
> a number slightly less than 1.0 might require slightly more significant
> digits than one slightly higher than 1.0. However, I don't have time to
> confirm that right now.

I was wrong - it's the same number of significant digits:

The following are two consecutive representable values on my system:
0.999999999999999777955395074968691915273666381835937500
0.999999999999999888977697537484345957636833190917968750

The digit string
0.999999999999999833466546306226518936455249786376953125
has a value exactly half-way between them. Therefore,
0.999999999999999833466546306226518936455249786376953124 should round to
0.999999999999999777955395074968691915273666381835937500, while
0.999999999999999833466546306226518936455249786376953126 should round to
  123456789012345678901234567890123456789012345678901234

Therefore, when converting either of those digit strings to double, it's
necessary to look at 54 significant digits before deciding which way to
round it, the same as my previous example. There might be some clever
way of dealing with such strings that avoids the necessity of storing
all of those digits in some fashion, but the method you described which
checks only for whether or not any of the following digits is non-zero
can only be applied after first reading in
"0.999999999999999833466546306226518936455249786376953125"; it cannot
kick in after the 17th significant digit, as was the case with your
example.

> I also suspect that the worst case might be such
> a number - but that would take even longer to confirm.

I won't attempt to address that issue tonight, or any time soon. I've
got lots of higher priority things to deal with right now, including
income taxes.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: A final word on casting. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-02-25 23:26 -0800
  Re: A final word on casting. "I Set My Girlfriend's Pantyhose on Fire" <cdalten@gmail.com> - 2019-02-26 03:12 -0800
  Re: A final word on casting. James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-02-26 05:41 -0800
    Re: A final word on casting. James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-02-26 19:00 -0800
      Re: A final word on casting. James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-02-27 06:37 -0800
  Re: A final word on casting. James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-02-28 07:45 -0500
    Re: A final word on casting. James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-02-28 08:20 -0500
    Re: A final word on casting. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-02-28 15:16 +0000
      Re: A final word on casting. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-03-01 01:16 +0000
        Re: A final word on casting. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-03-02 01:10 +0000
    Re: A final word on casting. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-03-06 08:36 -0800
      Re: A final word on casting. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-03-06 09:04 -0800
        Re: A final word on casting. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-03-21 11:19 +0000
    Re: A final word on casting. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-03-06 09:33 -0800
      Re: A final word on casting. James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-03-06 11:19 -0800
        Re: A final word on casting. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-03-23 10:49 -0700
          Re: A final word on casting. James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-03-25 12:06 -0700

csiph-web