# Introduction to Numerical Methods/Rounding Off Errors

# Rounding Off Errors

Learning objectives:

-   recognize the sources of overflow and underflow errors
-   convert between decimal representation and floating point
    representation
-   understand the IEEE 754 standard of a floating point representation
    on computers
-   calculate the machine epsilon of a representation.

## Integer Overflow (Error)

How are integers represented on a computer?

Most computers use the 2\'s
complement
representation. Assume we have 4 bits to store and operate on an integer
we may end up with the following situation:

` 0111 (7)`\
`+0001 (1)`\
`-----`\
` 1000 (-8)`

The numbers in parentheses are the decimal value represented by the 2\'s
complement binary integers. The result is obviously wrong because adding
positive numbers should never result in a negative number. The reason
for the error is that result exceeds the range of values the 4-bit can
store with the 2\'s complement notation.

The following example gives the wrong answer for the same reason. The
leading 1 can not be stored.

` 1000 (-8)`\
`+1111 (-1)`\
`-----`\
`10111 (7)`

## Floating-point Underflow (Error)

In math numbers have infinite precision, but numerals (representations
of number) have finite precision. One third (1/3) can not be represented
precisely in decimal or it would require a infinite number of digits,
which is impossible. Similarly 0.2 can not be represented precisely in
binary, which means its binary representation is not precise (an
approximation).

When numbers are computed/calculated on a computer, the representations
of the numbers are being manipulated and the result will very likely be
imprecise. This is an important limitation of computing. Essentially the
computer must be considered a part of our model when we solve problems
computationally. We must factor the computer in because it is a binary
computer approximating base ten numbers.

An floating-point underflow or
underflow happens
when the result of a calculation is too small to be stored. A underflow
can be caused by the (negative) overflow of the exponent.

:   What is the binary representation of $11.1875_{10}$?

### Fixed-point Representation

Any real number can be represented in binary as a fixed-point number. To
convert the number from its decimal (base 10) representation to its
binary representation we need to convert the integer part and the
fractional part to binary separately, because different methods are
required. Please check out the following resource on how to do that
1.

With a fixed number of digits and a fixed decimal point the range of
representable values is fixed. Given five digits as follows
$nnn.nn_{10}$, we can represent positive values from $0.01_{10}$ to
$999.99_{10}$. Using the following scientific notation
$nnn \times 10^{nn}$ we can represent positive values ranging from
$0.01_{10}$ to $99900_{10}$, which is much larger than that of the
fixed-point representation.

### Floating-point Representation

Given a fixed number of digits we can represent a larger range of values
using the floating-point
format. The IEEE 754 format is a international standard on
floating-point representation of numbers in computers. A 32-bit floating
point number (single precision) is represented using three parts as
shown in the figure: : a sign bit, a (biased) exponent, and a fraction.
!The number 0.15625 represented as a single-precision IEEE 754-1985
floating-point number. See text for
explanation.
The value represented by an IEEE 754 single precision floating point
number can be calculated using the following formula:

$$(-1)^{sign} \times 1.fraction \times 2^{exponent - 127}$$

For example to store in IEEE single precision floating point format
$0.15625_{10}=0.00101_{2}=1.01_2 \times 2^{-3}$, we need to store a sign
bit of $0$ (0 means positive and 1 means negative), a fraction of $.01$,
and a biased exponent of $-3_{10}+127_{10}=124_{10}=1111100_2$. Because
all numbers, except 0, will have a leading one in the binary
\"scientific\" representation that one is not stored in IEEE 754 format
to save one bit. We will say how the value 0 is represented in a moment.

The biased exponent is just a clever way to use the available bits to
represent more values and make number comparison faster. We will use
8-bit exponent as an example. In the figure above, we have 8-bit which
can represent $2^8=256_{10}$ different things. The bit patterns have no
intrinsic meaning, so we can use them to represent anything we want. The
green part shows the values those bit patterns represent when they are
treated as binary representations of unsigned integers. The problem is
that we want to represent negative values as well. One easy solution is
to treat the left most bit as the sign bit: 0 means positive and 1 means
negative, which result in two zeros $+0$ and $-0$. The blue part shows
what happens when we use the 2\'s complement scheme to represent both
positive and negative values using the same set of bit patterns. Recall
that the 2\'s complement scheme is often used to simply hardware design
so that we can use addition to do subtraction: a - b is the same as a +
(the 2\'s complement of -b). To get the 2\'s complement of a positive
integer is to invert all the bits and add 1 to it. Now any subtraction
can be done with a inversion and two additions. The problem with 2\'s
complement representation is that a \"larger\" looking pattern does not
necessarily represent a larger value. !This figure shows how the biased
exponent for IEEE 754
works.
The red part shows the biased exponent represented by the same set of
bit patterns. As you can see a \"larger\" looking pattern always
represent a larger value except for the all one patterns, which is used
to represent a special value. The advantage of the biased exponent
representation is that each value is represented by a unique pattern (no
two zeros) and comparing floating point numbers is easier. The exponent
is put before the fraction in IEEE 754 standard so that floating point
numbers can be compared by treating their bit patterns as unsigned
integers (much faster).

The following table shows some special values represented by special bit
patterns.

  biased expoent   fraction   numbers
  ---------------- ---------- --------------------
  00\...00         0          0
  00\...00         nonzero    denormalized
  11\...11         0          +/- infinity
  11\...11         nonzero    NaN (Not a Number)

Because the implicit/hidden 1 is always added to the fraction to get the
represented value a special pattern is needed to represent the zero
value. Now the result of a division by zero can be represented as +/-
infinity (division by zero in integer operation will crash your
program). $\sqrt{-4}$, $$ and $0/0$ can be represented as NaN, which
helps debugging your programs.

:   What is the IEEE 754 floating-point representation of this number:
    $-2.340625 \times 10^1$
:   What is the decimal equivalent of this IEEE 754 floating-point
    number: 1100 0000 1111 0000 0000 0000 0000 0000?
:   What is the largest IEEE 754 single precision floating-point number?

What are the downsides of floating-point or scientific representation?
With five digits we can represent $999.99_{10}$ precisely using fixed
point notation. However, when we use the following
scientific/floating-point notation $n.nn \times 10^{nn}$ the closest
value we can represent is $9.99 \times 10^{02}$ and the error is
$999.99-999=0.99$ - a loss of precision.

### Real v.s. Floating-point Number Lines

This figure illustrates
the different the number line for real numbers and that for floating
point numbers. The following observations can be made:

-   The real number line is continuous, dense, and infinite.
-   The floating-point number (representation) line is discrete, sparse,
    and finite.
-   A group of real numbers are represented by the same floating-point
    number (an approximation).
-   The sizes of groups get larger and larger as the floating-point
    numbers get larger.

Lets study a concrete example. With four decimal digits and a fixed
point representation ($nnn.n$) we can represent 0, 0.1, 0.2, 0.3, \...,
999.8, 999.9 with equal distance between the consecutive numbers. With a
floating-point representation ($+n.nn \times 10^{\pm n}$) , the smallest
value we can represent is $1.00 \times 10^{-9}=0.\underbrace{0...0}_8 1$
and the largest representable value is $1.11 \times 10^{+9}=1110000000$.
Now lets look at representable values by this floating-point number
format around some points on the number line:

-   Next to 0:
    $1.00 \times 10^{-9}=0.\underbrace{0...0}_8 1, 1.01 \times 10^{-9}=0.\underbrace{0...0}_8 101, 1.02 \times 10^{-9}=0.\underbrace{0...0}_8 102, ...$
    (the distance between consecutive numbers is 0.00000000001)
-   Next to 1:
    $1.00 \times 10^{0}=1, 1.01 \times 10^{0}=1.01, 1.02 \times 10^{0}=1.02, ...$
    (the distance between consecutive numbers is 0.01)
-   Next to 10:
    $1.00 \times 10^{1}=10, 1.01 \times 10^{1}=10.1, 1.02 \times 10^{1}=10.2, ...$
    (the distance between consecutive numbers is 0.1)
-   Next to 100:
    $1.00 \times 10^{2}=100, 1.01 \times 10^{2}=101, 1.02 \times 10^{2}=102, ...$
    (the distance between consecutive numbers is 1)
-   Next to 1000:
    $1.00 \times 10^{3}=1000, 1.01 \times 10^{3}=1010, 1.02 \times 10^{3}=1020, ...$
    (the distance between consecutive numbers is 10)

As you can see not every real number can be represented using the
floating-point format. The distribution of the representable values is
not uniform: it is denser around smaller values and more sparse (spread
out) around larger values, which means the larger a value we want to
represent the less precise we can do it.

What is the smallest IEEE 754 single precision number greater than 1?

### Machine Epsilon

Machine epsilon is defined to be
the smallest positive number which, when added to 1, gives a number
different from 1. The machine epsilon for floating-point format is
$b^{-(p-1)}$, where $b$ is the base (radix) and $p$ (precision) is the
number of digits for the fraction plus one.

What is the machine epsilon of IEEE 754 floating-point numbers?

