Lab 8 Inexact Arithmetic
Purpose: To explore inexact (floating point) arithmetic
Warmup
a + b = b + a
(a + b) + c = a + (b + c)
Exercise 1 Design a function sum-R->L that sums a list of numbers from right to left. (Hint: This is really easy if you use the right loop function...)
Exercise 2 Design a function sum-L->R that sums a list of numbers from left to right. (Hint: Also really easy if you use the right loop...)
Write tests to see if your two functions agree. Come up with some lists of numbers and see whether(= (sum-L->R a-list) (sum-R->L a-list))
ever fails to hold.
Exercise 3 Test your functions on the following data:
(define janus (list 31.0 #i2e+34 #i-1.2345678901235e+80 2749.0 -2939234.0 #i-2e+33 #i3.2e+270 17.0 #i-2.4e+270 #i4.2344294738446e+170 1.0 #i-8e+269 0.0 99.0)) The number #i2e+34 means 2 × 1034.What numbers do (sum-L->R janus) and (sum-R->L janus) compute?
Has DrRacket gone crazy?
Well, sort of... or at least those numbers have. The #i in front of them means inexact. To save space and time, we often compute with inexact approximations to numbers rather than precise values. (There are many numbers whose precise value can’t even be represented in finite space!)
The unfortunate side effect is that even simple operations like addition can give wildly inaccurate answers. When adding up janus, for instance, we got a small positive number one time and a huge negative number the other! Care to guess which one was the right answer? Was either one the right answer?
Would you be happy if your bank represented your account balance using this kind of number? What about your stock broker? What would happen to the bits of money that get rounded away? (At least two popular movies have addressed this issue.)
Precision banking aside, inexact numbers are useful for many applications of computing. In the rest of this lab we will explore how they work.
Representing inexact numbers
How much memory does a boolean need? Very little.
How much memory does a string need? Probably proportional to its length.
How much memory does a number need? Probably proportional to the number of its digits.
How many digits in 1/3? How many in π? ...
To compute with these numbers we will need to come up with a smaller representation. Let’s start simple: limit the number of digits. For simplicity, we choose two-digit numbers. Consider some examples of adding two-digit numbers:
00 + 00 = 00
20 + 35 = 55
50 + 50 = 100—
oops!
The last value has flowed over its bound of two digits. We call this an overflow. We’d better adjust our data definition to account for overflows.
; An Inexact1 is one of: ; - an Integer between 00 and 99 (inclusive) ; - 'overflow
Exercise 4 Design a function inexact-plus that adds two inexact numbers using the data definition fofr Inexact1. Use the following tests:
(equal? (inexact-plus 'overflow 'overflow) 'overflow) (equal? (inexact-plus 'overflow 33) 'overflow) (equal? (inexact-plus 25 'overflow) 'overflow) (equal? (inexact-plus 20 35) 55) (equal? (inexact-plus 50 50) 'overflow)
Better inexact numbers
The distance from the earth to the sun in meters—
too big The average distance between the electron and proton in a hydrogen atom in meters—
too small The exchange rates of currencies—
too small, slightly
1 × 106 = 1,000,000
9.09 × 10-3 = .00909
(define-struct inex (mant expt)) ; An Inexact2 is one of: ; - 'overflow ; - (make-inex Mantissa Exponent) ; where Mantissa and Exponent are integers between 00 and 99 (inclusive)
Exercise 5 Write the closest possible representations of the following numbers as "Inexact2" values:
0
100
120
123
1,000
1,000,000
1,000,000,000,000,000
1,000,235,711,131,719
1 × 1050
1 × 10100
10 × 10100
999
992
Some numbers (e.g., 0 and 100) can have multiple representaitons
We can still have overflows
We often have to omit less significant digits
-1 × 106 = -1,000,000
2.5 × 10-5 = .000025
-8.25 × 10-2 = -.0825
; An Inexact3 is one of: ; - 'overflow ; - (make-inex Mantissa Exponent) ; where Mantissa and Exponent are integers between -99 and 99 (inclusive)
Exercise 6 Write down representations of the following numbers as "Inexact3" values:
0
1
-1
1/2
-1/2
5.5
4/3
-1/3
-1 × 10100
-1 × 10101
one millionth
one billionth
one quadrillionth
1/(1025)
1/(1050)
1/(10100)
As before, we can have overflow (even with negative numbers)
when the exponent becomes too large,
and we can lose precision when the mantissa can’t store all the lower-order digits.
But now we can also have underflow
when the exponent becomes too small—
; An Inexact4 is one of: ; - 'overflow ; - 'underflow ; - (make-inex Mantissa Exponent) ; where Mantissa and Exponent are integers between -99 and 99 (inclusive)
Exercise 7 Write the template for processing Inexact4 data.
Exercise 8 Write the template for processing two pieces of Inexact4 data. This is useful for writing arithmetic functions like inexact-equals?, inexact-plus, and inexact-times.
For the remaining problems, you may not want to use any numbers larger than four digits—
Exercise 9 Design a function build-inex that constructs an Inexact4 from a list of digits ordered from least to greatest significance. For example,(list 4 3 2 1) represents 1,234
Use the following tests:
(equal? (build-inex empty) (make-inex 0 0)) (equal? (build-inex '(1)) (make-inex 1 0)) (equal? (build-inex '(0 1 2 3)) (make-inex 32 2)) (equal? (build-inex '(3 2 1 0)) (make-inex 12 1))
Exercise 10 Design a function inex<=? that compares two inexact numbers.
Exercise 11 Design a function inex* that multiplies two inexact numbers.
Exercise 12 Design a function inex+ that adds two inexact numbers.
Exercise 13 (challenge) Using inex+, repeat the "Janus" experiement from Exercise 3: design functions sum-inex-L->R and sum-inex-R->L and devise a list of Inexact4 numbers that produce different results when given to these two functions.
How small can you make your list?
Can we avoid the "Janus" problem by increasing the size of the mantissa? If you have extra time, try it.