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

Groups > comp.lang.c > #141398 > unrolled thread

Re: A final word on casting.

Back to article view | Back to comp.lang.c

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  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

#141398 — Re: A final word on casting.

James Kuyper <jameskuyper@alumni.caltech.edu> writes:

> On 1/3/19 22:27, Richard Damon wrote:
>
>> On 1/3/19 1:55 PM, Bart wrote:
>>
>>> I found that if I used 80-bit floats, then I can get results that match
>>> those from strtod, and those produced by gcc.  (That is, given 1000
>>> random floating point numbers of varying precision and range in source
>>> code), the compiled binary pattern matches exactly.  For this set of
>>> numbers...)
>>>
>>> So I'm not sure what that 1000 bits is for that has been mentioned.
>>> 80-bit floats have only an extra 11 bits of precision.
>>>
>>> (This is experimental and done via non-portable inline ASM, but it shows
>>> that it can be done with only a few extra precision bits.  Since the
>>> discrepancy was only a couple of bits, this is not surprising.)
>>
>> 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?

[toc] | [next] | [standalone]

#141416

Casting doesn't really work on systems that check the type at runtime.

[toc] | [prev] | [next] | [standalone]

#141426

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 also suspect that the worst case might be such
a number - but that would take even longer to confirm.

I still have no idea how to construct a case requiring storage of
significantly more bits than would be required to represent a 54 digit
integer. If someone claims to have a valid argument for such a case,
I'm willing to listen - it's entirely plausible that I've missed a
relevant issue.

[toc] | [prev] | [next] | [standalone]

#141469

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.

[toc] | [prev] | [next] | [standalone]

#141481

On Tuesday, February 26, 2019 at 10:00:47 PM UTC-5, James Kuyper wrote:
...
> 0.999999999999999833466546306226518936455249786376953126 should round to
>   123456789012345678901234567890123456789012345678901234

Sorry about that, I'm not sure how that last digit string got there. It
should have been:
0.999999999999999888977697537484345957636833190917968750

[toc] | [prev] | [next] | [standalone]

#141490

On 2/26/19 08:41, James Kuyper wrote:
...
> 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 on the right track, I just had to go down one order of magnitude.
The following are a consecutive pair of exactly representable double values:

0.100000000000000005551115123125782702118158340454101562500 ==
0x1.999999999999ap-4
0.100000000000000019428902930940239457413554191589355468750
== 0x1.999999999999bp-4

The value exactly half way between them is:
0.100000000000000012490009027033011079765856266021728515625
== 0x1.999999999999a8p-4

Therefore,
0.100000000000000012490009027033011079765856266021728515624 should round
to 0x1.999999999999ap-4, while
0.100000000000000012490009027033011079765856266021728515626 should round
to 0x1.999999999999bp-4

Therefore, an implementation needs to read 57 significant digits before
it can determine which way to round either of those constants. For a
constant starting with
"0.100000000000000012490009027033011079765856266021728515625", it can
switch over to testing whether any of the subsequent digits is non-0,
but only after reading the first 57 significant digits.

[toc] | [prev] | [next] | [standalone]

#141494

On 2/28/19 08:00, Stefan Ram wrote:
> James Kuyper <jameskuyper@alumni.caltech.edu> writes:
>> exactly representable double values
> 
>   To represent a real number like 0,1, we must agree that
>   every binary representation represents a whole interval of
>   real values (usually an interval with more than one value).

You can choose to think of it that way, but you don't have to, and the
relevant standards are not defined that way. The C standard defines a
model for floating point representations where each possible
representation that doesn't represent a NaN or an infinity represents
one specific real number (5.2.4.2.2p2). ISO/IEC 60559 (== IEEE 754)
specifies floating point types which (no coincidence) fit that model. It
specifies that floating point operations result in a value that is one
of the two representable values bracketing the value that the operation
should produce mathematically, if evaluated in a type with infinite
range and infinite precision. It does NOT specify that they result in
the representation of the "bin" that the infinite range, infinite
precision value would fall into.

[toc] | [prev] | [next] | [standalone]

#141496

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>So, even 0.5 is not "exactly representable". So, there are no
>>exactly representable values in the type double.
>
>   In a sense a bit pattern for a floating point number /is/
>   exact:
>
>   It exactly represents a specific real interval.

And it's exact in another, simpler sense: it exactly represents a
rational.  For C, exactly which rational is explained in the C standard.

BTW, what interval do you think a particular bit pattern represents?

<cut>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#141524

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>BTW, what interval do you think a particular bit pattern represents?
>
>   The number one usually associates with a binary floating
>   point representation as printed by "%.9999g" (where "9999"
>   is intended to be infinite) in printf, I call the /face 
>   value of the representation/.

I call it the value since it seems so clear that that is what it is, but
I can see you might need a more complex term if you want "the value" to
be an interval.

It's better to specify this "face value" as the C standard does it,
because printf is not required to print it.

<cut>
>   A face value represents the set of all numbers who are
>   closer to that face value than to every other face value.

By number do you mean real?  If so, the interval is open at both ends,
with some real not in any interval, yes?

This interval is likely to be confusing for some because it does not
take IEEE rounding into account.  I don't see what advantage you gain
from taking this point of view.

<cut>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#141596

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>By number do you mean real?  If so, the interval is open at both ends,
>>with some real not in any interval, yes?
>
>   Let me put it this way:
>
>   Definition
>
>   I say that a rational number x is in the /catchment set/ of a
>   rational number y under a C implementation M, iff under M,
>   y is the rational value corresponding to the result of the
>   evaluation of a floating constant R that represents x.
>
>   End of Definition

That does not associate an interval with a floating-point bit pattern
which was, I thought, how you viewed floating-point numbers.  It's now
about what source forms go into which intervals.

Also, I find it a little confusing because it appears to beg the
question using "represents x" without explaining this other meaning for
represents.  For example, if 1.23 and 0.123e1 convert to different bit
patterns (as C permits them to) do these two floating constants
represent different x's?  I suppose they must but I don't think you
expected them to.

<cut>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#141731

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> Supersedes: <exactly-20190228135433@ram.dialup.fu-berlin.de>
>
>   To represent a real number like 0.1, we must agree that
>   every binary representation represents a whole interval of
>   real values (usually an interval with more than one value).
>
>   To represent the real number 0.5, we can choose what seems
>   to be an "exact representation", but when that representation
>   is given to us, we /cannot/ reason that it represents the
>   real value 0.5 "exactly", [...]

I can.  But then I have the advantage of having received a pretty
good education in Numerical Analysis.

[toc] | [prev] | [next] | [standalone]

#141734

On Wednesday, 6 March 2019 16:37:00 UTC, Tim Rentsch  wrote:
> ram@zedat.fu-berlin.de (Stefan Ram) writes:
> 
> > Supersedes: <exactly-20190228135433@ram.dialup.fu-berlin.de>
> >
> >   To represent a real number like 0.1, we must agree that
> >   every binary representation represents a whole interval of
> >   real values (usually an interval with more than one value).
> >
> >   To represent the real number 0.5, we can choose what seems
> >   to be an "exact representation", but when that representation
> >   is given to us, we /cannot/ reason that it represents the
> >   real value 0.5 "exactly", [...]
> 
> I can.  But then I have the advantage of having received a pretty
> good education in Numerical Analysis.
>
It depends where the data comes from. If you cut a one pixel long
line in half, 0.5 means exactly 0.5. If you measure the length
of a line drawn on a piece of paper, 0.5 means 0.5 within the 
precision of your measurement, which will surely be less precise than
the interval between 0.5 and the surrounding values representable
as a C double.
  

[toc] | [prev] | [next] | [standalone]

#142170

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Wednesday, 6 March 2019 16:37:00 UTC, Tim Rentsch  wrote:
>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>> 
>> > Supersedes: <exactly-20190228135433@ram.dialup.fu-berlin.de>
>> >
>> >   To represent a real number like 0.1, we must agree that
>> >   every binary representation represents a whole interval of
>> >   real values (usually an interval with more than one value).
>> >
>> >   To represent the real number 0.5, we can choose what seems
>> >   to be an "exact representation", but when that representation
>> >   is given to us, we /cannot/ reason that it represents the
>> >   real value 0.5 "exactly", [...]
>> 
>> I can.  But then I have the advantage of having received a pretty
>> good education in Numerical Analysis.
>>
> It depends where the data comes from. If you cut a one pixel long
> line in half, 0.5 means exactly 0.5. If you measure the length
> of a line drawn on a piece of paper, 0.5 means 0.5 within the 
> precision of your measurement, which will surely be less precise than
> the interval between 0.5 and the surrounding values representable
> as a C double.

That conflates what a bit-pattern means with what it represents.

Also, I prefer to keep a distinction between precision and accuracy.
The accuracy of a measurement is not the same as the precision with it
it is reported (or stored in a computer).  I don't always get this
right, but I consider myself wrong when I don't.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#141739

James Kuyper <jameskuyper@alumni.caltech.edu> writes:

> On 2/26/19 08:41, James Kuyper wrote:
> ...
>
>> 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 on the right track, I just had to go down one order of magnitude.
> The following are a consecutive pair of exactly representable double values:
>
> 0.100000000000000005551115123125782702118158340454101562500 ==
> 0x1.999999999999ap-4
> 0.100000000000000019428902930940239457413554191589355468750
> == 0x1.999999999999bp-4
>
> The value exactly half way between them is:
> 0.100000000000000012490009027033011079765856266021728515625
> == 0x1.999999999999a8p-4
>
> Therefore,
> 0.100000000000000012490009027033011079765856266021728515624 should round
> to 0x1.999999999999ap-4, while
> 0.100000000000000012490009027033011079765856266021728515626 should round
> to 0x1.999999999999bp-4
>
> Therefore, an implementation needs to read 57 significant digits before
> it can determine which way to round either of those constants.  For a
> constant starting with
> "0.100000000000000012490009027033011079765856266021728515625", it can
> switch over to testing whether any of the subsequent digits is non-0,
> but only after reading the first 57 significant digits.

The number 2**300, which is

  2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397376

is exactly reprsentable.  The next representable number is
2**300 + 2**248, so halfway between those is 2**300 + 2**247,
which is

  2037035976334486312424869980042572347713548488759506276554079249433607939328930471638728704

This gets us up to 91 digits.  Can we do better?

[toc] | [prev] | [next] | [standalone]

#141747

On Wednesday, March 6, 2019 at 12:33:14 PM UTC-5, Tim Rentsch wrote:
> James Kuyper <jameskuyper@alumni.caltech.edu> writes:
> 
> > On 2/26/19 08:41, James Kuyper wrote:
> > ...
> >
> >> 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 on the right track, I just had to go down one order of magnitude.
> > The following are a consecutive pair of exactly representable double values:
> >
> > 0.100000000000000005551115123125782702118158340454101562500 ==
> > 0x1.999999999999ap-4
> > 0.100000000000000019428902930940239457413554191589355468750
> > == 0x1.999999999999bp-4
> >
> > The value exactly half way between them is:
> > 0.100000000000000012490009027033011079765856266021728515625
> > == 0x1.999999999999a8p-4
> >
> > Therefore,
> > 0.100000000000000012490009027033011079765856266021728515624 should round
> > to 0x1.999999999999ap-4, while
> > 0.100000000000000012490009027033011079765856266021728515626 should round
> > to 0x1.999999999999bp-4
> >
> > Therefore, an implementation needs to read 57 significant digits before
> > it can determine which way to round either of those constants.  For a
> > constant starting with
> > "0.100000000000000012490009027033011079765856266021728515625", it can
> > switch over to testing whether any of the subsequent digits is non-0,
> > but only after reading the first 57 significant digits.
> 
> The number 2**300, which is
> 
>   2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397376
> 
> is exactly reprsentable.  The next representable number is
> 2**300 + 2**248, so halfway between those is 2**300 + 2**247,
> which is
> 
>   2037035976334486312424869980042572347713548488759506276554079249433607939328930471638728704
> 
> This gets us up to 91 digits.  Can we do better?

OK - now I see what you mean, and what it is that I missed. Your point would have been clearer if you'd presented such an example in the first place, rather than presenting one for which 17 digits were sufficient. Why do you have to be so cryptic?

DBL_MAX is at least 1e37 according to the C standard, and is 0X1.fffffffffffffP1023 for IEEE double. 1fffffffffffff is 9007199254740991, and therefore not divisible by 5, so the decimal representation of that value won't have any trailing 0s, and therefore neither will the value halfway between that one and the previous exactly representable value. A naive implementation would have to store at least 1025 bits of information to determine which way to round such a constant. I won't rule out the possibility that a more clever algorithm might reduce the amount of storage needed, but I can at last finally see where the claim "more than 1000 bits" comes from.

Why couldn't you have said so directly, rather than wasting your time and mine going around the back way?

[toc] | [prev] | [next] | [standalone]

#142300

James Kuyper <jameskuyper@alumni.caltech.edu> writes:

> On Wednesday, March 6, 2019 at 12:33:14 PM UTC-5, Tim Rentsch wrote:
>
>> James Kuyper <jameskuyper@alumni.caltech.edu> writes:
>>
>>> On 2/26/19 08:41, James Kuyper wrote:
>>> ...
>>>
>>>> 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 on the right track, I just had to go down one order of magnitude.
>>> The following are a consecutive pair of exactly representable double
>>> values:
>>>
>>> 0.100000000000000005551115123125782702118158340454101562500 =>
>>> 0x1.999999999999ap-4
>>> 0.100000000000000019428902930940239457413554191589355468750
>>> == 0x1.999999999999bp-4
>>>
>>> The value exactly half way between them is:
>>> 0.100000000000000012490009027033011079765856266021728515625
>>> == 0x1.999999999999a8p-4
>>>
>>> Therefore,
>>> 0.100000000000000012490009027033011079765856266021728515624 should round
>>> to 0x1.999999999999ap-4, while
>>> 0.100000000000000012490009027033011079765856266021728515626 should round
>>> to 0x1.999999999999bp-4
>>>
>>> Therefore, an implementation needs to read 57 significant digits before
>>> it can determine which way to round either of those constants.  For a
>>> constant starting with
>>> "0.100000000000000012490009027033011079765856266021728515625", it can
>>> switch over to testing whether any of the subsequent digits is non-0,
>>> but only after reading the first 57 significant digits.
>>
>> The number 2**300, which is
>>
>>  20370359763344860[...]40449354381299763336706183397376
>>
>> is exactly reprsentable.  The next representable number is
>> 2**300 + 2**248, so halfway between those is 2**300 + 2**247,
>> which is
>>
>>  2037035976334486[...]79249433607939328930471638728704
>>
>> This gets us up to 91 digits.  Can we do better?
>
> OK - now I see what you mean, and what it is that I missed.  Your
> point would have been clearer if you'd presented such an example in
> the first place, rather than presenting one for which 17 digits were
> sufficient.  Why do you have to be so cryptic?

Here are some things you could have done:

(1) Spent a few minutes (10 or 15 should have been enough)
looking on the web for papers on the subject;  or

(2) Picked two or three floating point values, chosen at random
in the space of representable floating point numbers, rather than
just one value almost smack in the middle of the exponent range;
or

(3) Tried writing a floating point conversion routine yourself,
under the guideline that you be confident it would produce
correct results in all cases.

If you had done any one of those things I think you would have
found out for yourself without my having to be involved at all.
So why didn't you?

> DBL_MAX is at least 1e37 according to the C standard, and is
> 0X1.fffffffffffffP1023 for IEEE double.  1fffffffffffff is
> 9007199254740991, and therefore not divisible by 5, so the decimal
> representation of that value won't have any trailing 0s, and
> therefore neither will the value halfway between that one and the
> previous exactly representable value.  A naive implementation
> would have to store at least 1025 bits of information to determine
> which way to round such a constant.  I won't rule out the
> possibility that a more clever algorithm might reduce the amount
> of storage needed, but I can at last finally see where the claim
> "more than 1000 bits" comes from.
>
> Why couldn't you have said so directly, rather than wasting your
> time and mine going around the back way?

A better question is, considering your history of contentious and
garrulous obtuseness, why should I have bothered responding at
all in the first place?  I must confess I don't have a good
answer to that question.

[toc] | [prev] | [next] | [standalone]

#142426

On Saturday, March 23, 2019 at 1:49:40 PM UTC-4, Tim Rentsch wrote:
> James Kuyper <jameskuyper@alumni.caltech.edu> writes:
...
> > OK - now I see what you mean, and what it is that I missed.  Your
> > point would have been clearer if you'd presented such an example in
> > the first place, rather than presenting one for which 17 digits were
> > sufficient.  Why do you have to be so cryptic?
> 
> Here are some things you could have done:
> 
> (1) Spent a few minutes (10 or 15 should have been enough)
> looking on the web for papers on the subject;  or

If your initial mention of this 1000+ bits requirement had at least been
accompanied by sufficient information to allow me to search for the
relevant messages, I would have been happy to pursue the question
without involving you. I tried finding it, and failed. 15 minutes was
NOT sufficient - I spent at least a half hour trying and failing to
locate it from the information you provided. My subsequent messages have
all been fueled, at least in part, by my annoyance at your failure to
provide sufficient information to locate those messages.

> (2) Picked two or three floating point values, chosen at random
> in the space of representable floating point numbers, rather than
> just one value almost smack in the middle of the exponent range;
> or
> 
> (3) Tried writing a floating point conversion routine yourself,
> under the guideline that you be confident it would produce
> correct results in all cases.
> 
> If you had done any one of those things I think you would have
> found out for yourself without my having to be involved at all.
> So why didn't you?

You've expressed unwarranted confidence in my ability to understand what
you were getting at before; I believe that his is another example of
unwarranted confidence. I think you believe it would have taken me far
less time to follow one of those alternatives than would actually be the
case. I have only a limited amount of spare time; and not enough
interest in this topic to feel justified to spend the time needed to
follow up any of those alternatives. It would have taken you far less
time to provide a clear example than it would have taken me to to follow
any of those alternatives.

...
> > Why couldn't you have said so directly, rather than wasting your
> > time and mine going around the back way?
> 
> A better question is, considering your history of contentious and
> garrulous obtuseness, why should I have bothered responding at
> all in the first place?  I must confess I don't have a good
> answer to that question.

I recommend looking for one - your response wasn't particularly useful
to me, and no one else has made a comment indicating that they found it
any more useful than I did (I've deliberately worded that sentence to
leave open the possibility that there was such people, but that they
didn't bother making such a comment - so don't you dare suggest that I'm
"jumping to conclusions" again).

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web