To All,
I apolgize in advance for the length of this message, but the problem I've
encountered is rather subtle and the code and sample run to demonstrate the
error are rather lengthy even though I've tried to shorten them.
I've been working on the Traveling Salesman Problem using GNAT 3.09 for
Solaris 2.4 on a Sun Sparc Ultra 1. While working on TSP, I've encountered a
strange runtime problem (error, phenomenom??) with floating point numbers.
I was wondering if anyone out there has had a similar experience, has an
idea as to what's going on, or has any advice as to how to fix it. Here goes...
In my program, I generate a random set of points whose X and Y coordinates
are within the range 0.0 to 1.0. I then find an ordering of these points
using two different methods. One method is to search through all possible
permutations and return the permutation with the shortest path length. The
other method I will not discuss as I intend to publish the results (sorry).
To gather empirical evidence that my second method is valid before I launch
into a lengthy analysis of it, I compare the path length generated by the
permutation method with the path length generated by my method. Here's where
the fun began.
I first developed this program in Lucid Common Lisp running on the same Sun
Ultra machine. The problem I had there was that there were small variances
in the least (15th) significant digit. I was able to set this digit to zero
and then compare the remaining 14 signifcant digits. I encountered no
further problems. To further verify my method, I rewrote it in Ada95. I
verified the individual components and then tried to test my method against
the permutation method and it almost immediately failed. I added additional
debugging output and from what I learned from that and an analysis of the
code, I've been able to reproduce the problem in the program given below.
Here's how the program below works:
1. I define my own floating point type, IO and Elementary_Functions for that
type, and a Point_Type record that uses that type to store the X and Y
coordinates of the point.
2. There are two functions. One determines the distance between two points
and the other returns a random point.
3. I then define five random points A through E.
4. I then use the Distance function to determine the path lengths for going
from point A to B to C to D to E and back to A and for going from point C to
B to A to E to D and back to C. Since these are the same closed path (just
starting at a different point and going in opposite directions), the lengths
should be the same.
5. I then print out the coordinates for the points (displaying more digits
than the type is defined for).
6. Finally, I print out the path lengths, compare the path lengths, and
print out the results of the comparison.
About four times out of five the path lengths are the same and the
comparison reports this. The other time, however, the path lengths
displayed are the same, BUT the comparison reports that the first is LONGER
than the second.
Here's the output from a run that show this behavior:
Point A: 0.6049214601516720000000000, 0.6367374658584600000000000
Point B: 0.2369488328695300000000000, 0.0501336120069027000000000
Point C: 0.5963447093963620000000000, 0.3965126872062680000000000
Point D: 0.8365010619163510000000000, 0.6842445731163020000000000
Point E: 0.2764832675457000000000000, 0.4119921326637270000000000
Path 1 Length (ABCDEA) = 2.5870557464745700000000000
Path 2 Length (CBAEDC) = 2.5870557464745700000000000
Path 1 is longer than Path 2
Note that the actual values for the path lengths are the same, but the
comparison fails.
I've also run the same program under GNAT 3.07 for DOS on an Intel 486 and
under GNAT 3.05 for Win95 on an Intel Pentium and I get the same error.
Also, occasionally the first is reported as shorter than the second.
What is causing this and how do I fix it? Please don't tell me I have to do
this all in Lisp or, Heaven forbid, C because of a fluke in Ada!
If you try this on your own, be sure to run the program at least about 10
times. It may take this many times for the error to show up.
Thanks is advance for any help with this that I receive.
Here's the source code that generated this error:
with Ada.Text_IO, Ada.Integer_Text_IO, Ada.Numerics.Float_Random;
with Ada.Numerics.Generic_Elementary_Functions;
use Ada.Text_IO, Ada.Integer_Text_IO, Ada.Numerics.Float_Random;
procedure Float_Test is
type My_Float is digits 8;
package My_Float_IO is new Ada.Text_IO.Float_IO(My_Float);
package My_Float_Functions
is new Ada.Numerics.Generic_Elementary_Functions(My_Float);
use My_Float_IO, My_Float_Functions;
type Point_Type is record
X: My_Float;
Y: My_Float;
end record;
function Distance(Point1, Point2: in Point_Type) return My_Float is
begin
return Sqrt((Point1.X  Point2.X)**2 + (Point1.Y  Point2.Y)**2);
end Distance;
Float_Generator: Ada.Numerics.Float_Random.Generator;
function Random_Point return Point_Type is
New_Point: Point_Type;
begin
New_Point.X := My_Float(Random(Float_Generator));
New_Point.Y := My_Float(Random(Float_Generator));
return New_Point;
end Random_Point;
Point_A, Point_B, Point_C, Point_D, Point_E: Point_Type;
Path_A_Length, Path_B_Length: My_Float;
begin
Reset(Float_Generator);
Point_A := Random_Point; Point_B := Random_Point;
Point_C := Random_Point; Point_D := Random_Point;
Point_E := Random_Point;
Path_A_Length
:= Distance(Point_A, Point_B)+Distance(Point_B, Point_C)+
Distance(Point_C, Point_D)+Distance(Point_D, Point_E)+
Distance(Point_E, Point_A);
Path_B_Length
:= Distance(Point_C, Point_B)+Distance(Point_B, Point_A)+
Distance(Point_A, Point_E)+Distance(Point_E, Point_D)+
Distance(Point_D, Point_C);
Put("Point A: "); Put(Point_A.X,0,25,0);Put(", "); Put(Point_A.Y,0,25,0);
New_Line;
Put("Point B: "); Put(Point_B.X,0,25,0);Put(", "); Put(Point_B.Y,0,25,0);
New_Line;
Put("Point C: "); Put(Point_C.X,0,25,0);Put(", "); Put(Point_C.Y,0,25,0);
New_Line;
Put("Point D: "); Put(Point_D.X,0,25,0);Put(", "); Put(Point_D.Y,0,25,0);
New_Line;
Put("Point E: "); Put(Point_E.X,0,25,0);Put(", "); Put(Point_E.Y,0,25,0);
New_Line(2);
Put("Path 1 Length (ABCDEA) = "); Put(Path_A_Length,0,25,0);
New_Line;
Put("Path 2 Length (CBAEDC) = "); Put(Path_B_Length,0,25,0);
New_Line;
if Path_A_Length < Path_B_Length then
Put_Line("Path 1 is shorter than Path 2");
elsif Path_A_Length > Path_B_Length then
Put_Line("Path 1 is longer than Path 2");
elsif Path_A_Length = Path_B_Length then
Put_Line("Path 1 is the same length as Path 2");
else
Put_Line("Comparison Error!");
end if;
end Float_Test;
Thanks again for helping,
______ __ __
/ ____ \ / /\ / /\ Ray Harris, 2Lt, USAF
/ /\__/ /\ / / / / / / Rome Lab/C3CA
/ /_/_/ / // /_/__/ / / 525 Brooks Rd.
/ __ _/ // _____ / / Rome, NY 134414505
/ /\_ \_// /\___/ / / "Mind is the Software for the Hardware Called Brain"
/ / /   / / / / / / EMail: [log in to unmask] (Home: [log in to unmask])
/_/ / _/_/ / /_/ / Phone : 3153304266 (DSN 5874266)
\_\/ \_\\_\/ \_\/ Fax : 3153307989 (DSN 5877989)
