Next:
Introduction
Up:
A Calculator for Exact
Previous:
Acknowledgements
Contents
Contents
Introduction
Work Performed
Related Work
Organisation
Real Number Computation
Approaches to Real Arithmetic
Floating Point Arithmetic
Floating Point arithmetic with error analysis
Interval Arithmetic
Stochastic Rounding
Symbolic Approaches
Exact Real Arithmetic
Approaches to Exact Real Arithmetic
Representation Problems
Two Suitable Digit Representations
Other Possible Representations
Continued Fractions
B-adic Number Stream
Linear Fractional Transformations
Representations
Terminology and Notation
Streams
Representing Reals as Streams
Signed Binary Digit Streams
Dyadic Rational Streams
(Mantissa, Exponent) Representation
Nested interval Representation
Algorithm Design
Considerations
Useful Properties
Range Analysis
Relationship between `cons' and average
Properties of average
Conversion between Stream Representations
Conversion to and from decimal
Decimal to Signed Binary
Decimal integers to signed binary
Decimal fractions to signed binary
Signed Binary to Decimal
Signed binary integers to decimal
Signed binary fractions to signed decimal fractions
Signed decimal fractions to decimal
Basic Operations
Auxiliary operations
Negation
Multiplication of a stream by a digit
Addition or subtraction of one from stream
The `p' function
Dyadic Stream Operations
Average
Multiplication
Signed Binary Stream Operations
Average
Multiplication
Division by an integer
(Mantissa, Exponent) Operations
Addition and Subtraction
Multiplication
`Normalisation'
Signed binary (mantissa, exponent) `normalisation'
Dyadic (mantissa, exponent) `normalisation'
Division
Modification of mantissas
Output zero case:
Output positive digits
Output negative digits
Extending division to the whole real line
High-Level Operations
Computing Limits
Limits within [-1,1]
Determining output digits
Input digits required
A recursive definition
Recursive calls to compute the limits
Limits within
Transcendental Functions
Trigonometric Functions
Sine
Cosine
Arctan
Pi
Logarithmic Functions
Exponential Function
Natural Logarithm Function
Exponentiation:
x
y
Functional Operations
Design and Implementation
Design
Modular Structure
User Interface
Implementation
Language
Haskell:
User Interface
Implementation Tools
Implementation History
General Issues
Use of fixed and arbitrary length integers
Dyadic digit representation
Coding an algorithm in Haskell
Signed Binary Division by an Integer
Signed Binary Average
Analysis
Theoretical Analysis
Conversions between Representations
Average
Dyadic Stream Average
Signed Binary Stream Average
Multiplication
Dyadic Stream Multiplication
Signed Binary Stream Multiplication
Division
Logistic Map
Dyadic Arithmetic
Signed Binary Arithmetic
Sequences of operations
Summary of Theoretical Analysis
Experimental Analysis
Strategies
Lookahead
Profiling
Timing
Lookahead Results
Signed Binary Multiplication
Division
Dyadic digit swell
Profiling Results
Timing Results
Summary of Experimental Analysis
Conclusion
Summary of Analysis
Evaluation of Implementation
Possible Extensions and Future Work
Dyadic Digit Operations
Lowest Terms
Average
Multiplication
Shift operators
Relational Tests
Algorithms
Division
Limits
Expression Language
References
Martin Escardo
5/11/2000