Re: real.c fails floating point tests

Re: real.c fails floating point tests

[Robert Dewar]

<<The harness in contrib/paranoia.cc calls into real_arithmetic
and real_compare, which calls each of these functions.
>>

Well that sure sounds like it should be a sufficient test. Sorry Richard
for my unjustified assumption that you had not run paranoia (which sounded
really really odd). 

Anyway something is peculiar here. 

Re: real.c fails floating point tests

[Robert Dewar]

> Previously the REAL_VALUE_TYPE could not contain auxiliary
> information, because often it was actually just emulating a host computer
> double.  If you have removed that restriction then you can put various
> other items into the data structure and then it looks like it would be
> simple to make the 160-bit precision follow some arithmetic rules that
> are easier to analyze and test.

I definitely agree with this analysis. High precision is never an adequate
susbtitute for well defined axiomatic properties when it comes to fpt.

Re: real.c fails floating point tests

[Stephen L Moshier]

On Wed, 16 Oct 2002, Richard Henderson wrote:

> Paranoia runs vs the 160 bit internal arithmetic *will* fail,

Yes, that is what I am talking about.  The decimal<->binary
uses this arithmetic and its pathological behavior makes it
hard to test and hard to analyze.  IEEE 754 and 854 provide the
results of an analysis, telling how high the arithmetic precision
must be to meet the requirements of the standard.  That analysis
assumes the arithmetic follows the other IEEE rules and therefore
it does not apply to this situation.  That leaves us in somewhat
of a quandry.

The guard and sticky bits are not supposed to be part of the number.
They are auxiliary variables used to implement the rounding rules.  It
is OK to keep the number in an undrounded state and preserve the
sticky bit somewhere else in the data structure.  But using the bottom
bit of the number for the sticky bit does not make arithmetic sense
for the 160-bit version.

Previously the REAL_VALUE_TYPE could not contain auxiliary
information, because often it was actually just emulating a host computer
double.  If you have removed that restriction then you can put various
other items into the data structure and then it looks like it would be
simple to make the 160-bit precision follow some arithmetic rules that
are easier to analyze and test.

Re: real.c fails floating point tests

[Richard Henderson]

On Thu, Oct 17, 2002 at 03:01:19PM +0100, Joern Rennecke wrote:
> Did you try to go implement ldexp / frexp first,
>  and go from there?

Yes.


r~

Re: real.c fails floating point tests

[Joern Rennecke]

> Yeah, well, I tried to write log/exp/pow routines that didn't
> get too fresh with the representation, and yet produced result
> that were sufficiently accurate, but failed.

Did you try to go implement ldexp / frexp first,
 and go from there?

-- 
--------------------------
SuperH (UK) Ltd.
2410 Aztec West / Almondsbury / BRISTOL / BS32 4QX
T:+44 1454 465658

Re: real.c fails floating point tests

[Robert Dewar]

<<When I checked in the code, I had a 100% success for Paranoia
on x86, sparc, and alpha.  I've not checked since then since
I'd not changed the arithmetic routines at all.  I'll re-check.
>>

OK, well that's reassuring. I withdraw my comment about not running
Paranoia :-)

Re: real.c fails floating point tests

[Richard Henderson]

On Wed, Oct 16, 2002 at 06:54:35PM -0400, Stephen L Moshier wrote:
> That does not test the 160-bit internal arithmetic, which is what the posted
> report was all about.  We seem to be talking about different things there.

Apparently.

Paranoia runs vs the 160 bit internal arithmetic *will* fail,
because the internal arithmetic (1) doesn't round and (2)
doesn't implement guard digits.  This is because it is expected
that the extra precision of the internal representation *is*
the guard digit.  The results will be correct after rounding
for some smaller external format.  As far as I can tell, the
old real.c implementation was the same in this respect.

> Also, beware that contrib/paranoia.cc is currently a watered-down test
> because the log, exp, pow functions use the host computer's math
> library instead of the arithmetic supposedly under test.

Yeah, well, I tried to write log/exp/pow routines that didn't
get too fresh with the representation, and yet produced result
that were sufficiently accurate, but failed.

Note that substituting native fpu arithmetic into these routines
didn't change this failure, so I don't believe this is a flaw
in the real.c routines, merely that it is quite difficult to
write accurate libm routines.

> I am mainly concerned about the decimal <-> binary conversion, which
> does exercise the internal arithmetic.  I'll continue to test and
> post decimal-binary cases as time permits.

Please do.


r~

Re: real.c fails floating point tests

[Stephen L Moshier]

> The harness in contrib/paranoia.cc calls into real_arithmetic
> and real_compare, which calls each of these functions.

That does not test the 160-bit internal arithmetic, which is what the posted
report was all about.  We seem to be talking about different things there.
Also, beware that contrib/paranoia.cc is currently a watered-down test
because the log, exp, pow functions use the host computer's math
library instead of the arithmetic supposedly under test.

I am mainly concerned about the decimal <-> binary conversion, which
does exercise the internal arithmetic.  I'll continue to test and
post decimal-binary cases as time permits.

Re: real.c fails floating point tests

[Mark Mitchell]

--On Wednesday, October 16, 2002 03:03:15 PM -0700 Richard Henderson 
<rth@redhat.com> wrote:

> On Wed, Oct 16, 2002 at 11:01:57AM -0700, Mark Mitchell wrote:
>> (2) Richard, would you take a look at the bugs, as the architect of the
>>    new code?
>
> Yes.  I've been looking at the real_to_decimal problem reported
> yesterday already.

Cool!

Thanks,

-- 
Mark Mitchell                mark@codesourcery.com
CodeSourcery, LLC            http://www.codesourcery.com

Re: real.c fails floating point tests

[Richard Henderson]

On Wed, Oct 16, 2002 at 11:01:57AM -0700, Mark Mitchell wrote:
> (2) Richard, would you take a look at the bugs, as the architect of the
>    new code?

Yes.  I've been looking at the real_to_decimal problem reported
yesterday already.



r~

Re: real.c fails floating point tests

[Richard Henderson]

On Wed, Oct 16, 2002 at 05:54:03PM -0400, Stephen L Moshier wrote:
> You tested do_add, do_multiply, do_divide, do_compare, do_fix_trunc
> in real.c?

Yes.

The harness in contrib/paranoia.cc calls into real_arithmetic
and real_compare, which calls each of these functions.


r~

Re: real.c fails floating point tests

[Stephen L Moshier]

> When I checked in the code, I had a 100% success for Paranoia
> on x86, sparc, and alpha.

You tested do_add, do_multiply, do_divide, do_compare, do_fix_trunc
in real.c?

Re: real.c fails floating point tests

[Richard Henderson]

On Wed, Oct 16, 2002 at 10:37:51AM -0400, Stephen L Moshier wrote:
> It is perplexing, why it was so important to remove a working
> arithmetic and substitute a non-working arithmetic.

The old implementation didn't work either.

It failed completely for denormal numbers for which the target
format also used a 15-bit exponent, i.e 80-bit double-extended
and 128-bit quad precisions.

> Here is the output of the PARANOIA test program for the current
> real.c arithmetic.

When I checked in the code, I had a 100% success for Paranoia
on x86, sparc, and alpha.  I've not checked since then since
I'd not changed the arithmetic routines at all.  I'll re-check.


r~

Re: real.c fails floating point tests

[Mark Mitchell]

--On Wednesday, October 16, 2002 11:05:59 AM -0400 Robert Dewar 
<dewar@gnat.com> wrote:

>> That is too harsh and unfair to be a basis of a productive technical
>> discussion.
>
> Well I must say that I am surprised that anyone would install an IEEE
> arithmetic simulator without running paranoia, this seems an absolutely
> essential first step in testing any such software. I don't see it as
> unfair at all to point out that this was a real misstep.

I agree that this is a very important problem.

Here are the things that we should do.

(1) Log the bugs in GNATS, as high-priority defects.

    Steve, can you do that?

    Please be sure to include the test programs, so that people can
    figure out how to reproduce the bugs.

(2) Richard, would you take a look at the bugs, as the architect of the
    new code?

I agree that running more tests would be a good idea in the future, but
the first priority should be to fix the defects.

Thanks,

-- 
Mark Mitchell                mark@codesourcery.com
CodeSourcery, LLC            http://www.codesourcery.com

Re: real.c fails floating point tests

[Stephen L Moshier]

On Wed, 16 Oct 2002, Andrew Haley wrote:

> Robert Dewar writes:
>  >
>  > Stephen, how easy would it be to install the paranoia test in an easily
>  > reusable form, so that this test can be run periodically?
>
> It's already been done, in contrib/paranoia.cc.

By way of warning, this does not seem entirely as advertised.
contrib/paranoia.cc is not testing the internal real.c arithmetic.
Also it is otherwise incomplete as it stands.  For example, it is
using the host computer's math library for the log, exp, pow
functions.  That defeats many of the paranoia tests.  The reported
abort was in pow2test, involving an arithmetic bug stimulated by the
pow function written in real.c's arithmetic.  So paranoia.cc is a
weakened test; it needs some more work to finish it, and it should
also test the internal arithmetic (the functions now called do_add,
do_divide, etc. in real.c).

I used to keep a functional test harness for real.c and various tests
for it (including paranoia and a C++ class to overload arithmetic
calls) but lost track when the gcc development moved to Cygnus.
Adapting and updating for the many gcc changes since then is not
something I have free time for at present.  The decimal to binary
conversion is the only item there that I need as a user, in self
defense, to have working, and what little time I do have for this now
is concentrated on that.

Sorry, but I do not have time either to get into a flame war.
I am not a software prima donna, I am just an irate customer.

Re: real.c fails floating point tests

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| I don't see it as
| unfair at all to point out that this was a real misstep. 

The point being that there *ways* to point out misstep.

-- Gaby

Re: real.c fails floating point tests

[Andrew Haley]

Robert Dewar writes:
 > 
 > Stephen, how easy would it be to install the paranoia test in an easily
 > reusable form, so that this test can be run periodically?

It's already been done, in contrib/paranoia.cc.

Andrew.

Re: real.c fails floating point tests

[David Edelsohn]

	paranoia.cc was added to the GCC "contrib" directory.  I do not
know if there are different versions.

David

Re: real.c fails floating point tests

[Robert Dewar]

> That is too harsh and unfair to be a basis of a productive technical
> discussion. 

Well I must say that I am surprised that anyone would install an IEEE
arithmetic simulator without running paranoia, this seems an absolutely
essential first step in testing any such software. I don't see it as
unfair at all to point out that this was a real misstep. 

Certainly for GNAT, we will reinstall the old version until this is
fixed, since this seems like a very serious source of problems given
that in Ada absolute accuracy of arithmetic is required.

One thing to learn from this is that paranoia should be a standard part
of the testing process for GCC. So that should be put on the list of
desirable projects.

It is one thing to say that you don't expect things to be 100% perfect,
but this degree of failure in paranoia is really not acceptable at all
I think.

Anyway, the question is what is the right step forward now, can we fix
the current code relatively quickly (a caution is that any such code
is very delicate, and it may not be easy to fix), or would it be better
to reinstall the old simulator pending this being done.

This is definitely a very serious breakage from where I sit (it could
explain a number of failures we have been seeing in GNAT 5).

I realy appreciate Stephen's work here, and really I don't think I
would call his message a flame, just reasonable technical concern over
a serious problem :-)

Stephen, how easy would it be to install the paranoia test in an easily
reusable form, so that this test can be run periodically?

Re: real.c fails floating point tests

[Gabriel Dos Reis]

Stephen L Moshier <steve@moshier.net> writes:

[...]

| It is hard to see how users are going to develop a degree of assurance
| that the current GCC arithmetic is correct.  It is perplexing, why it
| was so important to remove a working arithmetic and substitute a
| non-working arithmetic.

That is too harsh and unfair to be a basis of a productive technical
discussion. 

There was no concerted efforts to replace the old code with a broken
one.  To support various languages (mostly C and C++) requirements on
numerical characteristics, it was at some point _necessary_ to rework
the old difficult-to-maintain-and-to-extend code.  Here, I would like
to thank RTH for having done that job.  

Sure in some sense, we weren't expecting the first iteration to be
100% perfect (I'm not diminishing RTH's skills) from start.  It is
great that people like you can make reports about malfunctioning codes
in the new rewrite, but I think there is no necessity (no place?) for
flames about it.

Thanks for the report.

Yours,

-- Gaby

Re: real.c fails floating point tests

[Robert Dewar]

> Decimal <-> binary conversion is the most important floating point
> operation for the compiler, since there is no portable alternative but
> to write decimal numbers (the ugly C99 hexadecimal input will become
> generally available only in the distant future) and hope that they
> will be converted with sufficient accuracy into binary machine
> numbers.  I have reported some errors for this in the current GCC, and
> have also noticed that the decimal conversion method suffers from
> double-rounding error (test case to follow later).

Wouldn't it always be better to write out floating-point constants in
hex in the assembler file. You definitely cannot trust assemblers to
be absolute accuracy (absolute accuracy in such conversions is required
in Ada, and desirable in other languages).

real.c fails floating point tests

[Stephen L Moshier]

Here are some initial results of testing the new version of real.c.
Exhaustive testing of floating point arithmetic operations is
impractical except in the case of some unary single precision
operations.  We rely on test programs that probe for implementation
errors that have been found and debugged in the past, and on programs
that use random number or deterministic techniques to generate input values
that we think are likely to uncover problems.

GCC uses a software floating point arithmetic for binary <-> decimal
conversion and constant folding.  Previously it passed various test
programs for floating point arithmetic, thus giving some degree of
assurance that the arithmetic was correct.  Virtually all of the
floating point arithmetic test programs that have been developed since
1984 are for IEEE 754 arithmetic, and the programs do not work with
non-IEEE arithmetic.  The previous, working, GCC arithmetic has been
replaced by another arithmetic that does not pass such tests, and
cannot even run them without first going through a considerable
programming and debugging effort to modify the test code.

Decimal <-> binary conversion is the most important floating point
operation for the compiler, since there is no portable alternative but
to write decimal numbers (the ugly C99 hexadecimal input will become
generally available only in the distant future) and hope that they
will be converted with sufficient accuracy into binary machine
numbers.  I have reported some errors for this in the current GCC, and
have also noticed that the decimal conversion method suffers from
double-rounding error (test case to follow later).

Full implementation of C99 floating point pragmas will require that
the GCC arithmetic maintain the IEEE exception flags.  That means the
arithmetic has to be strictly IEEE compliant in each supported
precision.  For the flags to be correct, each operation must be
rounded off directly to target mode without double-rounding.  GCC
previously had a provision for that, but it seems to have been
removed.  Currently GCC calculates an extended precision result and
then double-rounds to the target precision.

It is hard to see how users are going to develop a degree of assurance
that the current GCC arithmetic is correct.  It is perplexing, why it
was so important to remove a working arithmetic and substitute a
non-working arithmetic.  There was a configuration problem for Cray
computers, which do not have a 16-bit integer type.  To solve Cray's
problem, the radix 65536 arithmetic code that depended on 16-bit
integers might have been replaced by the radix 2 arithmetic that was
used in gcc-2.4, and which was kept available as a fallback through
gcc-2.8.


Here is the output of the PARANOIA test program for the current
real.c arithmetic.

Notes:

 This arithmetic has severe underflow and overflow bugs; consequently
the test generates unexpected results while probing for the overflow
and underflow thresholds.

 There is no guard digit, consequently programs that depend on small
differences can fail.  In particular the test function pow2test had to
be omitted because that subtest induces a GCC abort while GCC is attempting
to convert a large number to a decimal string.  The GCC abort is a
consequence of the guard bit defect, which then triggers the overflow bug.

 This test printout is for i386-linux.  I am still trying to get the program
to run on a sparcstation.

----
This version of paranoia omits test for extra precise subexpressions
and includes a few additional tests.

0 = 0.0
00000000 00000000 00000000 00000000 00000000 00000000
1 = 1.00000000000000000000000000000000000000000000000e+0
00000009 00000000 00000000 00000000 00000000 80000000
1+1 = 2.00000000000000000000000000000000000000000000000e+0
00000011 00000000 00000000 00000000 00000000 80000000
Program is now RUNNING tests on small integers:
-1, 0, 1/2, 1, 2, 3, 4, 5, 9, 27, 32 & 240 are O.K.

Searching for Radix and Precision.
Radix = 2.00000000000000000000000000000000000000000000000e+0
00000011 00000000 00000000 00000000 00000000 80000000
Closest relative separation found is U 1 = 6.84227765783602085411977335590779360976690401307e-49
fffffb09 00000000 00000000 00000000 00000000 80000000
Recalculating radix and precision.confirms closest relative separation U1 .
Radix confirmed.
The number of significant digits of the Radix is 1.60000000000000000000000000000000000000000000000e+2
00000041 00000000 00000000 00000000 00000000 a0000000
Subtraction appears to be normalized, as it should be.
Checking for guard digit in *, /, and -.
Serious: - lacks Guard Digit, so cancellation is obscured
Checking rounding on multiply, divide and add/subtract.
* is neither chopped nor correctly rounded.
/ is neither chopped nor correctly rounded.
Addition/Subtraction neither rounds nor chops.
Sticky bit used incorrectly or not at all.
lack(s) of guard digits or failure(s) to correctly round or chop
(noted above) count as one flaw in the final tally below

Does Multiplication commute?  Testing on 20 random pairs.
X * Y == Y * X trial fails.
X=3.63050464352284616725107325384666317732717329962e-1
fffffff9 61a89aaf bf4e4c2a 81e04512 61a05152 b9e1c01e
Y=3.67074300256508518327699029234143153463545945784e-1
fffffff9 738367dd 3ef51b2c 262de0d2 9b8a2a7a bbf129a5

Running test of square root(x).
Testing if sqrt(X * X) == X for 20 Integers X.
Test for sqrt monotonicity.
sqrt has passed a test for Monotonicity.
Testing whether sqrt is rounded or chopped.
Square root is neither chopped nor correctly rounded.
Observed errors run from -6.04938271604938271604938717428160477599954110124e-1
00000005 3acd47eb 232dcd13 74f0bc8b a4587e6b 9add3c0c
	to 5.00000000000000000000000000000000000000000000000e-1
00000001 00000000 00000000 00000000 00000000 80000000
ulps.
Testing powers Z^i for small Integers Z and i.
... no discrepancies found.

Seeking Underflow thresholds UfThold and E0.
Smallest strictly positive number found is E0 = 6.98652447960225958099589122020050053280205923037e-80807125
80000009 00000000 00000000 00000000 00000000 80000000
Z = 6.98652447960225958099589122020050053280205923037e-80807125
80000009 00000000 00000000 00000000 00000000 80000000
Since comparison denies Z = 0, evaluating (Z + Z) / Z should be safe.
What the machine gets for (Z + Z) / Z is 2.00000000000000000000000000000000000000000000000e+0
00000011 00000000 00000000 00000000 00000000 80000000
This is O.K., provided Over/Underflow has NOT just been signaled.
Underflow is gradual; it incurs Absolute Error =
(roundoff in UfThold) < E0.
((CInvrse E0) (1.5+U2)) / (CInvrse (1+U2)) != E0
CInvrse = 1.23611798402889138811011757425565984235889332296e+80807047
7ffff809 00000000 00000000 00000000 00000000 80000000
E0 = 6.98652447960225958099589122020050053280205923037e-80807125
80000009 00000000 00000000 00000000 00000000 80000000
U2 = 1.36845553156720417082395467118155872195338080261e-48
fffffb11 00000000 00000000 00000000 00000000 80000000
X = 1.23611798402889138811011757425565984235889332296e+80807047
7ffff809 00000001 00000000 00000000 00000000 80000000
Y = 1.29542528326416669380795277942005993566740005467e-77
fffff809 00000001 00000000 00000000 00000000 c0000000
Y/X = 1.04795735075967608845681472584251343288499149546e-80807124
80000009 ffffffff ffffffff ffffffff ffffffff bfffffff
The Underflow threshold is 5.10540848309556841246314867661897963420482280488e-80807077
80000501 00000001 00000000 00000000 00000000 80000000
below which calculation may suffer larger Relative error than merely roundoff.
Since underflow occurs below the threshold
UfThold = 2.00000000000000000000000000000000000000000000000e+0
00000011 00000000 00000000 00000000 00000000 80000000
	to the power  -2.68435297000000000000000000000000000000000000000e+8
000000e5 00000000 00000000 00000000 00000000 fffff610
only underflow should afflict the expression 2.00000000000000000000000000000000000000000000000e+0
00000011 00000000 00000000 00000000 00000000 80000000
	to the power  -2.68435298000000000000000000000000000000000000000e+8
000000e5 00000000 00000000 00000000 00000000 fffff620
Actually calculating yields: 2.55270424154778420623157433830948981710241140244e-80807077
800004f9 00000000 00000000 00000000 00000000 80000000
This computed value is O.K.
Searching for Overflow threshold:
This may generate an error.
2.00000000000000000000000000000000000000000000000e+0
00000011 00000000 00000000 00000000 00000000 80000000
	times -Inf
00000006 00000000 00000000 00000000 00000000 00000000
	equals -Inf
00000006 00000000 00000000 00000000 00000000 00000000
Can `Z = -Y' overflow?
Trying it on Y = -Inf
00000006 00000000 00000000 00000000 00000000 00000000
Seems O.K.
Overflow threshold is V  = 3.57831709786311968119428155838269724514906882400e+80807123
7ffffff1 ffffffff ffffffff ffffffff ffffffff ffffffff
Overflow saturates at V0 = +Inf
00000002 00000000 00000000 00000000 00000000 00000000
No Overflow should be signaled for V * 1 = 3.57831709786311968119428155838269724514906882400e+80807123
7ffffff1 ffffffff ffffffff ffffffff ffffffff ffffffff
                           nor for V / 1 = 3.57831709786311968119428155838269724514906882400e+80807123
7ffffff1 ffffffff ffffffff ffffffff ffffffff ffffffff
Any overflow signal separating this * from the one
above is a DEFECT.

 unbalanced range; UfThold * V = 1.82687704666362864775460604089535377456991567872e+47
000004f1 00000001 00000000 00000000 00000000 80000000
	is too far from 1.

The number of  SERIOUS DEFECTs  discovered = 1.
The number of  DEFECTs  discovered =         1.
The number of  FLAWs  discovered =           2.

The arithmetic diagnosed has unacceptable serious defects.
END OF TEST.