![[CS Dept., U Chicago]](http://www.cs.uchicago.edu/i/header_background.jpg)
Courses
Project step 3 is due at 11:59 PM on Friday, 21 November, 2003.
In this project, we represent exact reals as infinite expansions in
some chosen base. Last year, I implemented base 3. Read over the
description of infinite base 3 from 2002. Make sure that you can run my solution on the
resources page,
which includes some helpful output functions as well as the work from
2002
(xreal-2_tristream-1,mod1.2.scm).
Also make sure you understand it. There are a lot of subtleties.
Add a definition for abs_xreal->ratintvl. The
definition is trivial, but it's important to understand the
correspondence between numerical streams and intervals, and very easy
to goof it up. Check over my output utilities and correct problems. I
got the basic idea right, but I didn't work out all details. In
particular, I'm pretty sure that minus signs aren't treated quite
right. This is a bit tricky, since the tristream system
uses genuine negative trinary digits (trits).
The tristream implementation is rather inefficient,
partly because it adds numbers one trinary trit at a
time. precfunc uses arithmetic on full machine words,
which is roughly equivalent to working in base 2^32.
Generalize the trinary code to work on an arbitrary integer base >2
(it turns out that base 2 is much harder than base 3, but larger bases
are essentially the same as 3). Call the generalized implementation
wordstream instead of tristream
Rewrite the code to work with this
unspecified (define large_base <integer>)
large_base. The basic concept is just to
replace the number 3 wherever it refers to the base by
large_base. But the concept of 3 may not always look like
the Scheme number 3. For example, a particular
instance of 2 might really mean the number 2, or it might
mean one less than the base. The changes to the code are quite small,
but you need to be very careful to change just the right integers.
Also change the names of functions and variables to suggest an arbitrary, presumably large, base. I used "wit" for a word-length digit, and "winary" as the generalization of binary, trinary, ... Try not to make your names any dumber than mine.
The output routines need a bit of fixing, so you can tell where one
wit ends and the next begins, since even a single wit may need many
decimal digits to display. I used the underscore character
(_) as a separator.
Test your definitions first with large_base set to 3,
and make sure you get the same results as the trinary
definitions. This is how to catch stupid typing errors before
wrestling with the real stuff.
Even though they are designed to represent exact real numbers, you
can test wordstream operations very well on rationals
with infinite expansions.
Test your definitions with some modest bases other than 3. Base 10 may be particularly easy to check.
Choose the best base for our local computer and implementation of Scheme. The best base is essentially the biggest one that allows all calculations to fit in a single-precision integer value. Scout through the Scheme documentation to discover functions that help you discover the limits on single-precision integer values.
How can you be sure that all of your calculations fit in single-precision? Since Scheme supports unlimited precision, you might not notice an overflow. You can try to make sure by scanning your code very carefully, and by asking a friend to scan it with you. It would be better to find a way to let the Scheme implementation check for you. I'm not sure whether there is such a way or not. This is a good feature to explore and discuss.
Hand in your work with the handin command in the form
handin P3 <files>
wordstream is the name for this assignment's
implementation of xreal.
 | |