Transcript Objects

Numerics
Representation and Errors
Copyright © 2003-2012 Curt Hill
Integers
• Typically stored as a series of bits
• Two’s complement binary
• Each bit represents a zero or one
– Similar to a light switch
– Only two states
• Binary is base 2
Copyright © 2003-2012 Curt Hill
Decimal
•
•
•
•
In base 10 the 10 occurs twice
The number of digits
The power to which a place is raised
In decimal each digit may be one of
10 possibilities, 0 - 9
• Each digit is multiplied by 10 raised
to some power
Copyright © 2003-2012 Curt Hill
A Decimal Number
4,809
9  100=
9
0  101=
0
8  102= 800
4  103= 4000
Copyright © 2003-2012 Curt Hill
Binary is just the same
•
•
•
•
In base 2 the 2 occurs twice
The number of digits
The power to which a place is raised
In binary each digit may be one of
two possibilities, 0 or 1
• Each digit is multiplied by two raised
to some power
Copyright © 2003-2012 Curt Hill
A Binary Number
101101
1  20= 1
0  21= 0
1  22= 4
1  23= 8
0  24= 0
1  25= 32
45
Copyright © 2003-2012 Curt Hill
Binary and other bases
• We use it because it is the only base
easy to implement in hardware
• We almost never display it
– Binary is quite bulky
• We often use other bases for certain
displays
– Octal, base 8
– Hexadecimal, base 16
– Converting these to and from binary is
quite simple
– Conversion to decimal is much harder
Copyright © 2003-2012 Curt Hill
Integers
• Come in several sizes:
• 16 bit
– -32768 to 32767
• Most common is 32 bit
– Largest integer is (231)-1
– -2,147,483,648 to 2,147,483,647
– There is always one more negative than
positive
– Zero is taken from positives
• Large integers may be 64 bit
– Largest is 9,223,372,036,854,780,000
Copyright © 2003-2012 Curt Hill
Integer Errors
• Integers are only subject to one error
• Overflow
• Add 1 to largest positive integer and
result is smallest negative integer
• Subtract 1 from largest (in absolute value)
negative and result is largest positive
• Similar to clock arithmetic, except there
are positives and negatives
Copyright © 2003-2012 Curt Hill
Another Look at Overflow
Copyright © 2003-2012 Curt Hill
Real Numbers
• Real numbers (float, double) are
actually two numbers
• Similar to scientific notation:
2.543 108
• The 2.543 is called the mantissa
• The 8 is called the exponent
• The 10 is the base
– Not represented, since always a 2 or
some other constant
Copyright © 2003-2012 Curt Hill
Real Number Errors
• Real numbers are subject to a
variety of errors
– Some quite subtle
• In order to demonstrate these we
will model a computation using three
digit arithmetic
– Two digit of mantissa
– One digit of exponent
– Base of 10
Copyright © 2003-2012 Curt Hill
3 Digit Arithmetic Game
•
•
•
•
A perfect circle is found in nature
We want to know its area
The formula is a =πr2
The radius (r) is:
11.4962790000000000
• Unfortunately, we measured this
radius to be:
11.495
• Which becomes 11E0 on our
machine
Copyright © 2003-2012 Curt Hill
Computing…
Take the 11 E 0 and square
11 E 0
11 E 0
121 E 0
The121E0 has too many
digits, adjust:
12 E 1
Multiply timesπ
12 E 1
31 E -1
372 E 0
Adjust again
37 E 1
Copyright © 2003-2012 Curt Hill
What happened?
• This exercise demonstrates several
important sources of error
• It is never the case that if its close
its accurate
– Which is what most believe
• The three demonstrated errors are
– Observational
– Representational
– Computational
Copyright © 2003-2012 Curt Hill
The Results
• The real value should be
415.2060805
• We ended up with 370
• About 12% error
• One half of a significant digit
Copyright © 2003-2012 Curt Hill
Observational Error
• We can never measure anything
completely accurately
– To infinite precision
• The introduced error in this case is
0.02%
• This is not a problem for integers
• The Olympics have a problem with
this, in measuring to hundredths of a
second
Copyright © 2003-2012 Curt Hill
Olympic Observational Error
• LA 1984 Women’s 100 M. Freestyle
– Carrie Steinseifer and Nancy Hogshead
won in 55.92
– Both received gold – no silver awarded
• Sydney 2000 Men’s 50 M. Freestyle
– Anthony Ervin and Gary Hall Jr. 21.98
• London 2012 two events, four silvers
– Men’s 200 M. Freestyle
• Taehwan Park and Yang Sun
– Men’s 100 M. Butterfly
• Chad le Clos and Evgeny Korotyshkin
Copyright © 2003-2012 Curt Hill
Representational Error
• The measurement cannot be represented
accurately on this machine
• 11.495 to 11 causes an error amounting
to 8.4% in addition to previous
• Truncatingπwill cause an additional 1.3%
• This will be minimized but not eliminated
with many more than 2 digits of precision
• This is the only integer arithmetic error
– Overflow
• There is more of this than you might think
Copyright © 2003-2012 Curt Hill
Computational Error
• A digit was lost twice
– 121 to 120
– 372 to 370
• We may round or truncate this but
we still lose information
• This will account for another 1.3%
error in addition to the previous
• Another problem that integer
arithmetic does not have
Copyright © 2003-2012 Curt Hill
Representational Error
Revisited
• Recall from grade school days there are
three types of decimal numbers:
– Rational
• Terminating
• Repeating
– Irrational
• πcould not be represented since it has
infinite digits
• For computational purposes, irrationals
are no worse than repeating decimals
Copyright © 2003-2012 Curt Hill
Repeating decimals
• Many fractions convert to repeating
decimals
• 1/3 repeats with one digit 0.33333…
• 1/11 has two digits 0.09090909…
• 1/7 repeats with 6: .142857 142857…
• As does 1/13: .076923 076923…
Copyright © 2003-2012 Curt Hill
Terminating decimals
•
•
•
•
•
•
•
•
•
Terminating decimals are what we want
They end in an infinite number of zeros
1/2 is 0.50
1/4 is 0.25
1/5 is 0.2
1/8 is 0.125
1/10 is 0.1
No representational errors with these
Or is there?
Copyright © 2003-2012 Curt Hill
Terminating and Repeating
• Why does 1/5 terminate and 1/3
repeat?
• It all has to do with the prime factors
of the denominator
– If the prime factors only contain 2s and
5s the number terminates, otherwise it
repeats
– These are the prime factors of 10
Copyright © 2003-2012 Curt Hill
Terminator
• A number terminates if its
denominator has only the prime
factors of the base
• 1/7 terminates in base 7 and base 14
but not in base 10 or base 2
• What base does a computer use?
• Binary – base 2
• We have representational error for
any fraction whose denominator has
something other than two for a
prime factor
Copyright © 2003-2012 Curt Hill
Example: Money
• Cents are always fractions, with a
denominator of 100
– 100 has prime factors of 2 and 5
• Only the cent amounts of .00, .25,
.50 and .75 reduce to having a
denominator of 2 or 4
• Thus 96% of all monetary amounts
have representational error
Copyright © 2003-2012 Curt Hill
Computational Error Revisited
• Certain operations produce more or less
error
• The subtraction of two values that are
close in value has a deleterious effect
• The most significant and most accurate
digits cancel each other
• This leaves only the most error prone
digits left
Copyright © 2003-2012 Curt Hill
Multiplication and Division
• Generally multiplication and division
are better at preserving significant
digits than addition and subtraction
– The result has the precision of the least
precise value
• The result of multiplication has the
sum of digits
– Most of these are thrown away
• Errors are cumulative
• Once we have error digits we cannot
get rid of them
Copyright © 2003-2012 Curt Hill
Examples
0.95
0.20348
0.83
-0.20321
0.0285
0.00027
+ 0.760
0.7885
Most accurate
digits are lost
The most accurate
digits contribute most
Copyright © 2003-2012 Curt Hill