TEAM-ADA Archives

Team Ada: Ada Programming Language Advocacy

TEAM-ADA@LISTSERV.ACM.ORG

Options: Use Forum View

Use Proportional Font
Show Text Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Subject:
From:
Lamar Harris <[log in to unmask]>
Reply To:
Lamar Harris <[log in to unmask]>
Date:
Wed, 12 Feb 1997 10:57:05 -0400
Content-Type:
text/plain
Parts/Attachments:
text/plain (180 lines)
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 run-time 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 13441-4505
  / /\_| |\_// /\___/ / / "Mind is the Software for the Hardware Called Brain"
 / / / | || / / /  / / / E-Mail: [log in to unmask] (Home: [log in to unmask])
/_/ /  |_||/_/ /  /_/ / Phone : 315-330-4266 (DSN 587-4266)
\_\/   \_\|\_\/   \_\/ Fax   : 315-330-7989 (DSN 587-7989)

ATOM RSS1 RSS2