errors in computer science lessons as a motivation Prof J

Report
TWO EXAMPLES AS MOTIVATION
FOR THE STUDY OF COMPUTER
ERRORS
Prof Jorge Lemagne
Faculty of Science, Bindura University
[email protected], [email protected]
Summary
Introduction
Example 1: The Patriot Missile Failure
Example 2: An apparently contradictory result
Exhortations
2
Introduction. To encourage students to
study Mathematics
For many people, Mathematics is a boring discipline.
They ignore its fundamental role in Science,
Technology and in general, in life.
Showing the students these relationships would
motivate and encourage them to study this discipline.
3
9 strategies for increasing student
motivation in Math (Posamentier
[2013]) (1)
S1. Call attention to a void in student’s knowledge.
S2. Show a sequential achievement.
S3. Discovering a pattern
S4. Present a challenge.
S5. Entice the class with a “Gee-Whiz” mathematical result.
4
9 strategies for increasing student
motivation in Math (Posamentier
[2013]) (2)
S6. Indicate the usefulness of a topic.
S7. Use recreational mathematics.
S8. Tell a pertinent story.
S9. Get students actively involved in justifying
mathematical curiosities.
5
Preceding strategies might be applied
• In this talk: Two examples as motivation for
the study of computer errors.
• In both, all S1 to S9 might be applied.
• Especially “S6. Indicate the usefulness of a
topic” can be carried out by introducing “a
practical application of genuine interest to
the class at the beginning of a lesson.”
6
Inevitable presence of error
• Scientific computing: Discipline concerned
with the development and study of numerical
algorithms for solving mathematical problems
that arise in science and engineering.
• The most fundamental feature of numerical
computing is the inevitable presence of error.
7
Consequences of careless numerical
computing
• Scientists and engineers often wish to believe
that the numerical results of a computer
calculation, especially those obtained as output
of a software package, contain no error: at least
not a significant or intolerable one.
• But careless numerical computing does
occasionally lead to disasters.
• Among them one of the most spectacular was the
Patriot missile failure.
8
Summary (1)
 Introduction
 Example 1: The Patriot Missile Failure
Example 2: An apparently contradictory result
Exhortations
9
Example 1: The Patriot Missile Failure
February 25, 1991 (Gulf War), Dharan, Saudi Arabia:
An American Patriot Missile was supposed to
track and intercept an incoming Iraqi Scud missile.
10
To produce the time in seconds
• In Patriot computer, the system's internal
clock measured the time in tenths of second.
• So it was multiplied by
in seconds.
1
10
to produce the time
11
But, what was actually stored?
1
10
In binary notation, the expansion of
is nonterminating:
0.110 = 0.00011001100110011001100 … 2
1
10
However the multiplication by was performed
using a 24 bit fixed point register, so it stored
instead
0.00011001100110011001100 2 ≈ 0.110
12
Error
Consequently, it is introduced an error
 = 0.11001100 … 2 ∙ 2−23 ≈ 9.5 ∙ 10−8 ,
called rounding error (in this case by chopping).
13
Total time error
The Patriot battery was up around 100 hours.
Multiplying by the number of tenths of a second
in 100 hours gives
 = 9.5 ∙ 10−8 × 100 × 60 × 60 × 10 = 0.34,
the time error (in seconds).
14
The distance travelled
• A Scud travels at about 1676 meters per
second.
• So travels more than half a kilometre in this
time (0.34 sec).
• This was far enough that the incoming Scud
was outside the "range gate" that the Patriot
tracked.
15
Consequence
• As a consequence, the Patriot failed to track
and intercept the incoming Iraqi Scud missile.
• The Scud struck an American Army barracks,
killing 28 soldiers and injuring around 100
other people.
16
Cause of this disaster
• The small rounding error , when multiplied
by the large number giving the time in tenths
of a second, led to a significant error , due to
the magnified rounding error.
• It turns out that the cause of this disaster was
an inaccurate calculation of the time since
boot due to computer arithmetic errors.
17
Summary (2)
 Introduction
 Example 1: The Patriot Missile Failure
 Example 2: An apparently contradictory result
Exhortations
18
Example 2: An apparently
contradictory result
• The second example of this talk is far less
tragic than the preceding one.
• We initially propose you to make a simple
experiment.
• It will be used an environment that is suitable
for technical computing: MATLAB (MathWorks
[2013]). We open the application:
19
MATLAB Presentation
20
Simple experiment
>> 0.3*4==1.2
ans =
1
>> 0.4*3==1.2
ans =
0
>>
Why?
(To be explained)
21
Traditionally
• We are used to perform calculations using
decimal notation.
• Moreover, in some cases, they are done
exactly.
• That happens when we perform
0.3 ∙ 4 = 0.4 ∙ 3 = 1.2
22
Scientific calculations
• However, scientific calculations are not exact
or use decimal notation.
• Why?
• Scientific calculations are usually carried out in
floating point arithmetic.
• Actually, this is just a generalization of what is
called scientific notation.
23
Scientific notation
• Essentially, as we know, its form has mantissa
and exponent. For example:
3748 = 0.3748 ∙ 104
0.000001643 = 0.1643 ∙ 10−5
−83.92 = −0.8392 ∙ 102
• Since decimal notation is used, the base is 10,
and each mantissa digit is between 0 and 9.
24
Significant digits
3748 = 0.3748 ∙ 104
0.000001643 = 0.1643 ∙ 10−5
−83.92 = −0.8392 ∙ 102
In the three examples the mantissa has 4 digits,
or equivalently, each number has 4 significant
digits.
25
Floating point number
 = ± . 1 2 … 

∙


• In general, the base is , and 1 , 2 , … , 
are digits between 0 and  − 1 (normally
1 ≠ 0).
• For most computers,  = 2.
• The reason is mainly technological.
26
Can we represent exactly 1.2 in
floating point with  = 2?
• Using the binary notation:
1.210 = 1.0011 0011 0011 … 2
= 0.10011 0011 0011 … 2 ∙ 21
• Observe that the mantissa has infinitely many
binary digits or bits.
• So, again, we need to approximate (round) the
number.
• This means to take only  digits.
27
IEEE (Institute of Electrical and
Electronics Engineers)
• Standard 754, published in 1985, defines a
binary floating point arithmetic system.
• Values of : 24 (simple precision), 53 (double
precision) and 64 (extended precision).
• Correspondingly, the precision in decimal
system is about 7, 15 or 19, obtained
multiplying by log10 2 ≈ 0.3
28
For the sake of clarity
We consider a computer with  = 5, so instead of
1.210 = 0.10011 0011 0011 … 2 ∙ 21
we have
1.210 ≈ 0.10011 2 ∙ 21
Or equivalently:
1.210 ≈ .  
Hence some error is committed.
Observe the number that is actually represented.
29
The other data
Similarly, the other data represented in our
computer are the following:
0.310 ≈ 0.010011 2
410 = 100 2
0.410 ≈ 0.011010 2
310 = 11 2
30
Rounding again
• Now, we perform the multiplications with
these rounded numbers.
• Each multiplication gives a number with 10
significant digits.
• Hence, it must be rounded again.
31
Results
Thus, we have the following results:
1.2 ≈ 1.0011 2
0.3 ∙ 4 ≈ 1.0011 2
0.4 ∙ 3 ≈ 1.0100 2
Therefore, in our computer:
0.3 ∙ 4 = 1.2
But
0.4 ∙ 3 ≠ 1.2
32
Why unexpected results?
In our example, when 0.3, 1.2 and 0.4 are represented
in the computer, some error is committed.
Afterwards, when the multiplications 0.3 ∙ 4 and 0.4 ∙
3 are performed, additional error is committed.
That is why we obtain unexpected results.
33
In general, laws of arithmetic do not
hold on scientific computing
For some numbers ,  and :
 +  +  ≠  + ( + )
  ≠  
  +  ≠  + 
+ =:  ≠0
In arithmetic of  = 3 decimal digits:
1 
1 + 0.001 + 0.001 + ⋯ + 0.001=
2 
(1000 )
34
Further information
To deepen on floating point arithmetic and
analysis of error:
Conte and de Boor [1980] and
Heath [2002] (for instance)
35
Summing up
In general, on scientific computing the
representation of numbers is not exact.
Nor the result of arithmetic operations is
exact.
Hence, most laws of arithmetic do not
hold on scientific computing.
36
Summary (3)
 Introduction
 Example 1: The Patriot Missile Failure
 Example 2: An apparently contradictory result
 Exhortations
37
So, what have we seen?
• Two examples as motivation for the study of
computer errors.
• These may be startling to readers who are not
familiarized with computer arithmetic.
38
You are exhorted to
Verify the previous results, and to experiment
computationally.
Learn conversion from decimal to binary notation.
Study floating point arithmetic and analysis of error.
These are ways for developing skills.
39
It is also recommended these
examples to be used
As motivation in Scientific Computing and Numerical
Analysis courses, and a vocational guidance to O and A
level students.
To show the students (once more) the strong relationships
between Mathematics and Computer Science.
To illustrate some of the difficulties and challenges to be
faced when new technologies are used.
40
Bibliography (1)
[1] Arnold, D. N. (2000): The Patriot Missile Failure,
http://www.ima.umn.edu/~arnold/disasters/
disasters.html
[2] Conte, S. D. and de Boor, C. (1980): Elementary
Numerical Analysis, an Algorithmic Approach,
Third Edition, McGraw-Hill Book Company,
ISBN 0-07-012447-7
[3] Heath, M. T. (2002): Scientific Computing: An
introductory survey, Second edition, The
McGraw-Hill Companies, Inc.,
ISBN 0-07-239910-4, ISBN 0-07-112229-X (ISE)
41
Bibliography (2)
[4] Higham, N. J. (1996): Accuracy and stability of
numerical algorithms, SIAM, Philadelphia,
ISBN O-8987 l-355-2 (pbk.)
[5] MathWorks, Inc., The (2013): MATLAB R2013a
[6] Posamentier A. (2013): 9 Strategies for
Motivating Students in Mathematics,
EDUTOPIA, The George Lucas Educational
Foundation, http://www.edutopia.org/blog/
9-strategies-motivating-students-mathematicsalfred-posamentier
42

similar documents