\documentclass[12pt]{article}
\usepackage{a4wide}
\newcommand{\al}{$<$}
\newcommand{\ar}{$>$}
\parindent 0pt
\parskip 6pt
\begin{document}
\thispagestyle{empty}
\rightline{\large\al\emph{name}\ar}
\medskip
\rightline{\large\al\emph{College}\ar}
\medskip
\rightline{\large\al\emph{CRSID}\ar}
\vfil
\centerline{\large Diploma in Computer Science Project Proposal}
\vspace{0.4in}
\centerline{\Large\bf Exact Real Arithmetic}
\vspace{0.3in}
\centerline{\large \al\emph{date}\ar}
\vfil
{\bf Project Originator:} This is a Model Project Proposal
\vspace{0.1in}
{\bf Resources Required:} See attached Project Resource Form
\vspace{0.5in}
{\bf Project Supervisor:} \al\emph{name}\ar
\vspace{0.2in}
{\bf Signature:}
\vspace{0.5in}
{\bf Director of Studies:} \al\emph{name}\ar
\vspace{0.2in}
{\bf Signature:}
\vspace{0.5in}
{\bf Overseers:} \al\emph{name}\ar\ and \al\emph{name}\ar
\vspace{0.2in}
{\bf Signatures:} \al\emph{no need to obtain Overseers' signatures yourself}\ar
\vfil
\eject
%Special Resources:& Possible requirement for a Poly/ML compiler or
% some other non-standard language. A Project
% Supervisor who understands the relevant numerical
% analysis background.\cr
%\noalign{\vskip 12pt}
\al\emph{This Model Proposal refers to the language ML and to data
structures known as lazy lists. These are used only as examples.
It is perfectly possible to use a different language and to use
different data structures. Likewise any specific representations of
numbers are also given simply as examples. At various points in
this document\/ {\rm alternatives} are suggested or implied, and the
submitted proposal is to be selected from the options given.}\ar
\section*{Introduction and Description of the Work}
Floating-point calculations do not, in general, lead to exact results.
Moreover, there are circumstances when the results of very few
operations can be wildly in error even when using 64-bit precision. A
well-known example is the following iteration which takes the golden
ratio as the starting point:
\[
\gamma_0=\frac{1+\sqrt5}{2}\qquad \mbox{and}\qquad
\gamma_{n}=\frac{1}{\gamma_{n-1}-1}\qquad
\mbox{for $n>0$}
\]
It is trivial to demonstrate that $\gamma_0=\gamma_1=\gamma_2\ldots$
but when this iteration is carried out using any finite precision
arithmetic the values diverge from $\gamma_0$ after very few
iterations.
People concerned with theorem proving sometimes want to perform
arithmetic calculations but cannot tolerate any possibility of the end
results being incorrect. In general, the value to be computed will be
a boolean obtained by comparing the results of various numeric
calculations. For example, it may be important to know whether
$\gamma_{20}${}$<$4 even though the exact value of $\gamma_{20}$ is
not too important.
One way of enabling a theorem prover to evaluate such a boolean
reliably is to provide it with so-called ``exact'' real arithmetic.
Where normal floating-point arithmetic uses fixed precision, exact
arithmetic will work in variable precision. Furthermore, at all
stages of the calculation, it will keep track of the extent to which
rounding errors could have accumulated. When it comes to display a
result, a comparison is performed to check that all is well.
A key idea is that when an exact real arithmetic system finds itself
close to being compromised by the effects of round-off it must be able
to go back and (automatically) extend the precision of all its
previous working until eventually it has a result that is as accurate
as is needed.
The effect is that when the system computes a value and is asked to
display it to (say) five significant figures the user can be certain
that the figures displayed are correct, however unstable the numerical
calculation involved.
Tests involving equality necessarily give trouble. For example,
evaluating the boolean formula $\sin(\pi)$=0.0 might reasonably loop,
evaluating $\sin(\pi)$ to ever higher precision trying to detect that
the answer was non-zero. This problem is inherent in the idea of
exact real arithmetic (exactness comes at the cost of guaranteed
termination) but its implications should be regarded as outside the
scope of any project based on this Model Proposal.
\section*{Resources Required}
\al\emph{The most suitable language may turn out to be non-standard
and its availability needs to be established. This would be the
case if Poly/ML is chosen as the language.}\ar
\section*{Starting Point}
\al\emph{This is the place to declare any prior knowledge relevant to
the project. For example any relevant courses taken prior to the
start of the Diploma year.}\ar
\section*{Substance and Structure of the Project}
\al\emph{You should choose between options I and II below after
discussions with your Supervisor and Overseers}.\ar
\newcounter{bean}
\begin{list}
{\Roman{bean}}{\usecounter{bean}}
\item The aim of the project is to investigate alternative
representations of real numbers and to produce a suite of procedures
for carrying out arithmetic operations. It will implement methods
\al\emph{X\/}\ar\ and \al\emph{Y\/}\ar\ as described below and compare them
in terms of implementation complexity and performance.
\item The aim of the project is to implement the \al\emph{X\/}\ar\
style of exact real arithmetic as described below.
\end{list}
\medskip
\al\emph{If just one method is implemented it will be expected that
more work will be done in that single implementation than if two or
more different schemes are being compared}.\ar
\begin{enumerate}
\item A real number can be represented as a lazy list, with each
successive value in the list giving a better approximation to the
number concerned. The values stored are numerators of fractions
which have implicit denominators, so that item $i$ in the list is
treated as having denominator $B^{i}$ for some pre-chosen base
$B$\null.
Lazy lists (which it will be reasonable to implement using the
language ML) enable later, higher precision, representations to be
calculated only when needed. Poly/ML supports arbitrary precision
integer arithmetic and its use means that having huge multi-precision
integers as later terms in a lazy list does not present a problem.
\item A real number can be stored as a pair of rational numbers, each
with a common denominator which is a power of 2. The two numbers
represent the lower and higher end-points of an interval within
which the exact value is known to lie.
In addition to the interval, a number needs to have associated data
structures that enable the source of the number to be identified and
extra calculations to be\break performed which update the number in such a
way that the width of the interval is reduced.
The rational numbers involved frequently grow to be multiple-precision
integers, so either the code has to be written in a language that
supports them or time has to be allowed for implementing support for
them. \al\emph{You have to decide which approach to adopt before
handing in your Project Proposal}.\ar
\item A real number can be stored as the first few partial quotients
of its continued fraction. The continued fraction for a number $x$
is a sequence of integers $a_i$ defined by letting $x_0 = x$ and
then
\[
a_i = \mbox{floor}(x_i)\qquad \mbox{and}\qquad
x_{i+1} = \frac{1}{(x_i - a_i)}
\]
Arithmetic on continued fractions has been explored by Gosper.
\item A fractional number with decimal expansion of (say)
$0.14159\ldots$ can be represented as a lazy list $[1, 4, 1, 5,
9,\ldots]$. Arithmetic on such lazy decimals can run into severe
trouble with the confusion between $[1, 9, 9, 9, 9,\ldots]$ and $[2,
0, 0, 0, 0,\ldots]$, and it may prove necessary to adjust the
representation slightly to soften the impact of this problem.
It would also be natural to implement a scheme which uses a
radix larger than 10, but nevertheless all calculations will be
performed in terms of single digits so the representation does not
need to rely on any underlying big-integer arithmetic.
\item Other representations for exact real numbers can also be
found in the literature, for instance storing a number by giving
a polynomial equation that it satisfies together with a bounding
interval. For example, the square root of 2 could be represented by
[$q^2-2=0, 1 < q < 2$].
\end{enumerate}
\al\emph{The sketches above are to be taken as starting points for
investigation of the literature and discussion with your Supervisor.
A look at the 1996 Diploma Dissertation, {\rm Exact Real Arithmetic,
using ML}, by Chetan Radia, is likely to prove useful since it
provides some pointers into the literature, and discusses terms such
as $B$-adic and $B$-approximable}.\ar
\al\emph{Note also that it may make sense to store some numbers in
your package in one format and others in another. For example, it
might be sensible to represent numbers that happen to be rational as
exact fractions but reserve a more general scheme for numbers like
$\sqrt2$}.\ar
\bigskip
The project has the following main sections:
\begin{enumerate}
\item A study of the selected representation of real numbers and the
algorithms for handling numbers so represented. This will involve
study of both general background material on error propagation in
numerical calculation, and a detailed study of previous work both in
Cambridge and elsewhere of the selected style of exact arithmetic.
\item Familiarisation \al\emph{if need be}\ar\ with the programming
language to be used and the\break surrounding software tools. Detailed
design of data structures to represent real\break numbers. Planning
implementation and test strategies for basic arithmetic.
\item Developing and testing the code for the principal arithmetic
operations (addition, subtraction, multiplication, division and
square root).
\item Evaluation using the golden ratio example and other illustrative
cases. Collating the evidence that will be included in the
Dissertation to demonstrate that the code behaves as required.
\item Writing the Dissertation.
\end{enumerate}
\al\emph{If two or more representations are to be implemented and
compared, the above is probably sufficiently ambitious. If just one
representation is to be used it would be appropriate to augment (3)
with further procedures such as logarithms and trigonometrical
functions. Before simply adding these to the text of your proposal
you need to check the literature and discuss details quite carefully
with your Supervisor since not all representations support the
elementary functions at all comfortably}.\ar
\al\emph{It would also be possible to adjust the style and emphasis of
the project either towards the best possible computational
capability for your code, or towards the most careful and formally
justified certainty that the answers delivered are correct. It is
unlikely that this project would call for a substantial or elaborate
user-interface but that side of things could also figure as a modest
aspect of the entire project}.\ar
\section*{Success Criterion}
To demonstrate, through well-chosen examples, that the project is
capable, with reasonable efficiency, of performing exact real
calculations.
\section*{Timetable and Milestones}
\al\emph{In the following scheme, weeks are numbered so that the week
starting on the day on which Project Proposals are handed in is
Week~1. The year's timetable means that the deadline for submitting
dissertations is in Week~34.}\ar
\al\emph{In the Project Proposal that you hand in, {\rm actual dates}
should be used instead of week numbers and you should show how these
dates relate to the periods in which lectures take place. Week~1
starts immediately after submission of the Project Proposal.}\ar
\al\emph{The timetable and milestones given below refer to just one
particular interpretation of this document: this uses ML and a
lazy-list data-structure. Even if you select exactly this
interpretation you will need to review the suggested timetable and
adjust the dates to allow as precisely as you can for the amount of
programming and ML experience you have at the start of the year.
Take account of the dates you and your Supervisor will be working in
Cambridge outside Lecture Term. Note that some candidates write the
Introduction and Preparation chapters of their dissertations quite
early in the year, while others will do all their writing in one
burst near the end}.\ar
\al\emph{If \hbox{Java} were to be used there would be no need to
allow time to learn ML but time would have to be budgeted for
gaining experience of lazy lists in Java and for writing
procedures to handle arbitrary precision integers.}\ar
\subsection*{Before Proposal submission}
\al\emph{This section will not appear in your Project Proposal.}\ar
Discussion with Overseers and Director of Studies. Allocation of and
discussion with Project Supervisor, preliminary reading, choice of the
variant on the project \al\emph{a lazy list representation in this
example}\ar\ and language \al\emph{ML in this example\/}\ar, writing
Project Proposal. Discussion with Supervisor to arrange a schedule of
regular meetings for obtaining support during the course of the year.
Milestones: Phase~1 Report Form (on the Monday immediately following
the main Briefing Lecture), then a Project Proposal complete with as
realistic a timetable as possible, approval from Overseers and
confirmed availability of any special resources needed. Signatures
from Supervisor and Director of Studies.
\subsection*{Weeks 1 to 5}
\al\emph{Real work on the project starts here (as distinct from just
work on the proposal). A significant problem for Diploma candidates
is that this critical period largely coincides with the Christmas
vacation. There is no guarantee that supervisors will be available
outside Lecture Term, but Diploma students take much less of a
Christmas break than undergraduates do, and so have some opportunity
for uninterrupted reading and initial practical work at this stage.
It is important to have completed some serious work on the project
before the pressures of the Lent Term become all too apparent.}\ar
Study ML and the particular implementation of it to be used. Practise
writing various small programs, including ones that use lazy lists.
Milestones: Some working example ML programs including cases that
create and use lazy lists.
\subsection*{Weeks 6 and 7}
Further literature study and discussion with Supervisor to ensure that
the chosen representation of exact real numbers is understood.
Implementation in ML of data types which accord with the
representation, and code that makes it possible to construct data
structures representing simple constants. Write code that can be used
to display the data structures in human-readable form so that it is
possible to check that they are as expected.
Milestones: Ability to construct and display data structures that
represent simple constants such as 0, 1 and 2.
\subsection*{Weeks 8 to 10}
Implement code to add, subtract and negate numbers. Also implement
either code that displays a number to a specified guaranteed precision
or which performs a ``less-than'' comparison between two numbers.
This will involve being able to make the precision of intermediate
results grow on demand.
Start to plan the Dissertation, thinking ahead especially to the
collection of examples and tests that will be used to demonstrate that
the project has been a success.
Milestones: Ability to run some very simple calculations in such a way
that precision has to be increased (requiring a lazy list has to be
extended) during the course of the calculation.
\subsection*{Weeks 11 and 12}
Complete code for the multiplication and division. Refine the code
for addition, subtraction etc. Prepare further test cases. Review
timetable for the remainder of the project and adjust in the light of
experience thus far. Write the Progress Report drawing attention to
the code already written, incorporating some examples, and recording
any augmentations which at this stage seem reasonably likely to be
incorporated.
Milestones: Basic arithmetic operations now working, but probably with
some serious inefficiencies in the code, Progress Report submitted and
entire project reviewed both personally and with Overseers.
\subsection*{Weeks 13 to 19 (including Easter vacation)}
Implement square roots \al\emph{and any other elementary functions
selected at proposal time to bulk out the single-implementation
project}\ar. Write initial chapters of the Dissertation.
\al\emph{The Easter break from lectures can provide a time to work on
a substantial challenge such as the computation of logarithms, where
an uninterrupted week can allow you to get to grips with a fairly
complicated algorithm. This is a good time to put in some quiet
work (while your Supervisor is busy on other things) writing the
Preparation and Implementation chapters of the Dissertation. By
this stage the form of the final implementation should be
sufficiently clear that most of that chapter can be written, even if
the code is incomplete. Describing clearly what the code will do
can often be a way of sharpening your own understanding of how to
implement it.}\ar
Milestones: Preparation chapter of Dissertation complete,
Implementation chapter at least half complete, code can perform a
variety of interesting tasks and should be in a state that in the
worst case it would satisfy the examiners with at most cosmetic
adjustment.
\subsection*{Weeks 20 to 26}
\al\emph{Since your project is, by now, in fairly good shape there is
a chance to use the immediate run-up to exams to attend to small
rationalisations and to implement things that are useful but fairly
straightforward. It is generally not a good idea to drop all
project work over the revision season; if you do, the code will feel
amazingly unfamiliar when you return to it. Equally, first priority
has to go to the exams, so do not schedule anything too demanding on
the project front here. The fact that the Implementation chapter of
the Dissertation is in draft will mean that you should have a very
clear view of the work that remains, and so can schedule it
rationally.}\ar
Work on the project will be kept ticking over during this period but
undoubtedly the Easter Term lectures and examination revision will
take priority.
\subsection*{Weeks 27 to 31}
\al\emph{Getting back to work after the examinations and May Week
calls for discipline. Setting a timetable can help stiffen your
resolve!}\ar
Evaluation and testing. Finish off otherwise ragged parts of the
code. Write the Introduction chapter and draft the Evaluation and
Conclusions chapters of the Dissertation, complete the Implementation
chapter.
Milestones: Examples and test cases run and results collected,
Dissertation essentially complete, with large sections of it
proof-read by friends and/or Supervisor.
\subsection*{Weeks 32 and 33}
Finish Dissertation, preparing diagrams for insertion. Review whole
project, check the Dissertation, and spend a final few days on
whatever is in greatest need of attention.
\al\emph{In many cases, once a Dissertation is complete (but not
before) it will become clear where the biggest weakness in the
entire work is. In some cases this will be that some feature of the
code has not been completed or debugged, in other cases it will be
that more sample output is needed to show the project's capabilities
on larger test cases. In yet other cases it will be that the
Dissertation is not as neatly laid out or well written as would be
ideal. There is much to be said for reserving a small amount of
time right at the end of the project (when your skills are most
developed) to put in a short but intense burst of work to try to
improve matters. Doing this when the Dissertation is already
complete is good: you have a clearly limited amount of time to work,
and if your efforts fail you still have something to hand in! If
you succeed you may be able to replace that paragraph where you
apologise for not getting feature X working into a brief note
observing that you can indeed do X as well as all the other things
you have talked about.}\ar
\subsection*{Week 34}
\al\emph{Aim to submit the dissertation at least a week before the
deadline. Be ready to check whether you will be needed for a\/ {\rm
viva voce} examination}.\ar
Milestone: Submission of Dissertation.
\end{document}