Week 1 - Floating Point#

Numerical problem solving#

Understand the specification
Analyse the problem
Design an algorithm and tests
Implement
Test and iterate

Numerical modelling is an iterative design process.

Approaches#

Top-down (stepwise refinement)	Bottom-up
Start from the full problem	Start from small components
Divide it into smaller parts	Combine components into a complete solution

Practical solutions usually mix both approaches.

Types of error#

Truncation	Round-off
Error caused by the numerical method	Error caused by finite-precision arithmetic

Truncation error#

Replacing an infinite process with a finite approximation.

For the exponential function:

$e^x=\sum_{k=0}^{\infty}\frac{x^k}{k!}$

Using only the first $n$ terms:

$P_n(x)=\sum_{k=0}^{n}\frac{x^k}{k!}$

$E_T=e^x-P_n(x)$

Taylor approximation of

$e^{-0.4}$

Increasing $n$ makes $P_n(-0.4)$ approach $e^{-0.4}$ .

For an alternating series, the error is bounded by the next omitted term.

Round-off error#

Error caused by storing numbers using finitely many digits.

Accumulates during arithmetic
Can dominate even when truncation error is small
Severe when large values cancel

Computing

$e^{-30.4}$

A direct Taylor sum creates large alternating terms which nearly cancel, producing a highly inaccurate result.

A safer form is:

$e^{-30.4}=\frac{e^{-0.4}}{e^{30}}$

Binary numbers#

$(\ldots b_1b_0.b_{-1}b_{-2}\ldots)_2 =\sum_i b_i2^i$

Decimal part	Conversion
Integer	Repeatedly divide by $2$ ; read remainders upwards
Fraction	Repeatedly multiply by $2$ ; read integer parts downwards

Decimal to binary

$(53)_{10}=(110101)_2$

$(0.7)_{10}\approx(0.10110011\ldots)_2$

Some decimal fractions repeat infinitely in binary.

Floating-point representation#

$x=\pm0.d_1d_2\ldots d_p\times B^e$

Part	Meaning
$\pm$	Sign
$d_1\ldots d_p$	Mantissa/significand
$B$	Base
$e$	Exponent

Normalised numbers have $d_1\neq0$
Computers normally use base $2$
Only finitely many real numbers can be represented exactly

Base-10 normalisation

$27.39=0.2739\times10^2$

$-0.00124=-0.1240\times10^{-2}$

IEEE 754#

Normalised binary form:

$\pm1.d_1d_2\ldots d_p\times2^e$

Precision	Total bits	Sign	Exponent	Fraction
Single	32	1	8	23
Double	64	1	11	52
Extended	80	1	15	64

For single precision:

$e=\text{stored exponent}-127$

Normal exponent range:

$-126\le e\le127$

Binary normalisation

$(9.4)_{10}=(1001.0110\ldots)_2$

$=1.0010110\ldots\times2^3$

Machine Epsilon#

Distance between $1$ and the next representable floating-point number.

For double precision:

$\epsilon_M=2^{-52} \approx2.220446\times10^{-16}$

Representation error:

$\frac{|x-x^*|}{|x|} \le\frac{1}{2}\epsilon_M$

Machine epsilon in Python

import sys

sys.float_info.epsilon

Chopping and Rounding#

Chopping	Rounding
Discard extra digits	Choose the nearest representable value
Usually larger error	Usually smaller error

Chopping vs rounding

$0.137\times10^1+0.269\times10^{-1} =0.13969\times10^1$

Chopping	Rounding
$0.139\times10^1$	$0.140\times10^1$

Cancellation#

Subtracting nearly equal numbers can remove significant digits.

Loss of significance

$0.485\times10^4-0.482\times10^4$

$=0.003\times10^4 =0.300\times10^2$

Most of the original significant information is lost.

Floating-point comparisons#

Avoid exact comparisons:

x == 8.932

Use a tolerance:

abs(x - 8.932) < tolerance

Good practice

Avoid exact floating-point equality
Avoid subtracting nearly equal values
Reformulate numerically unstable expressions
Verify results using another method
More iterations do not always mean greater accuracy

Contributors: Keys

Comments

Powered by GitHub issues