Rounding errors
Example
Show demo: “Waiting for 1”.
Determine the double-precision machine representation for 0.1
0.1 = 0.000110011 0011 … = 1.100110011 … "#
! ! ×2
𝑠=0
#×𝟐 Integer Fractional
part part
𝑓 = 100110011 … 00110011010
0.2 0 0.2
0.4 0 0.4 𝑚 = −4
0.8 0 0.8
1.6 1 0.6 𝑐 = 𝑚 + 1023 = 1019 = 01111111011 !
1.2 1 0.2
0.4 0 0.4 0 01111111011 10011 … 0011 … 0011010
0.8 0 0.8
1.6 1 0.6 (52-bit)
1.2 1 0.2 Roundoff error in its basic form!
Machine floating point number
• Not all real numbers can be exactly represented as a machine floating-point
number.
• Consider a real number in the normalized floating-point form:
𝑥 = ±1. 𝑏! 𝑏" 𝑏# … 𝑏$ …× 2%
• The real number 𝑥 will be approximated by either 𝑥& or 𝑥', the nearest two
machine floating point numbers.
0 𝑥0 𝑥 𝑥1 +∞
Without loss of generality, let’s see what happens when trying to represent a positive
machine floating point number:
Exact number: 𝑥 = 1. 𝑏% 𝑏& 𝑏' … 𝑏( …× 2)
𝑥$ = 1. 𝑏% 𝑏& 𝑏' … 𝑏( × 2) (rounding by chopping)
𝑥* = 1. 𝑏% 𝑏& 𝑏' … 𝑏( × 2) + 0.000 … 01× 2)
𝜖$
0 𝑥0 𝑥 𝑥1 +∞
Exact number: 𝑥 = 1. 𝑏% 𝑏& 𝑏' … 𝑏( …× 2)
𝑥$ = 1. 𝑏% 𝑏& 𝑏' … 𝑏( × 2)
𝑥* = 1. 𝑏% 𝑏& 𝑏' … 𝑏( × 2) + 0.000 … 01× 2)
𝜖$
Gap between 𝑥' and 𝑥&: 𝑥% − 𝑥" = 𝜖$ × 2$
Examples for single precision:
𝑥' and 𝑥& of the form 𝑞 × 2&!( : 𝑥' − 𝑥& = 2&## ≈ 10&!(
𝑥' and 𝑥& of the form 𝑞 × 2) : 𝑥' − 𝑥& = 2&!*≈ 2× 10&+
𝑥' and 𝑥& of the form 𝑞 × 2"( : 𝑥' − 𝑥& = 2&# ≈ 0.125
𝑥' and 𝑥& of the form 𝑞 × 2+( : 𝑥' − 𝑥& = 2#, ≈ 10!!
The interval between successive floating point numbers is not uniform: the interval is smaller as the
magnitude of the numbers themselves is smaller, and it is bigger as the numbers get bigger.
Gap between two successive machine floating point numbers
A ”toy” number system can be represented as 𝑥 = ±1. 𝑏4 𝑏5 ×26
for 𝑚 ∈ [−4,4] and 𝑏- ∈ {0,1}.
1.00 ! ×2& =1 1.00 ! ×2' =2 1.00 ! ×2! = 4.0
1.01 & ' !
! ×2 = 1.25 1.01 ! ×2 = 2.5 1.01 ! ×2 = 5.0
& ' !
1.10 ! ×2 = 1.5 1.10 ! ×2 = 3.0 1.10 ! ×2 = 6.0
1.11 & ' !
! ×2 = 1.75 1.11 ! ×2 = 3.5 1.11 ! ×2 = 7.0
1.00 ! ×2( = 8.0 1.00 ! ×2# = 16.0 1.00 ! ×2"' = 0.5
( # "'
1.01 ! ×2 = 10.0 1.01 ! ×2 = 20.0 1.01 ! ×2 = 0.625
1.10 ( # "'
! ×2 = 12.0 1.10 ! ×2 = 24.0 1.10 ! ×2 = 0.75
( # "'
1.11 ! ×2 = 14.0 1.11 ! ×2 = 28.0 1.11 ! ×2 = 0.875
1.00 ! ×2"! = 0.25 1.00 ! ×2"( = 0.125 1.00 ! ×2"# = 0.0625
"! "#
1.01 ! ×2 = 0.3125 1.01 ! ×2
"(
= 0.15625 1.01 ! ×2 = 0.078125
1.10 "! "#
! ×2 = 0.375 "( 1.10
1.10 ! ×2 = 0.1875 ! ×2 = 0.09375
1.11 "! "#
! ×2 = 0.4375 "( 1.11
1.11 ! ×2 = 0.21875 ! ×2 = 0.109375
Rounding
The process of replacing 𝑥 by a nearby machine number is called
rounding, and the error involved is called roundoff error.
Round Round Round Round
towards towards towards towards
−∞ zero zero +∞
−∞ 𝑥1 𝑥 𝑥0 0 𝑥0 𝑥 𝑥1 +∞
Round by chopping: 𝑓𝑙 𝑥 = 𝑥&
𝑥 is positive number 𝑥 is negative number
Round up (ceil) 𝑓𝑙 𝑥 = 𝑥% 𝑓𝑙 𝑥 = 𝑥"
Rounding towards +∞ Rounding towards zero
Round down (floor) 𝑓𝑙 𝑥 = 𝑥" 𝑓𝑙 𝑥 = 𝑥%
Rounding towards zero Rounding towards −∞
Round to nearest: either round up or round down, whichever is closer
Rounding (roundoff) errors
Consider rounding by chopping:
• Absolute error:
)l(𝑥) − 𝑥 ≤ 𝑥1 − 𝑥0 = 𝜖6 × 26
)l(𝑥) − 𝑥 ≤ 𝜖6 × 26
• Relative error:
)l(𝑥) − 𝑥 𝜖6 × 26
≤
𝑥 1. 𝑏4𝑏5𝑏> … 𝑏? …× 26
)l(𝑥) − 𝑥
≤ 𝜖6
𝑥
Rounding (roundoff) errors
𝑥0 𝑥 = 1. 𝑏4𝑏5𝑏> … 𝑏? …× 26 𝑥1
𝑥2 − 𝑥 𝑥2 − 𝑥
≤ 205>≈ 1.2×100@ ≤ 20A5≈ 2.2×1004B
|𝑥| |𝑥|
Single precision: Floating-point Double precision: Floating-point
math consistently introduces relative math consistently introduces
errors of about 100@. Hence, single relative errors of about 1004B.
precision gives you about 7 Hence, double precision gives you
(decimal) accurate digits. about 16 (decimal) accurate digits.
Iclicker question
Assume you are working with IEEE single-precision numbers. Find the smallest
number 𝑎 that satisfies
2C + 𝑎 ≠ 2C
A) 204D@E
B) 204D55
C) 20A5
D) 204A
E) 20C
Demo
Arithmetic with machine numbers
Mathematical properties of FP operations
Not necessarily associative:
For some 𝑥 , 𝑦, 𝑧 the result below is possible:
𝑥 + 𝑦 + 𝑧 ≠ 𝑥 + (𝑦 + 𝑧)
Not necessarily distributive:
For some 𝑥 , 𝑦, 𝑧 the result below is possible:
𝑧 𝑥+𝑦 ≠𝑧𝑥+𝑧𝑦
Not necessarily cumulative:
Repeatedly adding a very small number to a large number may do nothing
Floating point arithmetic (basic idea)
𝑥 = (−1)𝒔 1. 𝒇 × 2𝒎 = 𝒔 𝒄 𝒇
• First compute the exact result
• Then round the result to make it fit into the desired precision
• 𝑥 + 𝑦 = 𝑓𝑙 𝑥 + 𝑦
• 𝑥 × 𝑦 = 𝑓𝑙 𝑥 × 𝑦
Floating point arithmetic
Consider a number system such that 𝑥 = ±1. 𝑏4 𝑏5 𝑏> ×26
for 𝑚 ∈ [−4,4] and 𝑏- ∈ {0,1}.
Rough algorithm for addition and subtraction:
1. Bring both numbers onto a common exponent
2. Do “grade-school” operation
3. Round result
• Example 1: No rounding needed
𝑎 = 1.101 ×24
5
𝑏 = 1.001 4
5 ×2
𝑐 = 𝑎 + 𝑏 = 10.110 5 ×24 = 1.011 5 ×25
Floating point arithmetic
Consider a number system such that 𝑥 = ±1. 𝑏4 𝑏5 𝑏> ×26
for 𝑚 ∈ [−4,4] and 𝑏- ∈ {0,1}.
• Example 2: Require rounding
𝑎 = 1.101 5 ×2D
𝑏 = 1.000 ×2D
5
𝑐 = 𝑎 + 𝑏 = 10.101 5 ×2D ≈ 1.010 5 ×24
• Example 3:
𝑎 = 1.100 5 ×24
𝑏 = 1.100 5 ×204
𝑐 = 𝑎 + 𝑏 = 1.100 ×24 + 0.011 ×24 = 1.111 ×24
5 5 5
Floating point arithmetic
Consider a number system such that 𝑥 = ±1. 𝑏4 𝑏5 𝑏> 𝑏E ×26
for 𝑚 ∈ [−4,4] and 𝑏- ∈ {0,1}.
• Example 4:
𝑎 = 1.1011 5 ×24
𝑏 = 1.1010 ×24
5
𝑐 = 𝑎 − 𝑏 = 0.0001 ×24
5
Or after normalization: 𝑐 = 1. ? ? ? ? 5 ×20>
Unfortunately there is not data to indicate what the missing digits
should be. The effect is that the number of significant digits in the
result is reduced. Machine fills them with its best guess, which is
often not good (usually what is called spurious zeros). This
phenomenon is called Catastrophic Cancellation.
Cancellation
𝑎 = 1. 𝑎4𝑎5𝑎>𝑎E𝑎A𝑎B … 𝑎? …×264
𝑏 = 1. 𝑏4𝑏5𝑏>𝑏E𝑏A𝑏B … 𝑏? …×265
Suppose 𝑎 ≈ 𝑏 and single precision (without loss of generality)
𝑎 = 1. 𝑎4𝑎5𝑎>𝑎E𝑎A𝑎B … 𝑎5D𝑎5410𝑎5E𝑎5A𝑎5B𝑎5@ … ×26
𝑏 = 1. 𝑎4𝑎5𝑎>𝑎E𝑎A𝑎B … 𝑎5D𝑎5411𝑏5E𝑏5A𝑏5B𝑏5@ …×26
Lost due to
rounding
𝑓𝑙(𝑏 − 𝑎) = 0.0000 … 0001×26 = 1. ? ? ? ? ? ? … ? ?×20?16
𝑓𝑙 𝑏 − 𝑎 = 1.000 … 00×20?16
Not significant bits (precision lost, not due to 𝑓𝑙(𝑏 − 𝑎) but due to
rounding of a, 𝑏 from the beginning
Example of cancellation:
Loss of significance
Assume 𝑎 ≫ 𝑏. For example
𝑎 = 1. 𝑎4𝑎5𝑎>𝑎E𝑎A𝑎B … 𝑎? …×2D
𝑏 = 1. 𝑏4𝑏5𝑏>𝑏E𝑏A𝑏B … 𝑏? …×20C
In Single Precision (without loss of generality):
𝑓𝑙(𝑎) = 1. 𝑎4𝑎5𝑎>𝑎E𝑎A𝑎B … 𝑎55𝑎5>×2D
𝑓𝑙(𝑏) = 1. 𝑏4𝑏5𝑏>𝑏E𝑏A𝑏B … 𝑏55𝑏5>×20C
1. 𝑎4𝑎5𝑎>𝑎E𝑎A𝑎B𝑎@𝑎C𝑎N … 𝑎55𝑎5>×2D
+ 0.00000001𝑏4𝑏5𝑏>𝑏E𝑏A … 𝑏4E𝑏4A×2D
In this example, the result 𝑓𝑙 𝑎 + 𝑏 includes 15 bits of precision from
𝑓𝑙(𝑏). Lost precision!
Loss of Significance
How can we avoid this loss of significance? For example, consider the
function 𝑓 𝑥 = 𝑥 5 + 1 − 1
If we want to evaluate the function for values 𝑥 near zero, there is a
potential loss of significance in the subtraction.
For example, if 𝑥 = 100> and we use five-decimal-digit arithmetic
𝑓 100> = (100>)5 + 1 − 1 = 0
How can we fix this issue?
Loss of Significance
O!
Re-write the function as 𝑓 𝑥 = (no subtraction!)
O ! 1404
Evaluate now the function for 𝑥 = 100> using five-decimal-digit
arithmetic
(4D"# )! 4D"$
𝑓 100> = =
(4D"# )! 1404 5
Example:
If x = 0.3721448693 and y = 0.3720214371 what is the relative error in the computation of
(x − y) in a computer with five decimal digits of accuracy?
Using five decimal digits of accuracy, the numbers are rounded as:
Rl(x) = 0.37214 and Rl(y) = 0.37202
Then the subtraction is computed:
Rl x − Rl(y) = 0.37214 − 0.37202 = 0.00012
The result of the operation is: Rl x − y = 1.20000 ×10"! (the last digits are filled with spurious
zeros)
The relative error between the exact and computer solutions is given by
x − y − Rl x − y 0.0001234322 − 0.00012 0.0000034322
= = ≈ 3×10"!
| x−y | 0.000123432 0.000123432
Note that the magnitude of the error due to the subtraction is large when compared with the relative
error due to the rounding
|x − Rl x |
≈ 1.3×10")
|x|