CS U212 - Lab 10

As usual the lab is to be completed in pairs. Each pair works on one computer. You may not work with a partner with whom you have previously worked this semester. Change roles after each exercise. Never forget to apply the design recipe!.

Part 1: Math Review

Let's see how much DrScheme knows about math.

We all know that 1 + 2 is the same 2 + 1 (right?). We also know that 1 + 2 + 3 is the same as 3 + 2 + 1 (in fact, the order doesn't matter). Specifically, addition is commutative and associative.

Let's see if DrScheme agrees with this.

Exercise 1: Design a function sum-R->L that adds a list of numbers from right to left. Use one of the loops that you have learned.

Exercise 2: Design a function sum-L->R that adds a list of numbers from left to right. (Hint: this is really easy if you did the last exercise correctly.)

When you test exercise 1 and 2, test them on the same data. You want to make sure that:
   (= (sum-L>R a-list) (sum-R->L a-list))
for each list.

Exercise 3: Try your functions out on the following data: 

(define JANUS
  (list #i31
        #i2e+34
        #i-1.2345678901235e+80
        #i2749
        #i-2939234
        #i-2e+33
        #i3.2e+270
        #i17
        #i-2.4e+270
        #i4.2344294738446e+170
        #i1
        #i-8e+269
        #i0
        #i99))
These funny looking numbers that start with #i are just another way of writing down numbers. You'll find numbers like these in every popular programming language. They're usually written differently, though.

Numbers like #i2e+34 just mean 2 times 10 to the power of 34, or 2 with 34 zeros after it.

Check to see what (sum-L->R JANUS) and (sum-R->L JANUS) are equal to.

Has DrScheme gone crazy?

Well, sort of, or at least those numbers have.  The #i in front of them stands for "inexact."  In order to save space and time, computers often use approximations of numbers rather than precise values.  Sometimes precise values can't be computed at all.

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 movies have addressed this issue.)

Nonetheless, inexact numbers are useful for some kinds of computing. The rest of this lab explains how they work.

Representing inexact numbers

Anyone who owns a computer knows that memory is expensive. It is important that our programs use small amounts of memory when possible.  Every piece of information in a program takes up some amount of memory.

How much memory does a boolean take?
Probably not much.

How much memory does a string take?
Probably the same as its length.

How much memory does a number take?
Probably about the same as its number of digits.

How many digits in 1/3?  How many in pi?
Uh-oh.  We don't have that much memory!

We have to find a smaller representation for numbers. Let's start simply: limit our number of digits. For simplicity, we choose two digit numbers. Let's write down some examples of adding these numbers.

(+ 00 00) = 00
(+ 20 35) = 55
(+ 50 50) = 100

But there's a problem! The last computed 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 the function inexact-plus that adds two inexact numbers using the data definition for 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

Our last representation of numbers was pretty limited. Here are some things we might want to write programs for:

The distance from the earth to the sun in meters:
Can't represent it (too big).

The average distance between the electron and proton in a hydrogen atom in meters:
Can't represent it (too small).

The exchange rates of currencies:
Can't represent it well (too coarse-grained: we can't tell 1.6, 1.7, and 2.2 apart).

Computers need to handle large numbers, small numbers, and numbers close together. Recall scientific notation from science class:

The first part (the 1 or the 9.09) is called the mantissa.
The second part (the 6 or the 3) is called the exponent.

If we stay away from decimals, for the moment, and stick to two digit numbers, we have another new data representation.

(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.
You might have noticed a few things:
First, some numbers (like 0, 100, etc.) can have multiple representations.
Second, we can still have overflows.
Third, we often have to "leave off" some digits.

This third case, where we leave off digits, is why we call these "inexact" numbers.  We use (make-inex 10 6) to represent 10,000,000, 10,000,001, 10,000,002, and all the way up to 10,999,999.  It's not very exact, but it's a compact representation.

Speaking of small, we can now represent large numbers but we can't represent small numbers.  Neither negative numbers nor fractions can be represented so far.

Returning to scientific notation, negative numbers are easy to represent: we use a negative mantissa.  To represent negative one million, we use -1*10^6.  We represent -235,678 as -2.35*10^5.

Fractions are represented as decimals with a negative exponent.  One half, or 0.5, is 5.0*10^-1.  One sixteenth, or 0.0625, is 6.25*10^-2.  One one-millionth is 1*10^-6.

Let's make another refinement to our data definition:

; 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 for the following numbers as Inexact3 values.
As before we can have overflow (even with negative numbers) when our exponent becomes too large.

As before we can have inexact representations when our mantissa should have too many digits.

Now we can have Underflow when our numbers become too small (too close to zero) and the exponent becomes less than -99.

This gives us our final data definition:

; 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 Inexact4 data.

Exercise 8: Now write the template for processing two pieces of Inexact4 data.  This is useful for writing programs such as inexact-equals?, inexact-plus, and inexact-times.

Restriction: You may not use or compute any numbers larger than 4 digits in solving the following problems.  Using unbounded-size numbers for bounded-size computations defeats the point.

; A Digit is an integer between 0 and 9, inclusive.

Exercise 9: Design the 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 the number 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 the function inex<=? that compares two inexact numbers.

Exercise 11: Design the function inex* that multiplies to inexact numbers.

Challenge Exercise: Design the function inex+ that adds two inexact numbers.