Transcript 5.2 Errors

5.2 Errrors
Why Study Errors First?
• Nearly all our modeling is done on digital
computers (aside: what would a non-digital
analog computer look like?)
Analog Computer for Fitting a
Line to a Set of Points
Why Study Errors First?
• Nearly all our modeling is done on digital
computers (aside: what would a non-digital
analog computer look like?)
• A better set of terms is discrete vs.
continuous (recall the discrete/continuous
distinction from 1.2).
• Discrete devices have finite precision - we
cannot represent all the different values we’d
like.
• Finite precision leads to errors
Finite Precision with Bits
•
•
•
•
Bit = value of 0 or 1 (aside: why base 2 ?)
With n bits, we can distinguish 2n different values
E.g., with three bits we get eight possible values.
These values can correspond to anything we want
to represent…
000
001
010
011
100
101
110
111
0
1
2
3
4
5
6
7
A
B
C
D
E
F
G
H
Greg
Wade
Sam
Jordan
Mark
Jason
Gaurav
Alex
Floating-Point Numbers
• History: origins of computers in finance
(banking) and military (physics).
• Financial calculations are (usually) fixedpoint: the decimal place is fixed in one
position, two digits from right: $129.95, $0.59,
etc.
• In physical calculations, we need the decimal
place to “float”: 3.14159, 0.333,
6.0221415 × 1023 , etc.
Exponential Notation
• Format: Mantissa X 10Exponent, or a X 10n
• Abbreviated a e n or a E n; for example,
6.0221415e23
• Mantissa (a.k.a. significand, a.k.a. fractional part)
is a floating-point number; exponent is an integer.
• So someone has to decide the precision:
– IEEE 754 standard: with 64-bit numbers, use 52 bits for
mantissa, 11 for exponent, 1 for sign (+ or −)
• Rough conversion: 3 bits  1 decimal digit (why?)
E.g., 53 bits  16 decimal digits of precision
Normalized Notation
• Normalization is a common operation: e.g.,
percentage normalizes everything to 100:
2/4 = 75/50 = 50%
• Scientists usually prefer to normalize to 1:
2/4 = 75/150 = 0.5
• So a normalized number in exponential notation
has the decimal place immediately before the first
nonzero digit:
.314159e1,
.60221415e24,
etc.
• Significant digits of a normalized floating-point
number are all of the digits except leading zeros.
Precision and Magnitude
• Precision is the number of significant
digits.
• Magnitude is the power of 10.
.314159e1
6 digits of
precision
Magnitude = 1
Quick Review Question 1
•
For the number 0.0004500, give
a. the significand in normalized exponent
notation
b. the magnitude in normalized exponent
notation
c. the precision
Absolute and Relative Error
• If correct is the answer and result is the
result obtained, then
absolute error = | correct - result |
relative error = (absolute error)
| correct |
= (absolute error)
| correct |
X 100%
Truncation
• To truncate a normalized number to k
significant digits, eliminate all digits of
the significand beyond the kth digit.
• E.g., .314159 truncated to 5 significant
digits = .?????
Truncation
• To truncate a normalized number to k
significant digits, eliminate all digits of
the significand beyond the kth digit.
• E.g., .314159 truncated to 5 significant
digits = .31415
• Relative error = | correct - result | X 100%
| correct |
Truncation
• To truncate a normalized number to k
significant digits, eliminate all digits of
the significand beyond the kth digit.
• E.g., .314159 truncated to 5 significant
digits = .31415
• Relative error = | .314159 - .31415 | X 100%
| .314159 |
Truncation
• To truncate a normalized number to k
significant digits, eliminate all digits of
the significand beyond the kth digit.
• E.g., .314159 truncated to 5 significant
digits = .31415
• Relative error =
.00009
X 100%
.314159
Truncation
• To truncate a normalized number to k
significant digits, eliminate all digits of
the significand beyond the kth digit.
• E.g., .314159 truncated to 5 significant
digits = .31415
• Relative error = 0.0286479 %
Rounding
• To round a normalized number to precision k,
consider the (k+1)th significant digit d. If it is less
than 5, round down the normalized number by
truncating the significand to k significant digits. If
d is greater than or equal to 5, round up the
normalized number by truncating the significand
to k significant digits and then adding 1 to the kth
significant digit of the significand, carrying as
necessary to digits on the left.
Quick Review Question 3
•
Round each of the following so that the
significand has a precision of 2:
a. 0.93742e-5
b. 0.93472e-5
c. 0.93572e-5
Round-off Error
• Round-off error is the problem of not having
enough bits (or digits) to store an entire floatingpoint number and approximating the result to the
nearest number that can be represented.
• E.g., 1/3 = 0.333 ≠ 0.3 ≠ 0.33 ≠ 0.333 ≠ etc.
Avoiding Round-off Error
• Some values (1/3) will always result in roundoff;
however, we can help reduce error:
– When adding numbers whose magnitudes are drastically
different, accumulate smaller number before combining
them with larger ones.
– When multiplying and dividing, perform all multiplications
in the numerator before dividing by the denominator.
Avoiding Round-off Error
• E.g. consider computing (x/y)z on a machine with
three significant digits of precision, where
x = 2.41
y = 9.75 z = 1.54
(x / y)z = (2.41 / 9.75)(1.54) = (0.247)(1.54) = 0.380
But (x / y)z = (xz) / y:
(xz) / y = ((2.41) )(1.54)) / 9.75 = 3.71 / 9.75 = 0.381
Overflow and Underflow
• Overflow is an error condition that occurs when
there are not enough bits to express a value in a
computer.
• Underflow is an error condition that occurs when
the result of a computation is too small for the
computer to represent.
Overflow and Underflow in
Excel
Looping and Error
Propagation
• A loop is a segment of code [computer instructions]
that is executed repeatedly.
• Accumulating values in a loop (repeatedly) can
produce error
• E.g., Patriot Missile failure in 1991 Gulf War
Patriot Missile Failure
• Patriot’s internal clock measured time in 1/10 of a
second.
• Each tick of the clock added 1/10 s to current time.
• But 1/10 cannot be represented in a finite number
of bits (just as 1/3 cannot be represented in a finite
number of decimal digits)
Representing Fractions in Binary
• Consider ordinary Base-10 notation: what does
e.g. 1205.91410 mean?
1
2
103
0
102
5 .
101
100
9
.
1
4
10-1
10-2
10-3
• Binary works the same way; e.g., what is 101.012?
1 0 1 .
0 1
2-2
= 4 + 1 + 1/4 = 5.025
22 21 20
.
2-1
Patriot Missile Failure
• Each one-tenth increment produced an error of
about .000000095 seconds.
• After ten hours of running Patriot’s computer:
10 hr
60 min
1 hr
60 sec .000000095 sec
1 min 1 sec
= 0.34 sec
• Scud travels 1,676 meters / sec. So error =
1676 meters 0.34 sec
1 sec
= 570 meters
• Result Patriot missed Scud , 28 Americans died
Looping and Error
Propagation in Excel*
Enter values:
Highlight;
click corner;
drag downward:
+
*Courtesy of Bob Panoff
See apparent
uniform
sequence:
Double click for
actual values:
Avoiding Error Propagation in
Excel*
Enter first value;
highlight rest:
*Courtesy of Bob Panoff
Do Fill/Series:
Other Ways to @&^% Up?
Other Ways to @&^% Up?
LA Times, 1 October 1999