►Fundamentals 1
▼Labs
►Lab 11 Inexact Arithmetic
On this page:
Basic Arithmetic Facts
Representing inexact numbers
Better inexact numbers
7.5
    ← prev  up  next → 

Lab 11 Inexact Arithmetic

lab!

Purpose: This lab is an introduction to way computers represent fractional numbers – and its associated pitfalls.

Basic Arithmetic Facts

Let’s see how much DrRacket knows about math. We all know that

a + b = b + a

We also all know that

(a + b) + c = a + (b + c)

The first property means that addition is commutative and the second means that addition is associative. Let’s see if these properties hold in DrRacket…

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 functional abstraction…)

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 functional abstraction…)

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
        -1.2345678901234999e+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 2e+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

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 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 pi? …

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 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

The representation Inexact1 is pretty limited. Here are some things we can’t compute with it:

  • 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

When we compute we often need to handle a wide range of numbers. Let’s try to do this by devising a representation based on scientific notation:

  • 1 × 106 = 1,000,000

  • 9.09 × 10-3 = .00909

In 9.09 × 10-3, 9.09 is the mantissa and -3 is the exponent. This suggests a small modification to Inexact1 that will enable us to represent numbers that are both very large and very small:
(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

There are a few things to notice from the last exercise:

  • Some numbers (e.g., 0 and 100) can have multiple representations

  • We can still have overflows

  • We often have to omit less significant digits

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

Speaking of small, we can now represent large numbers but we can’t represent small ones. Neither negative numbers nor fractions are representable so far. In scientific notation, we represent negative numbers with a negative mantissa, and we represent fractions with a negative exponent. For example:

  • −1 × 106 = −1,000,000

  • 2.5 × 10−5 = .000025

  • −8.25 × 10−2 = -.0825

Let’s further refine our data definition for inexact numbers:
; 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:

  • 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—when the number get too close to zero.

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 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 use any numbers larger than four digits—computing with arbitrary-precision numbers to operate on fixed-precision numbers defeats the purpose!

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 '())  (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.

Final note: What we have called "inexact numbers" in this lab (and in DrRacket) are what most of the programming world calls "floating-point numbers." Essentially all general-purpose microprocessors have custom circuitry on-chip that implements the inexact arithmetic directly in hardware that you implemented today in Racket software. If you understand how your inexact arithmetic functions work, then you understand how this hardware works.

And, of course, you also now understand how computations with these values can go wrong or do weird, counter-intuitive things.

    ← prev  up  next →