Transcript Floating-point Arithmetic

Chapter 2
Floating-point
Computation
Prof. Chuan-Ming Liu
MCSE Lab, NTUT
TAWIAN
MCSE Lab, NTUT
1
Outline
• Positional Number System
• Floating-point Arithmetic
• Condition of Problems and Stability
of Algorithms
• Ill-Conditioned Problems
MCSE Lab, NTUT
2
Positional Number System
•
• Example:
MCSE Lab, NTUT
3
Positional Number System
•
• Example: Decimal system: (0.4213)10
numbers represented
real-world number set
MCSE Lab, NTUT
4
Positional Number System
• Conversion between number systems
– Example 1: binary to decimal
– Consider a polynomial
MCSE Lab, NTUT
5
Positional Number System
– Horner’s rule for polynomial:
MCSE Lab, NTUT
6
Positional Number System
– Example 2: decimal to binary
– Two methods:
MCSE Lab, NTUT
7
Positional Number System
• Method 1.
MCSE Lab, NTUT
8
Positional Number System
• Method 2.
2
2
2
418
0
0
209
1
10
0
010
0
0010
0
00010
104
2
52
2
26
2
13
2
5
2
3
1
100010
0
0100010
1
110100010
1
The whole process is the “reverse” of the Horner’s rule
MCSE Lab, NTUT
9
Positional Number System
– Not all decimal fractions are exactly
represented in the binary system.
– Example 1: (decimal to binary)
MCSE Lab, NTUT
10
Positional Number System
– Example 2: (binary to decimal)
MCSE Lab, NTUT
11
Positional Number System
– Terminating an infinite binary fraction.
MCSE Lab, NTUT
12
Positional Number System
• Fixed-Point Notation:
– Present a number by the positions
– E.g. (101.011)2=1*22+0+1*20+0*2-1+2-2+2-3
– Difficulty occurs when presenting very
large or very small numbers.
– The difficulty can be overcome by
scientific notation.
MCSE Lab, NTUT
13
Positional Number System
– E.g. 0.00000056 = 5.6 * 10-7
scale factor
Significant digits
– One key part to consider with is how
many digits to retain during computation.
– E.g.
• 1.23 + 15.6 = 16.83
• if using 3-digit computation
• 1.23 + 15.6 = 16.8
MCSE Lab, NTUT
14
Floating-point Arithmetic
•
MCSE Lab, NTUT
15
Floating-point Arithmetic
• In above floating-point representatoin
– δ1≠0 implies it is a normalized floatingpoint number
– e is the exponent.
– δ1 δ2…δt is the mantissa (or fraction).
MCSE Lab, NTUT
16
Floating-point Arithmetic
• Usually,
• The floating-point numbers are not
uniformly distributed on the real line.
MCSE Lab, NTUT
17
Floating-point Arithmetic
•
MCSE Lab, NTUT
18
Floating-point Arithmetic
– The floating-point numbers in a given
group βe are
MCSE Lab, NTUT
19
Floating-point Arithmetic
– The number of floating-point numbers in
a group is
• By counting
(+ or -)
t-1
• By spacing
MCSE Lab, NTUT
20
Floating-point Arithmetic
– The total number of floating-point
numbers in the system is
• The number with largest magnitude is
• The number with smallest magnitude is
MCSE Lab, NTUT
21
Floating-point Arithmetic
• Example:
MCSE Lab, NTUT
22
Floating-point Arithmetic
• How to represent an arbitrary real
number in the floating-point system
MCSE Lab, NTUT
23
Floating-point Arithmetic
– chopping
MCSE Lab, NTUT
24
Floating-point Arithmetic
– rounding
MCSE Lab, NTUT
25
Floating-point Arithmetic
MCSE Lab, NTUT
26
Floating-point Arithmetic
– hence,
–
MCSE Lab, NTUT
27
Floating-point Arithmetic
• Example:
MCSE Lab, NTUT
28
Floating-point Arithmetic
• Example:
MCSE Lab, NTUT
29
Floating-point Arithmetic
MCSE Lab, NTUT
30
Floating-point Arithmetic
Conclusion:
largest magnitude number add last.
MCSE Lab, NTUT
31
Condition of Problems and
Stability of Algorithms
• Poor accuracy depends on either the
problem or the algorithm.
– The problem can be ill-conditioned :
small perturbations in the input could
lead to large perturbations in the output.
– The algorithm may be poorly designed:
unstable.
MCSE Lab, NTUT
32
Condition of Problems and
Stability of Algorithms
– Example: (using 3-digit with chopping)
MCSE Lab, NTUT
33
Condition of Problems and
Stability of Algorithms
MCSE Lab, NTUT
34
Condition of Problems and
Stability of Algorithms
– Compare the result with the exact
solution!!
The error comes from that we cancel all
the significant digits and have a result
heavily contaminated with rounding
errors.
– Example: (using 4-digit rounding)
MCSE Lab, NTUT
35
Condition of Problems and
Stability of Algorithms
MCSE Lab, NTUT
36
Condition of Problems and
Stability of Algorithms
MCSE Lab, NTUT
37
Condition of Problems and
Stability of Algorithms
MCSE Lab, NTUT
38
Condition of Problems and
Stability of Algorithms
• Cancellation
– Error-producing involves the
cancellation of significant digits due to
the substraction of nearly equal
numbers.
– Recall how to avoid cancellation we can
use rationalization to remedy the error
for the smaller root.
MCSE Lab, NTUT
39
Condition of Problems and
Stability of Algorithms
– The smaller root can be expressed
alternatively by
MCSE Lab, NTUT
40
Condition of Problems and
Stability of Algorithms
– No method can remedy the solution for
the previous example. (using chopping)
– A stable algorithm for computing the
roots of a quadratic ax2+bx+c=0 may be
outlined as
MCSE Lab, NTUT
41
Ill-Conditioned Problems
• the ill-conditioning of a problem is
measured by the condition number K.
(the larger K is the more illconditioned is the problem.)
•
MCSE Lab, NTUT
42
Ill-Conditioned Problems
• From Taylor series,
MCSE Lab, NTUT
43
Ill-Conditioned Problems
• Example:
MCSE Lab, NTUT
44
Ill-Conditioned Problems
MCSE Lab, NTUT
45
Ill-Conditioned Problems
MCSE Lab, NTUT
46
Ill-Conditioned Problems
• Ill-conditioned problem
MCSE Lab, NTUT
47
Ill-Conditioned Problems
• A stable algorithm for an illconditioned problem is an algorithm
for which the computed solution is
near the exact solution of another
slightly perturbed problem.
MCSE Lab, NTUT
48