[TAG] Paul Sephton's article "A Question Of Rounding"

[René Pfeiffer]

Hello, Paul!

I am beginning to understand your motivations for your article and
that's why I wish to reply to you and TAG in order to direct your and
mine comments to the right place.

On Oct 04, 2007 at 0031 +0200, Paul Sephton appeared and said:
> On Wed, 2007-10-03 at 23:17 +0200, Ren? Pfeiffer wrote:
> > Yes, but you don't seem to get the point of the nature of floating point
> > arithmetics. http://www2.hursley.ibm.com/decimal/decifaq1.html#inexact
> > was suggested to you multiple times and clearly states:
> > "Binary floating-point cannot exactly represent decimal fractions, so if
> > binary floating-point is used it is not possible to guarantee that
> > results will be the same as those using decimal arithmetic."
> Um.
> 
> This was a huge frustration for me in the bug report.  If I don't "get"
> the point about FP after 23 years programming computers, and a
> background in chemistry, then no-one "gets" it.

Well, probably, but statements like these may be regarded as arrogant
and may lead to adding more fuel to a flame war. I believe this is why
the bug report got a bit out of hand.

> I am perfectly aware of the inaccuracies of FP math.  I deal with and
> have dealt with it intimately.  Everyone keeps telling me though, that I
> "don't get it" and flame me when I argue with them.

I think this is due to a misunderstanding. I will come back to this
later.

> > After reading the conversation in the bug tracking system I am not so
> > sure about which answers get through to you and which do not.
> 
> The bug report's a mess.  I understand that.

And so was my review. I should have added some comments, and that's what
I am doing now.

> > [...]
> > I don't agree with you about the precision. As far as I understand you
> > are talking about a precision of 15 while the theorem 15 in the article
> > states:
> > 
> > "When a binary IEEE single precision number is converted to the closest
> > eight digit decimal number, it is not always possible to uniquely
> > recover the binary number from the decimal one. However, if nine decimal
> > digits are used, then converting the decimal number to the closest
> > binary number will recover the original floating-point number."
> 
> I think you refer to the 4 byte IEEE?  8 byte doubles have 15
> significant decimal digits of precision.

Yes, you are right, I was refering to the 4 byte IEEE format.

> > By using a precision of 15 you are already over the limit of the IEEE
> > 754 format, IMHO.
> 
> It depends on how you deal with the number.  If you try to convert the
> number to decimal starting with the most significant digit, then for
> imprecisely stored values, you end up with a remainder at the end that
> you can just keep dividing ad infinitum.  Around half the time, the
> number is below the actual, which results in rounding down.  The other
> half, you end up with a value higher than the actual which results in
> rounding down.
> 
> Working from the known precision of 15 backwards, allows you to carry
> the imprecise portion (after decimal 15) forward, and correctly round
> the numbers.

I wouldn't do that. I did some experiments by converting decimal numbers
to IEEE 754 and back to see how accurate the conversion is. As I said I
would stay away from the least significant digits, but frankly I haven't
thought much about the error I'd be doing then.

> > > Point here is that it can be done, but no-one is doing it.
> > 
> > Maybe because people use other means of processing numbers in certain
> > cases.
> 
> Yes.  Mostly sprintf(), since no-one is aware of the difference between
> MS and GNU LibC.  The reason for the article in the first place was to
> raise peoples awareness of the discrepancy.

And I think that's what went wrong. I compared the article with the bug
report. I believe that the impression of your intentions was to continue
your efforts on this article since the bug report deteriorated into a
lengthy discussion and evnetually a bit of a flame war. Your article can
be perceived as "if you don't listen to me, I'll find someone else to
talk to". During the email exchange with you I now know that you wanted
to raise awareness for the behaviour of sprintf() in combination with
floating point to string conversion. This is different from the
impression you left in the discussion of the bug, but it seems that
emotions were boiling and everyone wanted you to be silent about the
matter.

Your article can be read as an attack on the GNU C Library developers,
and that may be the cause of all the reactions.

> > My background is theoretical physics and although it has been a long
> > time since I did simulations of particle collisions I remember to stay
> > away from the "end" of the mantissa, not using all available bits and
> > avoiding certain library functions because they might introduce more
> > errors than the measured/simulated data can handle.
> 
> And mine is in Analytical and Nuclear Chemistry.   That part of my
> training is still ingrained in me.  I absolutely agree with your points
> on accuracy.

Thanks. It seems my memory is better than I think then. :)

> > > If you are really interested in having arbitrary precision
> > > operations
>
> I'm not.  I in fact need no more than a few decimal digits of precision
> in our software.  It's not as if I'm building an accounting or banking
> package and need to count beans- although I wonder if the FP arithmetic
> would not have sufficed even then- GnuCash I believe uses it quite
> successfully.  But I digress.

So now I know what your intentions are. The bug report and your article
didn't tell me explicitly that you were aware of all this. I thought you
wanted someone to "fix the FP behaviour of glibc into submission".

> [...]
> All in all, I am not the one with the problem here.  I don't need help
> "fixing" anything.  I reported what I believe is a bug introduced
> through a misinterpretation of the C language spec- and incorrect
> application of the IEEE specification to the process of displaying a
> number.
> 
> I would honestly like to see people owning up to that mistake and
> correcting it rather than hiding behind a ream of specifications.

I wouldn't call it hiding. Vincent Lef?vre already the details of the
specifications and how they are implemented. The developers of the glibc
can't be blamed if standards leave things open. There are a lot of
other protocols and specifications that do that as well. Sometimes you
hit this uncharted territory and have to make sure that your code uses
reasonable defaults and catches/corrects undesired behaviour of library
functions.

> > > I am talking about the process of displaying a floating point
> > > number to a desired precision using sprintf().  MS rounds it one
> > > way, and GNU C library does it another. [...]
> > 
> > Yes, and no one disputes this fact. It's just the behaviour of two
> > different software packages well within the specification. This may not
> > be the desired case, but if floating point numbers in combination with
> > sprintf() fail, then you simply have to use another way, as was
> > suggested multiple times. We did the same thing when doing numerical
> > calculations in theoretical physics. Simple stuff, too. And daily tasks
> > of developers.
> 
> Again, I do not have a problem.  Repeated suggestions as to how I could
> correct this myself have been spurious and redundant.  I am perfectly
> capable of building my own binary to text conversion, as demonstrated.

I know that now, so I don't need to suggest anything anymore. :)

> Rather, my arguments are on behalf of thousands of programmers who are
> blissfully unaware of the dangers of sprintf in binary to text
> conversion.

And that's the main reason why I approved your article. In my opinion
every bit of information that warns developers of unsuspected "dangers"
or "deviant results" is a good thing. 

> > I wouldn't be so sure about that since this claim is very hard to proof.
> > You call an awful lot of C library functions. You would have to trace
> > every conversion between the binary and decimal formats, and in addition
> > to the IEEE 754 representation after every mathematical operation. This
> > is best done with a debugger by collecting all computed values and
> > comparing them after every step in order to trace potential errors and
> > all the bits of the FP representation.
> 
> Alternatively, prove it with the brute force approach, as I have done.
> Throw randomly generated values at it until it has covered a
> representative proportion of the problem space.  I would think 10
> million random numbers without failure should be significant, don't you?
> If not, I could run it overnight and do 500 million, or over a week and
> do a couple of billion.

I could do that as well, but I doubt we would get a deeper insight into
this. 

> [...]
> If you reviewed the article on it's own merit, and did not find it
> wanting, then there is little reason to depart from your initial view.
> Nothing I have said in the bug report is in contradiction to the
> article.

No, it isn't, and due to the comments on TAG we now have a sufficiently
annotated article. I don't think that "watch out for sprintf() doing
something unexpected/unwanted" is a statement that needs to be
retracted. We also have more than enough proposals how to get around
this peculiarity and use other methods which may be less prone to
inaccuracies.

> [...]
> - neither did I claim that IEEE rounding to nearest even on boundaries
> is incorrect for FP operations or storage.  I said that using the IEEE
> rounding mode to decide how to round decimal numbers for display is
> incorrect according to accepted industry standards.

Indeed, but IEEE 754 has been written, new proposals are coming and
everyone reading your article, the bug report and hopefully this
conversation on TAG can now decide which methods to use. By seeing
everything in this light I hope not to see any further flame wars on
this topic.

> What I said right upfront, is that when converting a binary value to
> text, the results are inconsistent.  It was immediately proven to me
> that the results were not inconsistent, but consistently wrong- at least
> according to industry standards.  Subsequently I proved that the results
> were inconsistent with Microsoft's results.  Thereafter the whole bug
> report devolved into a flame war.
> 
> A whole seperate discussion evolved about accuracy- which was never an
> issue from my side.  I am quite happy with the accuracy I have.  I am
> unhappy with sprintf's rather mediocre attempt at binary to text
> conversion though.

Well, and until now I wasn't aware that you were happy about the
accuracy you have. :)

> How would you interpret the C99 specification where it says:
> 
> "Paragraph 2: Conversions involving IEC 60559 formats follow all
> pertinent recommended practice. In particular, conversion between any
> supported IEC 60559 format and decimal with DECIMAL_DIG or fewer
> significant digits is correctly rounded, which assures that conversion
> from the widest supported IEC 60559 format to decimal with DECIMAL_DIG
> digits and back is the identity function."

I think that this is done according to the specification. You take a
supported IEC 60559 format, convert into a decimal representation and
use a rounding scheme that allows you to reconvert the decimal
representation back into a supported number in IEC 60559 format. From my
point of view the phrase "correctly rounded" does not necessarily refer
to the industrial standard rounding you describe. This may be wrong, but
I think this is simply due to the limitation of the binary floating
point format.

I looked for lectures on numerical mathematics to remember how we did
the rounding. I found a lecture by Prof. Dr. R. Rannacher from the
University of Heidelberg. From what I saw in his script a common method
of rounding in the binary FP format expects the number to be rounded to
be from an interval of possible FP numbers and maps it to another number
with a constraint shown in formula 1.1.2.

http://web.luchs.at/gfx/numeric_rounding.png

The constraint basically limits the distance between the original and
the rounded number. The last formula give a recipe on how to do that in
the IEEE format. Sadly I am too tired to translate the German and try
out the rounding formula on one of your example numbers from your C
code. I'll do that as soon as my brain catches up. :)

> I feel very strongly about the GNU C library, and want it to be the best
> there is.  Am I wrong to persue what I percieve to be a problem that
> might affect it's future?

No, I don't think you are wrong, but you have to keep in mind that
people might react strongly when being accused of being wrong. The Road
to Hell is paved with Good Intentions. Again until now I wasn't aware
that you feel strongly about the GNU C library; your article can also be
seen as a bashing of the GNU C library. Fortunately we now know that
this is not the case. And I think this is all due to the language used
and a load of misunderstandings.

Best wishes,
Ren?,
off to bed.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://lists.linuxgazette.net/mailman/private/tag/attachments/20071004/de9a4d77/attachment.pgp