Re: floating point comparison

[Jan Galkowski <jan@digicomp.com>]

Matthew Heaney wrote:
> 
> I need to do some floating point comparisons in Ada 83 (but I'd like Ada 95
> advice too), and needed someone to interpret the advice in AQ&S.
> 
> My immediate problem is, How do I test 2 floating point numbers for equality?
> 
[snip]

I'm answering this question with my numerical analyst's hat donned.
The comparison of two flonums for equality needs to be done in terms
of an application-dependent criterion for equality.  Generally, in a 
strongly typed language like Ada, that means the criterion should vary
from subtype to subtype and perhaps the variation should be even finer than
that.  Thus, while the precision of a hypothetical navigation package may
be a maximum of 3 meters (with precision increasing as distance goes smaller),
some times the comparison that makes sense may be 5 meters and sometimes it
may be 100 meters.  With statistical quantities, the comparison needs to
be made considering their inherent variability.  

> 
> Suppose I have 2 lines, and I want to make sure they aren't parallel.  How
> should I write the predicate to compare the slopes of the lines, eg
> 
> if M1 = M2 then
> 
> or
> 
> if abs (M1 - M2) <= Slope'Small
> 
>

First of all, if you are using slopes, the criterion for comparison will
necessarily be related in a nonlinear way with the slope, because slopes
vary as the tangent of the angle of attack.  The preferred way to test for
perpendicularity or being parallel is to use the inner product of the
measurement space involved -- if it is a typical graphical space, this means
the dot product.  Two lines are parallel if the absolute value of the dot 
product of unit vectors erected parallel to each of them (easily done -- 
the vector divided by its L2-norm) is one.  How close to one this needs
to get is application dependent and a little tricky.  That's because
the distance is non-linearly related to the angle between the lines.  

In practice, the absolute criterion for being parallel will depend upon
the precision of the representation for the flonums being used -- its
easy to require "digits 14" -- and the value of the cosine for the
smallest angle you'd like to resolve.  So, to continue the example
above, if one needs to resolve an angle at the Earth's center 
equivalent to a separation of 3 meters at its surface, that's
about 2.7e-5 degrees but the cosine differs from one by a tad
over 1 part in 10 trillion (1 part in 10**13).

> Honestly, the advice in the AQ&S is way over my head.  Does anyone out
> there understand it, and care to explain it?

To quote Barnes' PROGRAMMING IN ADA95, page 328 in his section on floating
point types: "But care is sometimes needed and the advice of a professional
numerical analyst should be sought when in doubt."  And, no, it isn't
any easier in C or C++: There the mess is merely more disguised.

> 
> Is there a paper or book that explains Everything You Wanted To Know About
> Floating Point Comparisons?

Yes, take an introductory course in numerical analysis.  "Numerical analysis
is a science-- computation is an art."   A couple of shortstops,
however:

  (1) The introductory chapter of the Press, Flannery, Teukolsky, and Vetterling
      NUMERICAL RECIPES usually has a section which discusses precision, representation,
      and accuracy.

  (2) Francis Scheid wrote a "Numerical Analysis" installment for the Schaum's Outline
      Series.  I don't know if it is still in print, and it is a tad out of date,
      suffering from an excessive focus upon scalar computations, but it is a good
      learning on one's own text.

  (3) The first couple of chapters of the text J.E.Dennis, Jr., R.B.Schnabel,
      NUMERICAL METHODS FOR UNCONSTRAINED OPTIMIZATION AND NONLINEAR EQUATIONS,
      has a pretty modern treatment of errors and precision, although from a 
      particular focus.

  (4) The first chapter of J.J.Dongarra, C.B.Moler, J.R.Bunch, G.W.Stewart, 
      LINPACK USERS' GUIDE (SIAM), has a good introduction to these concerns.

  (5) An older, but still good (IMO) text is Froberg, INTRODUCTION TO NUMERICAL
      ANALYSIS, Addison-Wesley Publishing, 1969, LCC Card No. 73-79592.

  (6) The arguably best treatment I have seen was by L.Fox, D.F.Mayers in their
      COMPUTING METHODS FOR SCIENTISTS AND ENGINEERS, Clarendon Press, Oxford,
      1968, in its first chapter.

  (7) There may be something published about numerics in Ada-- There was or is
      a working group which studied or studies Ada's numerics.  So there may
      be direct advice available.  

I recall taking a course in Ada a long time ago where they offered the opinion --
with which I happen to agree -- that starting with numbers in the teaching
of programming languages is a mistake.  That is, at least in part -- and this is
my own opinion, not that of those teachers -- because numbers beyond integers
are a lot more complicated than they look.  Ada83's model numbers were a very
good simplification of matters, but noone seemed to understand even those,
particularly commercial compiler writers.  


[snip]

> 
> --------------------------------------------------------------------
> Matthew Heaney
> Software Development Consultant
> <mailto:matthew_heaney@acm.org>
> (818) 985-1271

-- 
 Jan Theodore Galkowski, 
 developer, statistician,

  speaking only for myself,
  
  jan@digicomp.com 
  jtgalkowski@worldnet.att.net

  Member, 

    the American Statistical Association,
    the Union of Concerned Scientists.