X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fdocuments.git;a=blobdiff_plain;f=LiteratureNotes.tex;h=c7aae7b3ef3f0d4f1bdc4581b7ed04a57586bff2;hp=2814e4b1e37c3b0cc86e27d61ef7f80ae2639d87;hb=12e7dacee2405e1edae91fc2c78437dcaa4181f5;hpb=93cb10d1d571c39a1f7b39b88d1fba745f2e31a9 diff --git a/LiteratureNotes.tex b/LiteratureNotes.tex index 2814e4b..c7aae7b 100644 --- a/LiteratureNotes.tex +++ b/LiteratureNotes.tex @@ -18,7 +18,7 @@ \parskip 8.2pt % sets spacing between paragraphs %\renewcommand{\baselinestretch}{1.5} % Uncomment for 1.5 spacing between lines \parindent 0pt % sets leading space for paragraphs -\linespread{0.8} +\linespread{1} \newcommand{\vect}[1]{\boldsymbol{#1}} % Draw a vector @@ -37,14 +37,14 @@ \definecolor{darkred}{rgb}{0.75,0,0} \definecolor{darkblue}{rgb}{0,0,0.75} \definecolor{pink}{rgb}{1,0.5,0.5} -\lstset{language=Java} +\lstset{language=XML} \lstset{backgroundcolor=\color{darkgray}} -\lstset{numbers=left, numberstyle=\tiny, stepnumber=1, numbersep=5pt} -\lstset{keywordstyle=\color{darkred}\bfseries} -\lstset{commentstyle=\color{darkblue}} +%\lstset{numbers=left, numberstyle=\tiny, stepnumber=1, numbersep=5pt} +%\lstset{keywordstyle=\color{darkred}\bfseries} +%\lstset{commentstyle=\color{darkblue}} %\lstset{stringsyle=\color{red}} -\lstset{showstringspaces=false} -\lstset{basicstyle=\small} +%\lstset{showstringspaces=false} +%\lstset{basicstyle=\small} \newcommand{\shell}[1]{\texttt{#1}} \newcommand{\code}[1]{\texttt{#1}} @@ -578,17 +578,175 @@ There is a version for multiplication. I'm still not quite sure when this is useful. I haven't been able to find an example for $x$ and $y$ where $x + y \neq \text{Fast2Sum}(x, y)$. +\section{Handbook of Floating-Point Arithmetic \cite{HFP}} +This book is amazingly useful and pretty much says everything there is to know about Floating Point numbers. +It is much easier to read than Goldberg or Priest's papers. + +I'm going to start working through it and compile their test programs. + +\subsection{A sequence that seems to converge to a wrong limit - pgs 9-10, \cite{HFP}} + +\begin{align*} + u_n &= \left\{ \begin{array}{c} u_0 = 2 \\ u_1 = -4 \\ u_n = 111 - \frac{1130}{u_{n-1}} + \frac{3000}{u_{n-1}u_{n-2}}\end{array}\right. +\end{align*} + +The limit of the series should be $6$ but when calculated with IEEE floats it is actually $100$ +The authors show that the limit is actually $100$ for different starting values, and the error in floating point arithmetic causes the series to go to that limit instead. + +\begin{figure}[H] + \centering + \includegraphics[width=0.8\textwidth]{figures/handbook1-1.pdf} + \caption{Output of Program 1.1 from \emph{Handbook of Floating-Point Arithmetic}\cite{HFP} for various IEEE types} + \label{HFP-1-1} +\end{figure} + +\subsection{Mr Gullible and the Chaotic Bank Society pgs 10-11 \cite{HFP}} + +This is an example of a sequence involving $e$. Since $e$ cannot be represented exactly with FP, even though the sequence should go to $0$ for $a_0 = e - 1$, the representation of $a_0 \neq e - 1$ so the sequence goes to $\pm \infty$. + +To eliminate these types of problems we'd need an \emph{exact} representation of all real numbers. +For \emph{any} FP representation, regardless of precision (a finite number of digits) there will be numbers that can't be represented exactly hence you could find a similar sequence that would explode. + +IE: The more precise the representation, the slower things go wrong, but they still go wrong, {\bf even with errorless operations}. + + +\subsection{Rump's example pg 12 \cite {HFP}} + +This is an example where the calculation of a function $f(a,b)$ is not only totally wrong, it gives completely different results depending on the CPU. Despite the CPU conforming to IEEE. + +\section{Scalable Vector Graphics (SVG) 1.1 (Second Edition) \cite{svg2011-1.1}} + +Scalable Vector Graphics (SVG) is a XML language for describing two dimensional graphics. This document is \url{http://www.w3.org/TR/2011/REC-SVG11-20110816/}, the latest version of the standard at the time of writing. + +\subsubsection{Three types of object} +\begin{enumerate} + \item Vector graphics shapes (paths) + \item Images (embedded bitmaps) + \item Text +\end{enumerate} + +\subsubsection{Rendering Model and Precision} + +SVG uses the ``painter's model''. Paint is applied to regions of the page in an order, covering the paint below it according to rules for alpha blending. + +``Implementations of SVG are expected to behave as though they implement a rendering (or imaging) model cor- +responding to the one described in this chapter. A real implementation is not required to implement the model in +this way, but the result on any device supported by the implementation shall match that described by this model.'' + +SVG uses {\bf single precision floats}. Unlike PDF and PostScript, the standard specifies this as a {\bf minimum} range from \verb/-3.4e+38F/ to \verb/+3.4e+38F/ + +``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.'' + +There is also a ``High Quality SVG Viewers'' requirement to use at least {\bf double} precision floats. + +\section{OpenVG Specification 1.1 \cite{rice2008openvg}} +``OpenVG is an application programming interface (API) for hardware-accelerated two- +dimensional vector and raster graphics developed under the auspices of the Khronos +Group \url{www.khronos.org}.'' + +Specifically, provides the same drawing functionality required by a high-performance SVG document viewer (SVG Tiny 1.2) +TODO: Look at that $\neq$ SVG 1.1 + +It is designed to be similar to OpenGL. + +\subsubsection{Precision} +``All floating-point values are specified in standard IEEE 754 format. However, +implementations may clamp extremely large or small values to a restricted +range, and internal processing may be performed with lesser precision. At least +16 bits of mantissa, 6 bits of exponent, and a sign bit must be present, allowing +values from $\pm 2^{-30}$ to $\pm2^{31}$ to be represented with a fractional precision of at least 1 +in $2^{16}$.'' + +IEEE but with a non standard number of bits. + +Presumably the decreased precision is for increased efficiency the standard states that example applications are for ebooks. + + +\section{Document Object Model --- pugixml 1.4 manual \cite{pugixmlDOM}} + +Pugixml is a C++ library for parsing XML documents\cite{kapoulkine2014pugixml}. XML is based on the Document Object Model (DOM); this is explained pretty well by the pugixml manual. + +The document is the root node of the tree. Each child node has a type. These may +\begin{itemize} + \item Have attributes + \item Have child nodes of their own + \item Contain data +\end{itemize} + +In the case of HTML/SVG an XML parser within the browser/viewer creates the DOM tree from the XML (plain text) and then interprets that tree to produce the objects that will be rendered. + +Example of XML $\to$ DOM tree given at\cite{pugixmlDOM}. +Example of XML parsing using pugixml is in \shell{code/src/tests/xml.cpp} + + +\begin{figure}[H] + \centering +\begin{lstlisting}[language=XML,basicstyle=\ttfamily] + + + + some text + + some more text + + + + + + +\end{lstlisting} + + \includegraphics[width=0.6\textwidth]{references/pugixmlDOM-dom_tree.png} + \caption{Tree representation of the above listing \cite{pugixmlDOM}} +\end{figure} \chapter{General Notes} +\section{The DOM Model} + +A document is modelled as a tree. The root of the tree is the document. This has nodes of varying types. Some nodes may have children, attributes, and data. + +\section{Floating-Point Numbers\cite{HFP,goldberg1991whatevery,goldberg1992thedesign,priest1991algorithms}} + +A set of FP numbers is characterised by: +\begin{enumerate} + \item Radix (base) $\beta \geq 2$ + \item Precision %$p \req 2$ ``number of sig digits'' + \item Two ``extremal`` exponents $e_min < 0 < e_max$ (generally, don't have to have the $0$ in there) +\end{enumerate} + +Numbers are represented by {\bf integers}: $(M, e)$ such that $x = M \times \beta^{e - p + 1}$ + +Require: $|M| \leq \beta^{p}-1$ and $e_min \leq e \leq e_max$. + +Representations are not unique; set of equivelant representations is a cohort. + +$\beta^{e-p+1}$ is the quantum, $e-p+1$ is the quantum exponent. + +Alternate represetnation: $(s, m, e)$ such that $x = (-1)^s \times m \times \beta^{e}$ +$m$ is the significand, mantissa, or fractional part. Depending on what you read. + + + + + \section{Rounding Errors} + They happen. There is ULP and I don't mean a political party. TODO: Probably say something more insightful. Other than "here is a graph that shows errors and we blame rounding". -Results of \verb/calculatepi/ +\subsection{Results of calculatepi} + +We can calculate pi by numerically solving the integral: +\begin{align*} + \int_0^1 \left(\frac{4}{1+x^2}\right) dx &= \pi +\end{align*} + +Results with Simpson Method: \begin{figure}[H] \centering \includegraphics[width=0.8\textwidth]{figures/calculatepi.pdf}