Department of Mathematics and Computer Science

Machine Problem 7

Math 61 D. C. Smolarski, S.J. Winter 2000

Data Structure Concepts:LONG INTEGER ARITHMETIC

40 points
DUE: Noon, Thursday, Mar 2, 2000

You have TWO OPTIONS:

OPTION I -- Write a program that will find the reciprocal (up to 100 decimal places) of an arbitrary number (of length up to 100 places). Use your program to find the values of 1/7 and 1/8. Then find the reciprocals of those reciprocals to see if you get 7 and 8 back again. Do not worry about the decimal place -- only concentrate on getting the correct digits.

When finding the "reciprocal of a reciprocal" you must store the initial reciprocal as a long integer, and then use that long integer when finding its reciprocal. You cannot have the code perform algebra, i.e., 1/(1/8.0), to simply the work!

OPTION II -- Write a program that will find the factorial of a relatively large number. Use your program to find 2000! (You should not worry about factorials larger than that.)

Note that the answer will not be able to fit on one output line (nor even on one page!)--therefore, arrange the output procedure to continue the number on additional lines. (Although you could theoretically use the Unix fold command, this does not work on a PC--your program should internally terminate a line at an appropriate length.) The correct answer is given on the LISP webpage "LISP Example," at this link.

GENERAL NOTES:

1. You may work in TEAMS on this program (either option), if you wish. Make sure you give me your team names by the Monday before the due date.
2. Large integer arithmetic is often implemented by using linked lists. A simpler alternative is to merely use large (one-dimensional) arrays. The main point is to use the knowledge you have received in the course to get the program running. Finding factorials or finding reciprocals (dividing a single digit into 1) are relatively "easy" operations to do, yet either can be quite difficult with extended digit arithmetic. That is the major challenge of this program.
3. You do not have to restrict yourself to modulus 100 arithmetic (as in the class example). It would probably be better to use modulus 10000 arithmetic (if it works on math, HP Unix server, or your PC -- you should test it to see!).