Tidy up a bit
[ipdf/sam.git] / chapters / Background.tex
index 87d18ce..ee8da21 100644 (file)
@@ -4,55 +4,40 @@ The first half of this chapter will be devoted to documents themselves, includin
 
 We will find that although there has been a great deal of research into the rendering, storing, editing, manipulation, and extension of document formats, modern standards are content to specify at best single precision IEEE-754 floating point arithmetic.
 
-The research on arbitrary precision arithmetic applied to documents is very sparse; however arbitrary precision arithmetic itself is a very active field of research. Therefore, the second half of this chapter will be devoted to considering fixed precision floating point numbers as specified by the IEEE-754 standard, possible limitations in precision, and alternative number representations for increased or arbitrary precision arithmetic.
+The research on arbitrary precision arithmetic applied to documents is rather sparse; however arbitrary precision arithmetic itself is a very active field of research. Therefore, the second half of this chapter will be devoted to considering fixed precision floating point numbers as specified by the IEEE-754 standard, possible limitations in precision, and alternative number representations for increased or arbitrary precision arithmetic.
 
 In Chapter \ref{Progress}, we will discuss our findings so far with regards to arbitrary precision arithmetic applied to document formats, and expand upon the goals outlined in Chapture \ref{Proposal}.
 
 \section{Raster and Vector Images}\label{Raster and Vector Images}
 \input{chapters/Background_Raster-vs-Vector}
 
-\section{Rasterising Vector Images}\label{Rasterising Vector Images}
+\section{Rendering Vector Images}\label{Rasterising Vector Images}
 
-Throughout Section \ref{vector-vs-raster-graphics} we were careful to refer to ``modern'' display devices, which are raster based. It is of some historical significance that vector display devices were popular during the 70s and 80s, and papers oriented towards drawing on these devices can be found\cite{brassel1979analgorithm}. Whilst curves can be drawn at high resolution on vector displays, a major disadvantage was shading; by the early 90s the vast majority of computer displays were raster based\cite{computergraphics2}.
+Hearn and Baker's textbook ``Computer Graphics''\cite{computergraphics2} gives a comprehensive overview of graphics from physical display technologies through fundamental drawing algorithms to popular graphics APIs. This section will examine algorithms for drawing two dimensional geometric primitives on raster displays as discussed in ``Computer Graphics'' and the relevant literature. This section is by no means a comprehensive survey of the literature but intends to provide some idea of the computations which are required to render a document.
 
-Hearn and Baker's textbook ``Computer Graphics''\cite{computergraphics2} gives a comprehensive overview of graphics from physical display technologies through fundamental drawing algorithms to popular graphics APIs. This section will examine algorithms for drawing two dimensional geometric primitives on raster displays as discussed in ``Computer Graphics'' and the relevant literature. Informal tutorials are abundant on the internet\cite{elias2000graphics}. This section is by no means a comprehensive survey of the literature but intends to provide some idea of the computations which are required to render a document.
+It is of some historical significance that vector display devices were popular during the 70s and 80s, and papers oriented towards drawing on these devices can be found\cite{brassel1979analgorithm}. Whilst curves can be drawn at high resolution on vector displays, a major disadvantage was shading; by the early 90s the vast majority of computer displays were raster based\cite{computergraphics2}.
 
-\subsection{Straight Lines}\label{Straight Lines}
+\subsection{Straight Lines}\label{Rasterising Straight Lines}
 \input{chapters/Background_Lines}
 
-\subsection{Spline Curves}\label{Spline Curves}
-
-Splines are continuous curves formed from piecewise polynomial segments. A polynomial of $n$th degree is defined by $n$ constants $\{a_0, a_1, ... a_n\}$ and:
-\begin{align}
-       y(x) &= \displaystyle\sum_{k=0}^n a_k x^k
-\end{align}
-
-
-A straight line is simply a polynomial of $0$th degree. Splines may be rasterised by sampling of $y(x)$ at a number of points $x_i$ and rendering straight lines between  $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$ as discussed in Section \ref{Straight Lines}. More direct algorithms for drawing splines based upon Brasenham and Wu's algorithms also exist\cite{citationneeded}.
-
-There are many different ways to define a spline. One approach is to specify ``knots'' on the spline and solve for the cooefficients to generate a cubic spline ($n = 3$) passing through the points. Alternatively, special polynomials may be defined using ``control'' points which themselves are not part of the curve; these are convenient for graphical based editors. Bezier splines are the most straight forward way to define a curve in the standards considered in Section \ref{Document Representations}
-\subsubsection{Bezier Curves}
-\input{chapters/Background_Bezier}
-
-\subsection{Font Rendering}
-
-Donald Knuth's 1986 textbook ``Metafont'' blargh
-
+\subsection{Spline Curves and B{\'e}ziers}\label{Spline Curves}
+\input{chapters/Background_Spline}
 
+\subsection{Font Glyphs}\label{Font Rendering}
+\input{chapters/Background_Fonts}
 
-\subsection{Shading}
+%\subsection{Shading}\label{Shading}
 
-Algorithms for shading on vector displays involved drawing equally spaced lines in the region with endpoints defined by the boundaries of the region\cite{brassel1979analgorithm}. Apart from being unrealistic, these techniques required a computationally expensive sorting of vertices\cite{lane1983analgorithm}.
 
-On raster displays, shading is typically based upon Lane's algorithm of 1983\cite{lane1983analgorithm}. Lane's algorithm relies on the ability to ``subtract'' fill from a region. This algorithm is now implemented in the GPU \rephrase{stencil buffer-y and... stuff} \cite{kilgard2012gpu}
+%\cite{brassel1979analgorithm}; %\cite{lane1983analgorithm}.
 
-\subsection{Compositing and the Painter's Model}\label{Compositing and the Painter's Model}
+\subsection{Compositing}\label{Compositing and the Painter's Model}
 
-So far we have discussed techniques for rendering vector graphics primitives in isolation, with no regard to the overall structure of a document which may contain many thousands of primitives. A straight forward approach would be to render all elements sequentially to the display, with the most recently drawn pixels overwriting lower elements. Such an approach is particularly inconvenient for anti-aliased images where colours must appear to smoothly blur between the edge of a primitive and any drawn underneath it.
+%So far we have discussed techniques for rendering vector graphics primitives in isolation, with no regard to the overall structure of a document which may contain many thousands of primitives. A straight forward approach would be to render all elements sequentially to the display, with the most recently drawn pixels overwriting lower elements. Such an approach is particularly inconvenient for anti-aliased images where colours must appear to smoothly blur between the edge of a primitive and any drawn underneath it.
 
 Colour raster displays are based on an additive red-green-blue $(r,g,b)$ colour representation which matches the human eye's response to light\cite{computergraphics2}. In 1984, Porter and Duff introduced a fourth colour channel for rasterised images called the ``alpha'' channel, analogous to the transparency of a pixel\cite{porter1984compositing}. In compositing models, elements can be rendered seperately, with the four colour channels of successively drawn elements being combined according to one of several possible operations.
 
-In the ``painter's model'' as described by the SVG standard, Porter and Duff's ``over'' operation is used when rendering one primitive over another\cite{svg2011-1.1}.
+In the ``painter's model'' as described by the SVG standard the ``over'' operation is used when rendering one primitive over another\cite{svg2011-1.1}.
 Given an existing pixel $P_1$ with colour values $(r_1, g_1, b_1, a_1)$ and a pixel $P_2$ with colours $(r_2, g_2, b_2, a_2)$ to be painted over $P_1$, the resultant pixel $P_T$ has colours given by:
 \begin{align}
        a_T &= 1 - (1-a_1)(1-a_2) \\
@@ -65,33 +50,20 @@ The PostScript and PDF standards, as well as the OpenGL API also use a painter's
 
 \subsection{Rasterisation on the CPU and GPU}
 
-Traditionally, vector graphics have been rasterized by the CPU before being sent to the GPU for drawing\cite{kilgard2012gpu}. Lots of people would like to change this \cite{worth2003xr, loop2007rendering, rice2008openvg, kilgard2012gpu, green2007improved}.
+Traditionally, vector images have been rasterized by the CPU before being sent to a specialised Graphics Processing Unit (GPU) for drawing\cite{computergraphics2}. Rasterisation of simple primitives such as lines and triangles have been supported directly by GPUs for some time through the OpenGL standard\cite{openglspec}. However complex shapes (including those based on B{\'e}zier curves such as font glyphs) must either be rasterised entirely by the CPU or decomposed into simpler primitives that the GPU itself can directly rasterise. There is a significant body of research devoted to improving the performance of rendering such primitives using the latter approach, mostly based around the OpenGL API\cite{robart2009openvg, leymarie1992fast, frisken2000adaptively, green2007improved, loop2005resolution, loop2007rendering}. Recently Mark Kilgard of the NVIDIA Corporation described an extension to OpenGL for NVIDIA GPUs capable of drawing and shading vector paths\cite{kilgard2012gpu,kilgard300programming}. From this development it seems that rasterization of vector graphics may eventually become possible upon the GPU.openglspec
 
-\rephrase{2. Here are the ways documents are structured ... we got here eventually}
+It is not entirely clear how well supported the IEEE-754 standard for floating point computation (which we will discuss in Section \ref{}) is amongst GPUs\footnote{Informal technical articles are prevelant on the internet --- Eg: Regarding the Dolphin Wii GPU Emulator: \url{https://dolphin-emu.org/blog} (accessed 2014-05-22)}. Although the OpenGL API does use IEEE-754 number representations, research by Hillesland and Lastra in 2004 suggested that many GPUs were not internally compliant with the standard\cite{hillesland2004paranoia}. %Arbitrary precision arithmetic, is provided by many software libraries for CPU based calculations
 
+ \pagebreak
 \section{Document Representations}\label{Document Representations}
 
-The representation of information, particularly for scientific purposes, has changed dramatically over the last few decades. For example, Brassel's 1979 paper referenced earlier has been produced on a mechanical type writer. Although the paper discusses an algorithm for shading on computer displays, the figures illustrating this algorithm have not been generated by a computer, but drawn by Brassel's assistant\cite{brassel1979analgorithm}. In contrast, modern papers such as Barnes et. al's recent paper on embedding 3d images in PDF documents\cite{barnes2013embeddding} can themselves be an interactive proof of concept.
+The representation of information, particularly for scientific purposes, has changed dramatically over the last few decades. For example, Brassel's 1979 paper referenced earlier\cite{brassel1979analgorithm} has been produced on a mechanical type writer. Although the paper discusses an algorithm for shading on computer displays, the figures illustrating this algorithm have not been generated by a computer, but drawn by Brassel's assistant. In contrast, modern papers such as Barnes et. al's 2013 paper on embedding 3d images in PDF documents\cite{barnes2013embedding} can themselves be an interactive proof of concept.
 
-In this section we will consider various approaches and motivations to specifying the structure and appearance of a document, including: early interpreted formats (PostScript, \TeX, DVI), the Document Object Model popular in standards for web based documents (HTML, SVG), and Adobe's ubiquitous Portable Document Format (PDF). Some of these formats were discussed in a recent paper ``Pixels Or Perish'' by Hayes\cite{hayes2012pixelsor} who argues for greater interactivity in the PDF standard.
-
-\subsection{Interpreted Document Formats}
-\input{chapters/Background_Interpreted}
+Haye's 2012 article ``Pixels or Perish'' discusses the recent history and current state of the art in documents for scientific publications\cite{hayes2012pixels}. Hayes argued that there are currently two different approaches to representing a document: As a sequence of static sheets of paper (Programmed Documents) or as a dynamic and interactive way to convey information, using the Document Object Model. We will now explore these two approaches and the extent to which they overlap.
 
 
-\begin{itemize}
-       \item This model treats a document as the source code program which produces graphics
-       \item Arose from the desire to produce printed documents using computers (which were still limited to text only displays).
-       \item Typed by hand or (later) generated by a GUI program
-       \item PostScript --- largely supersceded by PDF on the desktop but still used by printers\footnote{Desktop pdf viewers can still cope with PS, but I wonder if a smartphone pdf viewer would implement it?}
-       \item \TeX --- Predates PostScript, similar idea
-       \begin{itemize}
-               \item Maybe if \LaTeX were more popular there would be desktop viewers that converted \LaTeX directly into graphics
-       \end{itemize}
-       \item Potential for dynamic content, interactivity; dynamic PostScript, enhanced Postscript
-
-       \item Problems with security --- Turing complete, can be exploited easily
-\end{itemize}
+\subsection{Programmed Documents}
+\input{chapters/Background_Interpreted}
 
 \pagebreak
 \subsection{Document Object Model}\label{Document Object Model}
@@ -99,71 +71,71 @@ In this section we will consider various approaches and motivations to specifyin
 
 \subsection{The Portable Document Format}
 
+Adobe's Portable Document Format (PDF) is currently used almost universally for sharing documents; the ability to export or print to PDF can be found in most graphical document editors and even some plain text editors\cite{cheng2002finally}. 
 
-\subsection{Scientific Computation Packages}
-
-The document and the code that produces it are one and the same.
-
-\begin{itemize}
-       \item Numerical computation packages such as Mathematica and Maple use arbitrary precision floats
-       \begin{itemize}
-               \item Mathematica is not open source which is an issue when publishing scientific research (because people who do not fork out money for Mathematica cannot verify results)
-               \item What about Maple? \cite{HFP} and \cite{fousse2007mpfr} both mention it being buggy. 
-               \item Octave and Matlab use fixed precision doubles
-       \end{itemize}
-       \item IPython is pretty cool guys
-\end{itemize}
-
-\section{Precision in Modern Document Formats}
-
-We briefly summarise the requirements of the standards discussed so far in regards to the precision of mathematical operations:
-\begin{itemize}
-       \item {\bf PostScript} predates the IEEE-754 standard and originally specified a floating point representation with ? bits of exponent and ? bits of mantissa. Version ? of the PostScript standard changed to specify IEEE-754 binary32 ``single precision'' floats.
-       \item {\bf PDF} has also specified IEEE-754 binary32 since version ?. Importantly, the standard states that this is a \emph{maximum} precision; documents created with higher precision would not be viewable in Adobe Reader.
-       \item {\bf SVG} specifies a minimum of IEEE-754 binary32 but recommends more bits be used internally
-       \item {\bf Javascript} uses binary32 floats for all operations, and does not distinguish between integers and floats.   
-       \item {\bf Python} uses binary64 floats
-       \item {\bf Matlab} uses binary64 floats
-       \item {\bf Mathematica} uses some kind of terrifying symbolic / arbitrary float combination
-       \item {\bf Maple} is similar but by many accounts horribly broken
-       
-\end{itemize}
+Hayes describes PDF as ``... essentially 'flattened' PostScript; it’s what’s left when you remove all the procedures and loops in a program, replacing them with sequences of simple drawing commands.''\cite{hayes2012pixels}. Consultation of the PDF 1.7 standard shows that this statement does not a give a complete picture --- despite being based on the Adobe PostScript model of a document as a series of ``pages'' to be printed by executing sequential instructions, from version 1.5 the PDF standard began to borrow some ideas from the Document Object Model. For example, interactive elements such as forms may be included as XHTML objects and styled using CSS. ``Actions'' are objects used to modify the data structure dynamically. In particular, it is possible to include Javascript Actions. Adobe defines the API for Javascript actions seperately to the PDF standard\cite{js_3d_pdf}. There is some evidence in the literature of attempts to exploit these features, with mixed success\cite{barnes2013embedding, hayes2012pixels}.
+
+%\subsection{Scientific Computation Packages}
+
+
+\section{Precision required by Document Formats}
 
+We briefly summarise the requirements of the standards discussed so far in regards to the precision of mathematical operations.
 
-\rephrase{4. Here is IEEE-754 which is what these standards use}
+\subsection{PostScript}
+The PostScript reference describes a ``Real'' object for representing coordinates and values as follows: ``Real objects approximate mathematical real numbers within a much larger interval, but with limited precision; they are implemented as floating-point numbers''\cite{plrm}. There is no reference to the precision of mathematical operations, but the implementation limits \emph{suggest} a range of $\pm10^{38}$ ``approximate'' and the smallest values not rounded to zero are $\pm10^{-38}$ ``approximate''.
 
-\section{Real Number Representations}
+\subsection{PDF}
+PDF defines ``Real'' objects in a similar way to PostScript, but suggests a range of $\pm3.403\times10^{38}$ and smallest non-zero values of $\pm1.175\times10^{38}$\cite{pdfref17}. A note in the PDF 1.7 manual mentions that Acrobat 6 now uses IEEE-754 single precision floats, but ``previous versions used 32-bit fixed point numbers'' and ``... Acrobat 6 still converts floating-point numbers to fixed point for some components''.
 
-We have found that PostScript, PDF, and SVG document standards all restrict themselves to IEEE floating point number representations of coordinates. This is unsurprising as the IEEE standard has been successfully adopted almost universally by hardware manufactures and programming language standards since the early 1990s. In the traditional view of a document as a static, finite sheet of paper, there is little motivation for enhanced precision.
+\subsection{\TeX and METAFONT}
 
-In this section we will begin by investigating floating point numbers as defined in the IEEE standard and their limitations. We will then consider alternative number representations including fixed point numbers, arbitrary precision floats, rational numbers, p-adic numbers and symbolic representations. \rephrase{Oh god I am still writing about IEEE floats let alone all those other things}
+In ``The METAFONT book'' Knuth appears to describe coordinates as fixed point numbers: ``The computer works internally with coordinates that are integer multiples of $\frac{1}{65536} \approx 0.00002$ of the width of a pixel''\cite{knuth1983metafont}. There is no mention of precision in ``The \TeX book''. In 2007 Beebe claimed that {\TeX} uses a $14.16$ fixed point encoding, and that this was due to the lack of standardised floating point arithmetic on computers at the time; a problem that the IEEE-754 was designed to solve\cite{beebe2007extending}. Beebe also suggests that \TeX and METAFONT could now be modified to use IEEE-754 arithmetic.
 
-\rephrase{Reorder to start with Integers, General Floats, then go to IEEE, then other things}
+\subsection{SVG}
 
-\subsection{IEEE Floating Points}
+The SVG standard specifies a minimum precision equivelant to that of ``single precision floats'' (presumably referring to IEEE-754) with a range of \verb/-3.4e+38F/ to \verb/+3.4e+38F/, and states ``It is recommended that higher precision floating point storage and computation be performed on operations such as
+coordinate system transformations to provide the best possible precision and to prevent round-off errors.''\cite{svg2011-1.1} An SVG Viewer may refer to itself as ``High Quality'' if it uses a minimum of ``double precision'' floats.
 
-Although the concept of a floating point representation has been attributed to various early computer scientists including Charles Babbage\cite{citationneeded}, it is widely accepted that William Kahan and his colleagues working on the IEEE-754 standard in the 1980s are the ``fathers of modern floating point computation''\cite{citationneeded}. The original IEEE-754 standard specified the encoding, number of bits, rounding methods, and maximum acceptable errors for the basic floating point operations for base $B = 2$ floats. It also specifies ``exceptions'' --- mechanisms by which a program can detect an error such as division by zero\footnote{Kahan has argued that exceptions in IEEE-754 are conceptually different to Exceptions as defined in several programming languages including C++ and Java. An IEEE exception is intended to prevent an error by its detection, whilst an exception in those languages is used to indicate an error has already occurred\cite{}}. We will restrict ourselves to considering $B = 2$, since it was found that this base in general gives the smallest rounding errors\cite{HFP}, although it is worth noting that different choices of base had been used historically\cite{goldman1991whatevery}, and the IEEE-854 and later the revised IEEE-754 standard specify a decimal representation $B = 10$ intended for use in financial applications.
+\subsection{Javascript}
+We include Javascript here due to its relation with the SVG, HTML5 and PDF standards.
+
+According to the EMCA-262 standard, ``The Number type has exactly 18437736874454810627 (that is, $2^64-^53+3$) values, 
+representing the double-precision 64-bit format IEEE 754 values as specified in the IEEE Standard for Binary Floating-Point Arithmetic''\cite{ecma-262}. 
+The Number type does differ slightly from IEEE-754 in that there is only a single valid representation of ``Not a Number'' (NaN). The EMCA-262 does not define an ``integer'' representation.
+       
+
+\section{Number Representations}
+
+
+\subsection{Integers and Fixed Point Numbers}
 
-\subsection{Floating Point Definition}
 
-A floating point number $x$ is commonly represented by a tuple of integers $(s, e, m)$ in base $B$ as\cite{HFP, ieee2008-754}:
+
+\subsection{Floating Points}
+
+A floating point number $x$ is commonly represented by a tuple of values $(s, e, m)$ in base $B$ as\cite{HFP, ieee2008-754}:
 
 \begin{align*}
        x &= (-1)^{s} \times m \times B^{e}
 \end{align*}
 
-Where $s$ is the sign and may be zero or one, $m$ is commonly called the ``mantissa'' and $e$ is the exponent.
-The name ``floating point'' refers to the equivelance of the $\times B^e$ operation to a shifting of a decimal point along the mantissa. This contrasts with a ``fixed point'' representation where $x$ is the sum of two fixed size numbers representing the integer and fractional part.
+Where $s$ is the sign and may be zero or one, $m$ is commonly called the ``mantissa'' and $e$ is the exponent. Whilst $e$ is an integer in some range $\pm e_max$, the mantissa $m$ is actually a fixed point value in the range $0 < m < B$. The name ``floating point'' refers to the equivelance of the $\times B^e$ operation to a shifting of the ``fixed point'' along the mantissa.
 
-In the IEEE-754 standard, for a base of $B = 2$, numbers are encoded in continuous memory by a fixed number of bits, with $s$ occupying 1 bit, followed by $e$ and $m$ occupying a number of bits specified by the precision; 5 and 10 for a binary16 or ``half precision'' float, 8 and 23 for a binary32 or ``single precision'' and 15 and 52 for a binary64 or ``double precision'' float\cite{HFP, ieee2008-754}.
+For example, the value $7.25$ can be expressed as:
+\begin{enumerate}
+       \item 
+       
+\end{enumerate}
 
+The choice of base $B = 2$, closely matches the nature of modern hardware. It has also been found that this base in general gives the smallest rounding errors\cite{HFP}. Early computers had in fact used a variety of representations including $B=3$ or even $B=7$\cite{goldman1991whatevery}, and the revised IEEE-754 standard specifies a decimal representation $B = 10$ intended for use in financial applications\cite{ieee754std2008}. From now on we will restrict ourselves to considering base 2 floats.
 
-\subsection{Precision and Rounding}
+Figure \ref{minifloat.pdf} shows the positive real numbers which can be represented exactly by an 8 bit floating point number encoded in the IEEE-754 format, and the distance between successive floating point numbers. We show two encodings using (1,2,5) and (1,3,4) bits to encode (sign, exponent, mantissa) respectively.
 
-Real values which cannot be represented exactly in a floating point representation must be rounded. The results of a floating point operation will in general be such values and thus there is a rounding error possible in any floating point operation. Goldberg's assertively titled 1991 paper ``What Every Computer Scientist Needs to Know about Floating Point Arithmetic'' provides a comprehensive overview of issues in floating point arithmetic and relates these to the 1984 version of the IEEE-754 standard\cite{goldberg1991whatevery}. More recently, after the release of the revised IEEE-754 standard in 2008, a textbook ``Handbook Of Floating Point Arithmetic'' has been published which provides a thourough review of literature relating to floating point arithmetic in both software and hardware\cite{HFP}.
+For each distinct value of the exponent, the successive floating point representations lie on a straight line with constant slope. As the exponent increases, larger values are represented, but the distance between successive values increases\footnote{A plot of fixed point numbers or integers (which we omit for space considerations) would show points lying on a straight line with a constant slope between points}.
 
+In the graph of the difference between representations, a single isolated point should be visible; this is not an error, but due to the greater discontinuity between the denormalised and normalised values ($e = 0$ and $1$ respectively). 
 
-Figure \ref{minifloat.pdf} shows the positive real numbers which can be represented exactly by an 8 bit base $B = 2$ floating point number; and illustrates that a set of fixed precision floating point numbers forms a discrete approximation of the reals. There are only $2^7 = 256$ numbers in this set, which means it is easier to see some of the properties of floats that would be unclear using one of the IEEE-754 encodings. The first set of points corresponds to using 2 and 5 bits to encode $e$ and $m$ whilst the second set of points corresponds to a 3 and 4 bit encoding. This allows us to see the trade off between the precision and range of real values represented. 
 
 \begin{figure}[H]
        \centering
@@ -174,45 +146,20 @@ Figure \ref{minifloat.pdf} shows the positive real numbers which can be represen
 
 \subsection{Floating Point Operations}
 
-Floating point operations can in principle be performed using integer operations, but specialised Floating Point Units (FPUs) are an almost universal component of modern processors\cite{citationneeded}. The improvement of FPUs remains highly active in several areas including: efficiency\cite{seidel2001onthe}; accuracy of operations\cite{dieter2007lowcost}; and even the adaptation of algorithms originally used in software for reducing the overal error of a sequence of operations\cite{kadric2013accurate}. In this section we will consider the algorithms for floating point operations without focusing on the hardware implementation of these algorithms.
-
+Floating point operations can in principle be performed using integer operations, but specialised Floating Point Units (FPUs) are an almost universal component of modern processors\cite{kelley1997acmos}. The improvement of FPUs remains highly active in several areas including: efficiency\cite{seidel2001onthe}; accuracy of operations\cite{dieter2007lowcost}; and even the adaptation of algorithms originally used in software for reducing the overal error of a sequence of operations\cite{kadric2013accurate}. In this section we will briefly describe the algorithms for floating point operations without focusing on the hardware implementation of these algorithms.
 
-\subsection{Some sort of Example(s) or Floating Point Mayhem}
 
-\rephrase{Eg: $f(x) = |x|$ calculated from sqrt and squaring}
+\subsection{Precision and Rounding} 
 
-\rephrase{Eg: Massive rounding errors from calculatepi}
+Real values which cannot be represented exactly in a floating point representation must be rounded to the nearest floating point value. The results of a floating point operation will in general be such values and thus there is a rounding error possible in any floating point operation. Referring to Figure \ref{minifloat.pdf} it can be seen that the largest possible rounding error, or ``units in last place'' (ulp) is half the distance between successive floats; this means that rounding errors increase as the value to be represented increases. The IEEE-754 standard specifies the rounding conventions for floating point arithmetic\cite{ieee754std2008}.
 
-\rephrase{Eg: Actual graphics things :S}
 
+Goldberg's assertively titled 1991 paper ``What Every Computer Scientist Needs to Know about Floating Point Arithmetic''\cite{goldberg1991whatevery} provides a comprehensive overview of issues in floating point arithmetic and relates these to requirements of the IEEE-754 1985 standard\cite{ieee754std1985}. More recently, after the release of the revised IEEE-754 standard in 2008\cite{ieee754std2008}, a textbook ``Handbook Of Floating Point Arithmetic'' has been published which provides a thourough review of literature relating to floating point arithmetic in both software and hardware\cite{HFP}.
 
-\subsection{Limitations Imposed By Graphics APIs and/or GPUs}
-
-Traditionally algorithms for drawing vector graphics are performed on the CPU; the image is rasterised and then sent to the GPU for rendering\cite{}. Recently there has been a great deal of literature relating to implementation of algorithms such as bezier curve rendering\cite{} or shading\cite{} on the GPU. As it seems the trend is to move towards GPU 
-
-\rephrase{6. Here are ways GPU might not be IEEE-754 --- This goes *somewhere* in here but not sure yet}
-
-\begin{itemize}
-       \item Internal representations are GPU dependent and may not match IEEE\cite{hillesland2004paranoia}
-       \item OpenGL standards specify: binary16, binary32, binary64
-       \item OpenVG aims to become a standard API for SVG viewers but the API only uses binary32 and hardware implementations may use less than this internally\cite{rice2008openvg}
-       \item It seems that IEEE has not been entirely successful; although all modern CPUs and GPUs are able to read and write IEEE floating point types, many do not conform to the IEEE standard in how they represent floating point numbers internally. 
-       \item \rephrase{Blog post alert} \url{https://dolphin-emu.org/blog/2014/03/15/pixel-processing-problems/}
-\end{itemize}
-
-
-
-\rephrase{7. Sod all that, let's just use an arbitrary precision library (AND THUS WE FINALLY GET TO THE POINT)}
+William Kahan, one of the architects of the IEEE-754 standard in 1984 and a contributor to its revision in 2010, has also published many articles on his website explaining the more obscure features of the IEEE-754 standard and calling out software which fails to conform to the standard\footnote{In addition to encodings and acceptable rounding errors, the standard also specifies ``exceptions'' --- mechanisms by which a program can detect an error such as division by zero --- which are sometimes neglected, as in the ECMA-256}\cite{kahanweb, kahan1996ieee754}, as well as examples of the limitations of floating point computations\cite{kahan2007wrong}. 
 
 \subsection{Arbitrary Precision Floating Point Numbers}
 
-An arbitrary precision floating point number simply uses extra bits to store extra precision. Do it all using MFPR\cite{fousse2007mpfr}, she'll be right.
-
-\rephrase{8. Here is a brilliant summary of sections 7- above}
-
-Dear reader, thankyou for your persistance in reading this mangled excuse for a Literature Review.
-Hopefully we have brought together the radically different areas of interest together in some sort of coherant fashion.
-In the next chapter we will talk about how we have succeeded in rendering a rectangle. It will be fun. I am looking forward to it.
+Fouse described 
 
-\rephrase{Oh dear this is not going well}
 

UCC git Repository :: git.ucc.asn.au