Re: sqrt and divide
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.
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
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?
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
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.
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
I could make my argument as well but let me just say
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.
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