Exact numbers, Floating-point numbers, overflow, underflow, Round-off and other imprecision, Tradeoffs
Mathematical programs in Scheme can sometimes be unacceptably slow because they calculate exact answers. E.g., consider finding the integral of a curve using the standard beginning calculus method, adding the areas of many small trapezoids under the curve. Scheme would accurately calculate these areas in a result like 3141592654/2718281828. Working with such fractions can be slow, so Scheme can instead work to return an approximate result, like 1.155727350137, much more quickly. (A partial explanation: Consider multiplying two fractions. This really means multiplying twice, once each for the denominators and numerators, plus also simplifying the result.) The idea is that the answer might be inexact, but hopefully the error is small. Today's lab discusses this trade-off between efficiency and accuracy, and also demonstrates how sometimes computers give answers that are just flat-out wrong.
While there is no bound on how big or tiny a mathematical number can be, unfortunately every computer does have a bound on how big or tiny a number it can represent internally.
You have probably already noticed that Scheme uses "arbitrary precision
arithmetic": It can represent very large integers accurately.
For instance, ten to the eightieth power
plus seventeen can be typed directly into Scheme,
100000000000000000000000000000000000000000000000000000000000000000000000000000017
,
and the value stored exactly.
The only limit to such numbers in Scheme is the actual amount of memory of
the computer.
In order to represent these large, exact-precision integers, Scheme is (essentially) keeping a list of the digits. When it adds or multiplies two exact-precision numbers together, Scheme performs the grade-school algorithms.
There is an alternate way to represent numbers: one can assume that all integers have (say) 9 digits. This makes addition and multiplication of numbers simpler and faster, and might be sufficient for most programmer's needs. Of course the draw back is that only about 109 numbers can be expressed in this manner.
This fixed-size representation doesn't apply only to integers,
but can be applied to fractional numbers.
Most computers nowadys represent numbers by using
(say) 15 significant digits.
In order to express fractional amounts,
of numbers, scientific notation is used. For instance,
6.022e23
is 6.022 with the decimal place shifted
23 places to the right (i.e., 60.22 hexillion).
Just as the mantissa (the "6.022" part) is restricted to 15 digits,
the exponent (the "23" part) is also restricted in size; we'll see how
big it can be in a moment.
This method of representing numbers is called
floating-point representation,
since the decimal point "floats" among the
15 significant digits, depending on the exponent.
Notice that inside the computer, each floating-point number needs
the same, fixed number of digits to be stored. This convenience
sometimes makes up for the fact that such numbers might only be
approximations to the numbers we're actually interested in.
In Scheme, floating-point numbers are called "inexact" numbers because they aren't exact. In some languages, they are referred to as "reals".
Using fixed-width numbers up to (say) a billion
might be fine for most everyday calculations, but what
happens when you try to add a couple large 9-digit numbers and
get a 10-digit number?
The result can no longer be stored as an exact integer;
this is called overflow.
What happens next depends on the particular system.
The program might halt; it might procede with
the result tagged as a special, anomolous value
perhaps written +Infinity
; or (most frightful yet)
it might procede with some totally spurious number, without
even informing anybody that all subsequent calculations are garbage.
Just as with integers, it is possible to think of numbers whose exponent is larger than can be stored in a computer's floating point number; calculations whose answer exceeds the largest expressible number is again called overflow.
In addition to arbitrary-precision rational numbers,
Scheme also uses floating-point numbers whenever a
number is typed in as a decimal point.
Evaluate (/ 2 37)
and compare it to (/ 2.0 37.0)
.
(If you really need them,
there are also functions exact->inexact
and
inexact->exact to convert between the two formats.)
For any number x
, if we double x
and then
divide by two, hopefully we get x
back.
But here's where overflow can get in the way:
If x
is large enough that
doubling it causes an overflow, then
doubling x
followed by halving the result will likely not
give us x
back.
Let's take a number, and keep doubling it until (using
this approach) we find an overflow:
(define find-huge (lambda (x) (if (not (= x (/ (* x 2.0) 2.0))) x (find-huge (* x 2.0))))) (define huge (find-huge 1.0)) (+ huge huge)
Underflow occurs when a number is too tiny to be expressed as
a floating-point number; i.e., when you get a non-zero number which
is very very close to zero, such as 1/1e400
.
Beware that some people mis-use the term underflow to mean "overflow in the negative direction", that is taking a very negative number and multiplying it by two. The technical term for that situation is "overflow in the negative direction".
Self-exercise: Write a function find-tiny
which
finds a number which is within a factor of two of the
smallest (positive) representable fixpoint number.
There is an IEEE floating point standard which also incorporates gradual underflow, a scheme to try to go underflow "softly" from a non-zero value to zero (in some situations this difference is a qualitative change, as well as quantitative one).
Besides underflow and overflow, there are two other ways errors can be introduced in floating point numbers.
The first is round-off error. Sometimes, when dividing one number with 10 decimal places by another with 10 decimal places, the the result requires 11 or more decimal places to store the answer. No problem, you round the last digit, and you have an answer that's pretty darn close to exact.
The problem is, round-off error can accumulate.
For a simple example, write a function which adds up 185 copies of
(/ 1.0 185)
--what is the result?
What if you have a function which starts at 1 and subtracts 1.0/185
with each recursive call, quitting when its argument is
precisely equal to zero?
The second form of error can be more insidious.
If we are using only (say) 15 significant digits, then we run
into problems when adding numbers which vary by more than a
factor of 1016:
1.0e16 + 1
should be 1.00000000000000001e16
,
but if you only have 15 digits the closest answer is 1.0e16
,
which is what you started with!
You might think this error is reasonable; being wrong by one part
in 1016 (ten million billion)
is admittedly close enough for government work.
However, small errors can accumulate. Load
/home/comp210/public_html/Labs/lab06/sum.ss
into DrScheme to get the function sum
to
add a list, and some example lists b, c, d,
and e, which are all different arrangements of the same numbers.
Does the order of addition affect sum
's result?
The function better-sum
suggests a simple rule-of-thumb to
minimize the error: always handle small-magnitude numbers first.
Does that approach always solve the problem?
If a small error can occur even once, are there cases where
a large error can?
Consider the following list, named janus
after
the two-faced Roman god.
(define janus (list 99 3.2e+270 -99 -2.4e+270 1234 4 -8e+269 -4)) ; (sum janus) = ?? ; (sum (reverse janus)) = ?? ; (better-sum janus) = ?? ; The correct answer = !!What are the results of
(sum janus)
and (sum (reverse janus))
?
How about (better-sum janus)
?
That's quite a difference for answers that should be the same!
What's going on?
Do you still trust your computer to give you reasonably correct answers
as much as you did 30 seconds ago?
To ponder: Can you modify the small-magnitudes-first rule of thumb to better handle all cases?
There are some subtleties with rounding. For example, if the answer is halfway between the two choices, which way do you round? E.g., should -2.5 be rounded to -2 or -3? The method of "always round down" or "always around away from 0" suffers from the flaw that all round-off errors, though individually tiny, may all accumulate in the same direction, leading to results that drift away from the true answer. One solution is to round to the nearest even number. Hopefully (though not guaranteedly) this allows two round-off errors to cancel each other half the time, and therefore the total round-off error grows much more slowly. (Will it still accumulate at all, on average?)
So if Scheme has arbitrary precision integers and rationals,
why do we ever bother with floating-point arithmetic?
Like any interesting choice, there is a trade-off between
the two alternatives (otherwise, it wouldn't be interesting).
Using arbitrary precision arithmetic can sometimes slow us down,
and often the added accuracy isn't enlighting.
For example, in your integrate
problem on the homework,
if you never used a decimal point or the function exact->inexact
,
then integrating some functions can take a long time.
Consider writing our own version of expt
to raise
one number to another, where the second number is a nice, positive integer.
You should be able to whip this out in no time:
(define my-expt (lambda (r n) (cond [(zero? n) 1] [else (* r (my-expt r (sub1 n)))])))Okay, now define two versions of the same number, once as a floating-point number and once as an exact-precision number:
(define approx (+ 1 1e-12)) (define exact (+ 1 (expt 10 -12))(Evaluate each of these variables, just to see what their values look like.)
Now, we try our function on these numbers:
What is (my-expt approx 30)
?
How about (my-expt exact 30)
?
Which answer is more useful to you?
(Check out the interesting symmetry of the numerator
in this second version.)
(You may also want to try raising approx
to a huge
number: try (my-expt approx 1e6)
. Is the result familiar?)
You may also be interested in mathematical questions like what is 1/0? Try (/ 1 0) and (/ 1.0 0.0).
What about (/ 0 0) and (/ 0.0 0.0)? The latter returns something read as "Not a Number".
These are all part of the IEEE floating point standard, which describes the appropriate results for lots of unusual questions.