[ipdf/documents.git] / LiteratureNotes.tex

\documentclass[8pt]{extarticle}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{amsmath} % needed for math align
\usepackage{bm} % needed for maths bold face
 \usepackage{graphicx}    % needed for including graphics e.g. EPS, PS
\usepackage{fancyhdr}   % needed for header

\usepackage{hyperref}

 \topmargin -1.5cm        % read Lamport p.163
 \oddsidemargin -0.04cm   % read Lamport p.163
 \evensidemargin -0.04cm  % same as oddsidemargin but for left-hand pages
 \textwidth 16.59cm
 \textheight 21.94cm 
 %\pagestyle{empty}       % Uncomment if don't want page numbers
 \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}


\newcommand{\vect}[1]{\boldsymbol{#1}} % Draw a vector
\newcommand{\divg}[1]{\nabla \cdot #1} % divergence
\newcommand{\curl}[1]{\nabla \times #1} % curl
\newcommand{\grad}[1]{\nabla #1} %gradient
\newcommand{\pd}[3][ ]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} %partial derivative
%\newcommand{\d}[3][ ]{\frac{d^{#1} #2}{d #3^{#1}}} %full derivative
\newcommand{\phasor}[1]{\tilde{#1}} % make a phasor
\newcommand{\laplacian}[1]{\nabla^2 {#1}} % The laplacian operator

\usepackage{color}
\usepackage{listings}

\definecolor{darkgray}{rgb}{0.95,0.95,0.95}
\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{backgroundcolor=\color{darkgray}}
\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}





\begin{document}


\pagestyle{fancy}
\fancyhead{}
\fancyfoot{}

\fancyhead[LO, L]{}
\fancyfoot[CO, C]{\thepage}

\begin{center}
        B.Eng. Final Year Project \par
        {\bf \Large Literature Notes} \par
        Sam Moore, David Gow \\
        Faculty of Engineering, Computing and Mathematics, University of Western Australia \\
        March 2014
\end{center}

\tableofcontents

\section{Postscript Language Reference Manual\cite{plrm}}

Adobe's official reference manual for PostScript.

It is big.

\section{Portable Document Format Reference Manual\cite{pdfref17}}

Adobe's official reference for PDF.

It is also big.

\pagebreak

\section{Portable Document Format (PDF) --- Finally...\cite{cheng2002portable}}

This is not spectacularly useful, is basically an advertisement for Adobe software.

{\bf Intro}
\begin{itemize}
        \item Visual communications has been revolutionised by computing
        \item BUT there have always been problems in exchanging formats
        \item Filetypes like text, rich text, IGES, DXF, TIFF, JPEG, GIFF solve problems for particular types of files only
        \item PDF solves everything for everyone; can include text, images, animation, sound, etc
\end{itemize}
{\bf PDF Features}
\begin{itemize}
        \item Raster Image Process (RIP) --- For printing (presumably also displaying on screen)
        \item Originally needed to convert to PS then RIP, with PS 3 can now RIP directly.
        \item Reduced filesize due to compression
        \item Four major applications - Stoy 1999\cite{stoy1999}
                \begin{enumerate}
                        \item Download files from internet
                        \item Files on CDs
                        \item Files for outputing to printers
                        \item Conventional [commercial scale?] printing
                \end{enumerate}
        \item List of various (Adobe) PDF related software
        \begin{itemize}
                \item Includes software for PS that converts to/from PDF 
                \item So PS was obviously pretty popular before PDF
        \end{itemize}
        \item Can Optimize for screen/printer [not clear how]
        \item Can compress for size
\end{itemize}

\pagebreak
\section{Pixels or Perish \cite{hayes2012pixels}}

``The art of scientific illustration will have to adapt to the new age of online publishing''
And therefore, JavaScript libraries ($\text{D}^3$) are the future.

The point is that we need to change from thinking about documents as paper to thinking of them as pixels.
This kind of makes it related to our paper, because it is the same way we are justifying our project. It does mention precision, but doesn't say we need to get more of it.

I get the feeling from this that Web based documents are a whole bunch of completely different design philosophies hacked together
with JavaScript.

This paper uses Metaphors a lot. I never met a phor that didn't over extend itself.


{\bf Intro}
\begin{itemize}
        \item Drawings/Pictures are ornaments in science but they are not just ornamental
        \item Processes have changed a lot; eg: photographic plates $\to$ digital images
        \item ``we are about to turn the page --- if not close the book --- on yet another chapter in publishing history.'' (HO HO HO)
        \item It would be cool to have animated figures in documents (eg: Population pyramid; changes with time); not just as ``supplements''
        \item In the beginning, there was PostScript, 1970s and 1980s, John Warnock and Charles Geschke, Adobe Systems
        \item PS is a language for vector graphics; objects are constructed from geometric primitives rather than a discrete array of pixels
        \item PS is a complete programming language; an image is also a program; can exploit this to control how images are created based on data (eg: Faces)
        \item PDF is ``flattened'' PS. No longer programable. Aspires to be ``virtual paper''.
        \item But why are we using such powerful computing machines just to emulate sheets paper? (the author asks)
\end{itemize}

{\bf Web based Documents}
\begin{itemize}
        \item HTML, CSS, JavaScript - The Axis of Web Documents
        \begin{itemize}
                \item HTML - Defines document structure
                \item CSS - Defines presentation of elements in document
                \item JavaScript - Encodes actions, allows dynamic content (change the HTML/CSS)
        \end{itemize}
        \item \texttt{<canvas>} will let you draw anything (So in principle don't even need all of HTML/CSS)
        \begin{itemize}
                \item Not device independent
                \item ``Coordinates can be specified with precision finer than pixel resolution'' {\bf (TODO: Investigate this?)}
                \item JavaScript operators to draw things on canvas are very similar to the PostScript model
        \end{itemize}
        \item SVG --- Same structure (Document Object Model (DOM)) as HTML
        \begin{itemize}
                \item ``Noun language''
                \item Nouns define lines/curves etc, rather than paragraphs/lists
                \item Also borrows things from PostScript (eg: line caps and joints)
                \item IS device independent, ``very high precision'' {\bf (TODO: Investigate)}
                \item JavaScript can be used to interact with SVG too
        \end{itemize}
        \item $\text{D}^{3}$ (Data Driven Documents) - A JavaScript library
        \begin{itemize}
                \item Idea is to create or modify elements of a DOM document using supplied data
                \item \url{https://github.com/mbostock/d3/wiki}
        \end{itemize}
        \item We are in a new Golden Age of data visualisation
        \item Why do we still use PDFs?
        \begin{itemize}
                \item PDFs are ``owned'' by the author/reader; you download it, store it, you can print it, etc
                \item HTML documents are normally on websites. They are not self contained. They often rely on remote content from other websites (annoying to download the whole document).
        \end{itemize}
        \item {\bf Conclusion} Someone should open up PDF to accept things like $\text{D}^{3}$ and other graphics formats (links nicely with \cite{barnes2013embedding})
        \item Also, Harry Potter reference

\end{itemize}

\section{Embedding and Publishing Interactive, 3D Figures in PDF Files\cite{barnes2013embedding}}

\begin{itemize}
        \item Linkes well with \cite{hayes2012pixels}; I heard you liked figures so I put a figure in your PDF
        \item Title pretty much summarises it; similar to \cite{hayes2012pixels} except these guys actually did something practical
\end{itemize}

\section{27 Bits are not enough for 8 digit accuracy\cite{goldberg1967twentyseven}}

Proves with maths, that rounding errors mean that you need at least $q$ bits for $p$ decimal digits. $10^p < 2^{q-1}$

\begin{itemize}
        \item Eg: For 8 decimal digits, since $10^8 < 2^{27}$ would expect to be able to represent with 27 binary digits
        \item But: Integer part requires digits bits (regardless of fixed or floating point represenetation)
        \item Trade-off between precision and range
        \begin{itemize}
                \item 9000000.0 $\to$ 9999999.9 needs 24 digits for the integer part $2^{23} = 83886008$
        \end{itemize}
        \item Floating point zero = smallest possible machine exponent
        \item Floating point representation:
        \begin{align*}
                y &= 0.y_1 y_2 \text{...} y_q \times 2^{n}
        \end{align*}
        \item Can eliminate a bit by considering whether $n = -e$ for $-e$ the smallest machine exponent (???)
        \begin{itemize}
                \item Get very small numbers with the same precision    
                \item Get large numbers with the extra bit of precision
        \end{itemize}
\end{itemize}

\section{What every computer scientist should know about floating-point arithmetic\cite{goldberg1991whatevery}}

\begin{itemize}
        \item Book: \emph{Floating Point Computation} by Pat Sterbenz (out of print... in 1991)
    \item IEEE floating point standard becoming popular (introduced in 1987, this is 1991)
    \begin{itemize}
                \item As well as structure, defines the algorithms for addition, multiplication, division and square root
                \item Makes things portable because results of operations are the same on all machines (following the standard)
                \item Alternatives to floating point: Floating slasi and Signed Logarithm (TODO: Look at these, although they will probably not be useful)

        \end{itemize}
        \item Base $\beta$ and precision $p$ (number of digits to represent with) - powers of the base can be represented exactly.
        \item Largest and smallest exponents $e_{min}$ and $e_{max}$
        \item Need bits for exponent and fraction, plus one for sign
        \item ``Floating point number'' is one that can be represented exactly.
        \item Representations are not unique! $0.01 \times 10^1 = 1.00 \times 10^{-1}$ Leading digit of one $\implies$ ``normalised''
        \item Requiring the representation to be normalised makes it unique, {\bf but means it is impossible to represent zero}.
        \begin{itemize}
                \item Represent zero as $1 \times \beta^{e_{min}-1}$ - requires extra bit in the exponent
        \end{itemize}
        \item {\bf Rounding Error}
        \begin{itemize}
                \item ``Units in the last place'' eg: 0.0314159 compared to 0.0314 has ulp error of 0.159
                \item If calculation is the nearest floating point number to the result, it will still be as much as 1/2 ulp in error
                \item Relative error corresponding to 1/2 ulp can vary by a factor of $\beta$ ``wobble''. Written in terms of $\epsilon$
                \item Maths $\implies$ {\bf Relative error is always bounded by $\epsilon = (\beta/2)\beta^{-p}$}
                \item Fixed relative error $\implies$ ulp can vary by a factor of $\beta$ . Vice versa
                \item Larger $\beta \implies$ larger errors
        \end{itemize}
        \item {\bf Guard Digits}
        \begin{itemize}
                \item In subtraction: Could compute exact difference and then round; this is expensive
                \item Keep fixed number of digits but shift operand right; discard precision. Lead to relative error up to $\beta - 1$
                \item Guard digit: Add extra digits before truncating. Leads to relative error of less than $2\epsilon$. This also applies to addition
        \end{itemize}
        \item {\bf Catastrophic Cancellation} - Operands are subject to rounding errors - multiplication
        \item {\bf Benign Cancellation} - Subtractions. Error $< 2\epsilon$
        \item Rearrange formula to avoid catastrophic cancellation
        \item Historical interest only - speculation on why IBM used $\beta = 16$ for the system/370 - increased range? Avoids shifting
        \item Precision: IEEE defines extended precision (a lower bound only)
        \item Discussion of the IEEE standard for operations (TODO: Go over in more detail)
        \item NaN allow continuing with underflow and Infinity with overflow
        \item ``Incidentally, some people think that the solution to such anomalies is never to compare floating-point numbers for equality but instead to consider them equal if they are within some error bound E. This is hardly a cure all, because it raises as many questions as it answers.'' - On equality of floating point numbers

\end{itemize}




\pagebreak
\bibliographystyle{unsrt}
\bibliography{papers}

\end{document}