Introduction

Unbounded arithmetic operations are quite important in modern mathematical systems like Matlab, Mathematica, and Maple. In those systems unbounded signed integers are represented as linked lists of machine size integers. Thus the base of the integers might be 256 or higher. For this project we’ll just use base 10 integers. Since this is a data structures course we are really interested in the inner workings of unbounded arithmetic, not the user interface. We have seen in the homework assignments how to implement addition and subtraction. In addition to these you will implement multiplication. You may be tempted to look at some code in C++ or Java that implements unbounded integers. I don’t recommend that you look at this code until you have finished your project. The purpose of this project is to build up your ability to solve problems and it doesn’t help to look at the solution first.

Your program must be written in C++ and Java with a preamble to give an overall description of your program, and sufficient comments to assure readability.

The User Interface

The user interface will be very simple. It will be terminal input and output. For example:

> Enter an operation: + , - , or *

> Enter first operand:

-578902234567899999999999999999

> Enter second operand:

3789428937777777722222222222222

> The result is:

- 2193708879815819212713875857334970815010096022277777777777778

This product was generated by Mathematica and is correct. Your program should check for invalid inputs. If you are working in C++ you should check use the I/O library found here:

http://www.redhat.com/docs/manuals/gnupro/GNUPro-Toolkit-00r1/4_libs/c_The_GNU_C++_Iostream_Library/libio.html

In particular, the link "Operators and Default Streams" from the above page will be of most use and allow you to see the key read/write routines with an example. The rest is probably excessive detail.

If you are working in Java then you’ll want to use one of the I/O libraries found in

http://www.cs.washington.edu/education/courses/143/02au/javaLibraries.html

which is local to UW. You may also use the standard package java.io found in at the Sun web site

http://java.sun.com/j2se/1.4.1/docs/api/java/io/package-summary.html

Arithmetic Operations

In the solution of the first assignment you can find some pseudocode for addition and subtraction. You are certainly welcome to use that as a basis of your solution. For multiplication I strongly recommend that you design some pseudocode before you start writing code. One important suggestion is to design addition and multiplication for unsigned unbounded integers. These numbers would be represented by a linked list without the leading sign node. You will definitely need a Copy function too. In the first step of your design you should consider building a function that takes an unsigned unbounded integer and a digit and returns the product of the integer and the digit. In the second step of your design I suggest you design a function that multiplies unsigned unbound integers. Finally, you can design the unbounded signed integer multiplication function. There are quite elegant recursive solutions to the integer times digit and integer times integer functions. You should try to discover these.

How to Turn in your Program

We will announce a web based turn-in in the next week.

Good Luck!