From: David Gow Date: Mon, 19 May 2014 02:25:54 +0000 (+0800) Subject: Happy thoughts... Happy thoughts! X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fdocuments.git;a=commitdiff_plain;h=6dba5c70d6843d5c8fbb81116b8ee527cfa5a730;ds=sidebyside Happy thoughts... Happy thoughts! --- diff --git a/LitReviewDavid.pdf b/LitReviewDavid.pdf index 4949e4d..1e0bb5e 100644 Binary files a/LitReviewDavid.pdf and b/LitReviewDavid.pdf differ diff --git a/LitReviewDavid.tex b/LitReviewDavid.tex index 532017b..a8947e8 100644 --- a/LitReviewDavid.tex +++ b/LitReviewDavid.tex @@ -3,6 +3,7 @@ \usepackage{hyperref} \usepackage{graphicx} \usepackage{amsmath} +\usepackage{amssymb} %opening \title{Literature Review} @@ -42,7 +43,7 @@ a turing complete document language with instructions which emit shapes to be di immediately, as in PostScript, or stored in another file, such as with \TeX or \LaTeX, which emit a \texttt{DVI} file. Most other forms of document use a \emph{Document Object Model}, being a list or tree of objects to be rendered. \texttt{DVI}, \texttt{PDF}, \texttt{HTML}\footnote{Some of these formats --- most notably \texttt{HTML} --- implement a scripting lanugage such as JavaScript, -which permit the DOM to be modified while the document is being viewed.} and SVG. Of these, only \texttt{HTML} and \TeX typically +which permit the DOM to be modified while the document is being viewed.} and SVG\cite{svg2011-1.1}. Of these, only \texttt{HTML} and \TeX typically store documents in pre-layout stages, whereas even turing complete document formats such as PostScript typically encode documents which already have their elements placed. @@ -59,7 +60,7 @@ and \emph{vector} graphics, defined by mathematical descriptions of objects. Bit and are match how cameras, printers and monitors work. However, bitmap devices do not handle zooming beyond their ``native'' resolution --- the resolution where one document pixel maps to one display pixel ---, exhibiting an artefact called pixelation where the pixel structure becomes evident. Attempts to use interpolation to hide this effect are -never entirely successful, and sharp edges, such as those found in text and diagrams, are particularly effected. +never entirely successful, and sharp edges, such as those found in text and diagrams, are particularly affected. \begin{figure}[h] \centering \includegraphics[width=0.8\linewidth]{figures/vectorraster_example} @@ -96,7 +97,7 @@ the Cairo\cite{worth2003xr} library, based around the PostScript/PDF rendering m renderer by nVidia\cite{kilgard2012gpu} as an OpenGL extension\cite{kilgard300programming}. -\section{Floating-Point Precision} +\section{Numeric formats} On modern computer architectures, there are two basic number formats supported: fixed-width integers and \emph{floating-point} numbers. Typically, computers @@ -135,12 +136,27 @@ precision than numbers close to zero. This can present problems in documents whe on objects far from the origin. IEEE floating-point has some interesting features as well, including values for negative zero, -positive and negative infinity and the ``Not a Number'' (NaN) value. Indeed, with these values, +positive and negative infinity, the ``Not a Number'' (NaN) value and \emph{denormal} values, which +trade precision for range when dealing with very small numbers. Indeed, with these values, IEEE 754 floating-point equality does not form an equivalence relation, which can cause issues when not considered carefully.\cite{goldberg1991whatevery} -Arb. precision exists +There also exist formats for storing numbers with arbitrary precising and/or range. +Some programming languages support ``big integer''\cite{java_bigint} types which can +represent any integer that can fit in the system's memory. Similarly, there are +arbitrary-precision floating-point data types\cite{java_bigdecimal}\cite{boost_multiprecision} +which can represent any number of the form +\begin{equation} + \frac{n}{2^d} \; \; \; \; n,d \in \mathbb{Z} % This spacing is horrible, and I should be ashamed. +\end{equation} +These types are typically built from several native data types such as integers and floats, +paired with custom routines implementing arithmetic primitives.\cite{priest1991algorithms} +These, therefore, are likely slower than the native types they are built on. + +While traditionally, GPUs have supported some approximation of IEEE 754's 32-bit floats, +modern graphics processors also support 16-bit\cite{nv_half_float} and 64-bit\cite{arb_gpu_shader_fp64} +IEEE floats. Higher precision numeric types can be implemented or used on the GPU, but are slow. \cite{emmart2010high} diff --git a/papers.bib b/papers.bib index c735181..06b6f48 100644 --- a/papers.bib +++ b/papers.bib @@ -95,6 +95,25 @@ Goldberg:1991:CSK:103162.103163, address = {New York, NY, USA}, keywords = {NaN, denormalized number, exception, floating-point, floating-point standard, gradual underflow, guard digit, overflow, relative error, rounding error, rounding mode, ulp, underflow}, } + +@misc{arb_gpu_shader_fp64, + title={{ARB\_gpu\_shader\_fp64}}, + author={Brown, Pat and Lichtenbelt, Barthold and Licea-Kane, Bill and Merry, Bruce and Dodd, Chris and Werness, Eric and Sellers, Graham and Roth, Greg and Bolz, Jeff and Haemel, Nick and Boudier, Pierre and Daniell, Piers}, + year={2010}, + journal={OpenGL Extension}, + publisher={Kronos Group}, + howpublished={\url{http://www.opengl.org/registry/specs/ARB/gpu_shader_fp64.txt}} +} + +@misc{nv_half_float, + title={{NV\_half\_float}}, + author={Brown, Pat}, + year={2002}, + journal={OpenGL Extension}, + publisher={NVIDIA Corporation}, + howpublished={\url{http://www.opengl.org/registry/specs/NV/half_float.txt}} +} + @inproceedings{emmart2010high, title={High precision integer multiplication with a graphics processing unit}, author={Emmart, Niall and Weems, Charles}, @@ -513,6 +532,22 @@ doi={10.1109/ARITH.1991.145549},} howpublished = {\url{http://www.boost.org/doc/libs/1_53_0/libs/multiprecision/doc/html/boost_multiprecision/}} } +@misc{java_bigint, + author = {Oracle Corporation}, + title = {java.math.{BigInteger}}, + booktitle = {Java Platform 6 {SE}}, + urldate = {19-05-2014}, + howpublished = {\url{http://docs.oracle.com/javase/6/docs/api/java/math/BigInteger.html}} +} + +@misc{java_bigdecimal, + author = {Oracle Corporation}, + title = {java.math.{BigDecimal}}, + booktitle = {Java Platform 7 {SE}}, + howpublished = {\url{http://docs.oracle.com/javase/7/docs/api/java/math/BigDecimal.html}}, + urldate = {19-05-2014} +} + % A CMOS Floating Point Unit @MISC{kelley1997acmos, author = {Michael J. Kelley and Matthew A. Postiff and Advisor Richard and B. Brown},