CSC151.01 2009F Functional Problem Solving : Labs
Primary: [Front Door] [Schedule] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] - [Assignment]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Readings]
References: [A-Z] [By Topic] - [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [CSC151.02 2009F (Weinman)] [CSC151.02 2009S (Davis)] [CSC151 2008S (Rebelsky)]
Misc: [SamR] [MediaScript] [GIMP]
Summary: We explore some of the kinds of numbers and procedures that Scheme (well, the implementation of Scheme that MediaScript uses) supports.
As the reading on numbers suggests, there are two dimensions along which we can think about numbers. We can consider the kinds of values permitted (integer, rational, real, or complex) and we can consider the accuracy with which the numbers are represented.
Note that when we write numbers with a decimal point (e.g.,
12.5
or 2.0
) we are telling the interpreter
to use an inexact representation. Note also
that rational numbers can be represented in standard fraction form,
as in 23/4
Do your best to identify an example of each of the following kinds of numbers.
a. An exact integer. That is, something you can substitute into the underlined part of the following and get the given result.
>
(exact? ___)
#t
>
(integer? ___)
#t
b. An inexact integer. That is, something you can substitute into the underlined part of the following and get the given result.
>
(inexact? ___)
#t
>
(integer? ___)
#t
c. An exact rational number that is not an integer. That is, something you can substitute into the underlined part of the following and get the given result.
>
(exact? ___)
#t
>
(rational? ___)
#t
>
(integer? ___)
#f
d. An exact real number that is not an integer. That is, something you can substitute into the underlined part of the following and get the given result.
>
(exact? ___)
#t
>
(real? ___)
#t
>
(integer? ___)
#f
e. An inexact real number that is not an integer. That is, something you can substitute into the underlined part of the following and get the given result.
>
(inexact? ___)
#t
>
(real? ___)
#t
>
(integer? ___)
#f
a. Determine what type MediaScript's Scheme interpreter gives for the
square root of two, computed by (sqrt 2)
. Is it exact
or inexact? Real, Rational? An integer?
b. How do we know that the answer it gives us is correct? (What does “correct” mean when the answer is irrational?) We could check by squaring the value, as in
>
(* (sqrt 2) (sqrt 2))
Better yet, we could subtract that result from 2, as in
>
(- 2 (* (sqrt 2) (sqrt 2)))
c. What do the results of these experiments suggest? Why do you think you got the answer you got?
d. Do you expect to have the same problem as in the previous exercise if you compute the square root of 4 rather than the square root of 2? Why or why not?
e. Check your answer experimentally.
Suppose that we've defined val
as a number,
lower
as 0, and upper
a 100.
Consider the following definition.
> (define bounded-val (min (max val lower) upper))
a. Suppose val
is 25. What value will this definition associate with
bounded-val
?
b. Suppose val
is 211. What value will this definition associate with
bounded-val
?
c. Suppose val
is -25. What value will this definition associate with
bounded-val
?
d. Explain, in your own words, what the definition computes when
lower
is 0 and upper
is 100.
e. Suppose we redefined lower
to -10 and upper
to 10 and then redid each of a-c. What results would we get?
f. Explain, in your own words, what this definition computes in terms
of lower
and upper
.
As the reading suggests, the modulo
procedure
computes a value much like the remainder, except that the result is
always the same sign as the second parameter, called the modulus.
(So, when we use a positive modulus, we get a positive result.)
The reading also suggests that modulo
provides
an interesting alternative to using max
and
min
to limit the values of functions.
a. What value do you expect each of the following to produce?
>
(modulo 3 8)
>
(modulo 8 8)
>
(modulo 9 8)
>
(modulo 16 8)
>
(modulo 827 8)
>
(modulo 0 8)
>
(modulo -8 8)
>
(modulo -7 8)
>
(modulo -9 8)
>
(modulo -1 8)
b. Check your answers experimentally, one at a time. If you find that any of your answers don't match what Scheme does, try to figure out why (asking your professor or a tutor if you need help), and then rethink your remaining answers before checking them experimentally.
As the
reading on numbers suggests, Scheme provides
four functions that convert real numbers to nearby
integers:
,
floor
,
ceiling
, and
round
. The reading also claims
that there are differences between all four.
truncate
To the best of your ability, figure out what each does, and what distinguishes it from the other three. In your tests, you should try both positive and negative numbers, numbers close to integers and numbers far from integers. (Numbers whose fractional part is 0.5 are about as far from an integer as any real number can be.)
Once you have figured out answers, check the notes on this problem.
The implementation of Scheme used by MediaScript allows you to treat any real number as a rational number, which means we can get the numerator and denominator of any real number. Let's explore what numerator and denominator that implementation uses for a variety of values.
a. Determine the numerator and denominator of the rational representation of the square root of 2.
b. Determine the numerator and denominator of the rational representation of 1.5.
c. Determine the numerator and denominator of the rational representation of 1.2.
d. Determine the numerator and denominator of 6/5.
If you are puzzled by some of the later answers, you may want to read the notes on this problem.
You may recall that we have a number of mechanisms for rounding real numbers to integers. But what if we want to round not to an integer, but to only two digits after the decimal point? Scheme does not include a built-in operation for doing that kind of rounding. Nonetheless, it is fairly straightforward.
Suppose we have a value, val
. Write instructions that
give val rounded to the nearest hundredth.
For example,
>
(define val 22.71256)
>
(your-instructions val)
22.71
>
(define val 10.7561)
>
(your-instructions val)
>
(... val ...)
10.76
In a problem above, you wrote instructions for rounding a real number to two digits after the decimal place. While such rounding is useful, it is even more useful to be able to round to an arbitrary number of digits after the decimal point.
Suppose accuracy
is a non-negative integer and
val
is a real value. Write instructions for rounding
val
digits after the decimal point to use.
>
(your-instructions ... val ... accuracy ...)
As you write your instructions, you
may find the
useful.
expt
(expt b p)
computes b^{p}.
Here are the ways we tend to think of the four functions:
(
finds
the largest integer less than or equal to floor
r
)r
.
Some would phrase this as “floor
rounds
down”.
(
finds the smallest integer greater than or equal to
ceiling
r
)r
. Some would phrase this as
“ceiling
rounds up”.
(
removes the fractional portion of truncate
r
)r
, the portion
after the decimal point.
(
rounds round
r
)r
to the nearest integer.
It rounds up if the decimal portion is greater than 0.5 and it rounds
down if the decimal portion is less than 0.5. If the decimal portion
equals 0.5, it rounds toward the even number.
>
(round 1.5)
2
>
(round 2.5)
2
>
(round 7.5)
8
>
(round 8.5)
8
>
(round -1.5)
-2
>
(round -2.5)
-2
It's pretty clear that floor
and
ceiling
differ - If r
has a fractional component, then (
is one less than
floor
r
)(
.
ceiling
r
)
It's also pretty clear that round
differs from all of them,
since it can round in two different directions.
We can also tell that truncate
is different from
ceiling
, at least for positive numbers, because
ceiling
always rounds up, and
removing the fractional portion of a positive number causes us
to round down.
So, how do truncate
and floor
differ? As the previous paragraph implies, they differ for
negative numbers. When
you remove the fractional component of a negative number, you
effectively round up. (After all, -2 is bigger than -2.2.) However,
floor
always rounds down.
Why does Scheme include so many ways to convert reals to integers? Because experience suggests that if you leave any of them out, some programmer will need that precise conversion.
The underlying scheme implementation seems to represent the fractional part of many numbers as the ratio of some number and 4503599627370496, which happens to be 2^{52}. (Most computers like powers of 2.) By using a large denominator, it helps ensure that representations are as accurate as possible.
If you are energetic, you might scour the Web to find out why they use an exponent of 52.
Primary: [Front Door] [Schedule] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] - [Assignment]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Readings]
References: [A-Z] [By Topic] - [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [CSC151.02 2009F (Weinman)] [CSC151.02 2009S (Davis)] [CSC151 2008S (Rebelsky)]
Misc: [SamR] [MediaScript] [GIMP]
Copyright (c) 2007-9 Janet Davis, Matthew Kluber, Samuel A. Rebelsky, and Jerod Weinman. (Selected materials copyright by John David Stone and Henry Walker and used by permission.)
This material is based upon work partially supported by the National Science Foundation under Grant No. CCLI-0633090. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
This work is licensed under a Creative Commons
Attribution-NonCommercial 2.5 License. To view a copy of this
license, visit http://creativecommons.org/licenses/by-nc/2.5/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.