X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fdocuments.git;a=blobdiff_plain;f=LiteratureNotes.tex;h=111e22043a39142089d1b38c16fa097ef79fa8d7;hp=6831428552ba9079d36d7aa84fadf3e1f073cba2;hb=a52ebd597208f180dda4f25850dd16774169812e;hpb=0f8e75393b859ea4b974948a86772b8abacebfc1
diff --git a/LiteratureNotes.tex b/LiteratureNotes.tex
index 6831428..111e220 100644
--- a/LiteratureNotes.tex
+++ b/LiteratureNotes.tex
@@ -349,6 +349,12 @@ and is implemented almost exactly by modern graphics APIs such as \texttt{OpenGL
all but guaranteed that this is the method we will be using for compositing
document elements in our project.
+{\bf Some issues with the statements made here...}
+
+When introducing Bresenham's algorithm below you say modern graphics systems ``will often use Wu's line-drawing algorithm instead, \emph{as it produces antialiased lines}'' (and don't give a citation). Here you say OpenGL uses Porter-Duff compositing ``almost exactly''. But in their introduction they say: ``
+\begin{enumerate}
+\
+
\section{Bresenham's Algorithm: Algorithm for computer control of a digital plotter \cite{bresenham1965algorithm}}
Bresenham's line drawing algorithm is a fast, high quality line rasterization
algorithm which is still the basis for most (aliased) line drawing today. The
@@ -811,6 +817,80 @@ Comparisons to other attempts:
\end{itemize}
+\section{A Multiple Precision Binary Floating Point Library With Correct Rounding \cite{fousse2007mpfr}}
+
+This is what is now the GNU MPFR C library; it has packages in debian wheezy.
+
+The library was motivated by the lack of existing arbitrary precision libraries which conformed to IEEE rounding standards.
+Examples include Mathematica, GNU MP (which this library is actually built upon), Maple (which is an exception but buggy).
+
+TODO: Read up on IEEE rounding to better understand the first section
+
+Data:
+\begin{itemize}
+ \item $(s, m, e)$ where $e$ is signed
+ \item Precision $p$ is number of bits in $m$
+ \item $\frac{1}{2} \leq m < 1$
+ \item The leading bit of the mantissa is always $1$ but it is not implied
+ \item There are no denormalised numbers
+ \item Mantissa is stored as an array of ``limbs'' (unsigned integers) as in GMP
+\end{itemize}
+
+The paper includes performance comparisons with several other libraries, and a list of literature using the MPFR (the dates indicating that the library has been used reasonably widely before this paper was published).
+
+\section{Lecture Notes on the Status of IEEE Standard 754 for Binary Floating-Point Arithmetic \cite{kahan1996ieee754}}
+
+11 years after the IEEE 754 standard becomes official, Kahan discusses various misunderstood features of the standard and laments at the failure of compilers and microprocessors to conform to some of these.
+
+I am not sure how relevant these complaints are today, but it makes for interesting reading as Kahan is clearly very passionate about the need to conform \emph{exactly} to IEEE 754.
+
+Issues considered are: Rounding rules, Exception handling and NaNs (eg: The payload of NaNs is not used in any software Kahan is aware of), Bugs in compilers (mostly Fortran) where an expression contains floats of different precisions (the compiler may attempt to optimise an expression resulting in a failure to round a double to a single), Infinity (which is unsupported by many compilers though it is supported in hardware)...
+
+
+An example is this Fortran compiler ``nasty bug'' where the compiler replaces $s$ with $x$ in line 4 and thus a rounding operation is lost.
+\begin{lstlisting}[language=Fortran, basicstyle=\ttfamily]
+ real(8) :: x, y % double precision (or extended as real(12))
+ real(4) :: s, t % single precision
+ s = x % s should be rounded
+ t = (s - y) / (...) % Compiler incorrectly replaces s with x in this line
+\end{lstlisting}
+
+\subsection{The Baleful Influence of Benchmarks \cite{kahan1996ieee754} pg 20}
+
+This section discusses the tendency to rate hardware (or software) on their speed performance and neglect accuracy.
+
+Is this complaint still relevant now when we consider the eagerness to perform calculations on the GPU?
+ie: Doing the coordinate transforms on the GPU is faster, but less accurate (see our program).
+
+Benchmarks need to be well designed when considering accuracy; how do we know an inaccurate computer hasn't gotten the right answer for a benchmark by accident?
+
+A proposed benchmark for determining the worst case rounding error is given. This is based around computing the roots to a quadratic equation.
+A quick scan of the source code for paranoia does not reveal such a test.
+
+As we needed benchmarks for CPUs perhaps we need benchmarks for GPUs. The GPU Paranoia paper\cite{hillesland2004paranoia} is the only one I have found so far.
+
+\section{Prof W. Kahan's Web Pages \cite{kahanweb}}
+
+William Kahan, architect of the IEEE 754-1985 standard, creator of the program ``paranoia'', the ``Kahan Summation Algorithm'' and contributor to the revised standard.
+
+Kahan's web page has more examples of errors in floating point arithmetic (and places where things have not conformed to the IEEE 754 standard) than you can poke a stick at.
+
+Wikipedia's description is pretty accurate: ``He is an outspoken advocate of better education of the general computing population about floating-point issues, and regularly denounces decisions in the design of computers and programming languages that may impair good floating-point computations.''
+
+Kahan's articles are written with almost religious zeal but they are backed up by examples and results, a couple of which I have confirmed.\footnote{One that doesn't work is an example of wierd arithmetic in Excel 2000 when repeated in LibreOffice Calc 4.1.5.3} This is the unpublished work. I haven't read any of the published papers yet.
+
+The articles are filled sporadically with lamentation for the decline of experts in numerical analysis (and error) which is somewhat ironic; if there were no IEEE 754 standard meaning any man/woman and his/her dog could write floating point arithmetic and expect it to produce platform independent results\footnote{Even if, as Kahan's articles often point out, platforms aren't actually following IEEE 754} this decline would probably not have happened.
+
+These examples would be of real value if the topic of the project were on accuracy of numerical operations. They also explain some of the more bizarre features of IEEE 754 (in a manner attacking those who dismiss these features as being too bizarre to care about of course).
+
+It's somewhat surprising he hasn't written anything (that I could see from scanning the list) about the lack of IEEE in PDF/PostScript (until Adobe Reader 6) and further that the precision is only binary32.
+
+I kind of feel really guilty saying this, but since our aim is to obtain arbitrary scaling, it will be inevitable that we break from the IEEE 754 standard. Or at least, I (Sam) will. Probably. Also there is no way I will have time to read and understand the thousands of pages that Kahan has written.
+
+Therefore we might end up doing some things Kahan would not approve of.
+
+Still this is a very valuable reference to go in the overview of floating point arithmetic section.
+
\chapter{General Notes}
\section{The DOM Model}