[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: sqrt and divide



Dear all,


I fully agree with Dan. Furthermore, with some care in designing the 
algorithms, correct rounding of divide and sqrt comes for almost free. There 
are two major classes of algorithms for these operations: SRT (or 
digit-recurrence, mainly hardware-oriented)  algorithms, and variants (mainly 
software-oriented) of the Newton-Raphson iteration:

- with SRT algorithms, since your remainder is exactly computed at each 
iteration, rounding the final result is straightforward. Moreover, it can be 
done on-the-fly with the iterations, so that there is no additional delay (see 
the paper by Ercegovac and Lang "On-the-Fly Rounding", IEEE Trans Computers, 
Volume 41 ,  Issue 12, 1992)

- with Newton-Raphson algorithms, if an FMA instruction is available, correct 
rounding is easily obtained, at the reasonable cost of an additional correction 
iteration (see for instance M. Cornea, R. A. Golliver, and P. Markstein. 
"Correctness proofs outline for Newton–Raphson-based floating-point divide and 
square root algorithms",  Proceedings of the 14th IEEE Symposium on Computer 
Arithmetic (Adelaide, Australia), pages 96–105, April 1999).

There can be debate about whether correctly rounding more complex operations, 
but operations as basic as divide and square root must be correctly rounded: 
this greatly facilitates portability of numerical programs, and this is 
implementable without significant overhead. If you want to give to your 
colleagues an idea of the total mess there was before IEEE 754 specified 
roundings and other important features (such as the handling of exceptional 
cases), just have a look on Kahan's paper "why we needed a floating-point 
standard" (http://www.eecs.berkeley.edu/~wkahan/ieee754status/why-ieee.pdf). By 
the way, on Kahan's web page (http://www.eecs.berkeley.edu/~wkahan/), many 
other papers might interest your colleagues.

Regards

Jean-Michel


Le 25 août 2010 à 02:05, Dan Zuras IEEE a écrit :

Subject: sqrt and divide
From: Ian Ollmann <iano@xxxxxxxxx>
Date: Tue, 24 Aug 2010 15:06:49 -0700
To: stds-754@xxxxxxxxxxxxxxxxx

There is internal debate among the OpenCL designers as to
whether or not to make the default sqrt() and divide "/"
operators in OpenCL correctly rounded or not.   I expect
that the correctly-rounded-by-default side is likely lose
this debate and special correctly rounded versions of these
(e.g.  div_rte() and sqrt_rtp() ) would be added to cover
this need instead.  (It is unclear whether all rounding
modes would be provided or just default.)   The default
operators would continue as they are at less than 2.5 and
3.0 ulps, respectively. 

I am writing to solicit expert feedback on the advisability
of this course of action.   What are the reasons the 1985
spec includes these operations among the set of basic
operations?  If an OpenCL designer responds "but developers
aren't asking for it" or "I don't want to take the 1000x
speed hit for it", how would you advise him to proceed?  


Best Regards,

Ian Ollmann


      Ian,

      Your fears about these functions are unfounded.

      You can't use the argument that developers aren't
      asking for it because (1) they aren't aware of it
      because (2) none of them have seen it happen in
      longer than most of their careers.

      What was controversial in the late 70s it now
      easy to do & almost universal in hardware.  For
      those systems that have made the mistake of not
      including them, the software fixes are not 1000x
      slower than inaccurate software.  Its more like
      tens of percent.

      The others are right.


      A big reason correctly rounded results are needed
      is reproducibility.

                      (Eric Postpischil)


      Since the point of the OpenCL standard is to promote
      heterogenus computing (or does memory fail me?) a
      default of correct rounding would promote the kind of
      portability across processors that ought to be preferred.

                      Keith Bierman


      It is easy to list well-known bugs that come from
      incorrectly rounded versions of division and square-root,
      such as computing a value of
              z = x/sqrt(x^2+y^2)
      that exceeds one, which can cause subsequent code to
      malfunction in several ways, such as trying to compute
      arcsin(z).

                      Jim Demmel


      I could make my argument as well but let me just say
      this:

      Prof Kahan once told me over dinner that the lot of
      numerical designers was a hard one.  We are never
      appreciated for our diligence.  He said that if we do
      our job extraordinarily well our reward will be that
      no one will ever notice.  For it is only when we fail
      that people notice.

      I commend the history of the 1995 Pentium bug to you
      as an example.

      Don't be noticed.

      Don't screw up.


                              Dan

--
Jean-Michel Muller, directeur de recherches CNRS
Lab. LIP, ENS Lyon, 46 allée d'Italie, 69364 Lyon Cedex 07, France
Phone (+33) 4 72728229 - Fax (+33) 4 72728806
Jean-Michel.Muller@xxxxxxxxxxx   http://perso.ens-lyon.fr/jean-michel.muller


754 | revision | FAQ | references | list archive