Overview
This week we will begin a large project which we can use to transition from BDS
C on CP/M to C++ on Unix. In this project we will use the College Board's
The Large Integer Case Study in C++ as a guide to implement a
bigint
struct in BSD C.
Handling arbitrary-precision integers is a classic problem in computer science. To quote the problem statement on page one The Large Integer Case Study in C++:
Arithmetic operations are fundamental in computing and programming. In many programming environments the largest value of an integer variable is much too small to represent large quantities such as the population of the world, the U.S. national debt, the number of occurrences of the letter 'e' in Melville’s Moby Dick.
This is definitely true in our Altair 8800 BSD C environment, where as
you'll soon verify, the largest signed integer we can store is
32767. That's not even large enough to hold an APS teacher's
yearly salary! ;-)
You told me you want to work individually on this project, so that's how we'll do it. Period 3B meets three times this week while 1A meets only twice. I will be out Thursday and Friday, so we will plan for the whole week to accomdate all this.
Goals
Our guiding goal is to implement an arbitrary-precision integer in BDS C running on CP/M 2.2.
We'll be using the College Board's Large Integer Case Study in C++ as a guide, but we will need to make significant adjustments and adaptations to the approach taken in that document to accomodate our much more limited computing environment.
Our learning goals for this project include developing the ability to create a
large scale computer program to solve a large problem, and to create a
programmer defined object
(we'll be using a struct in C) to
implement an
abstract data
type.
In evaluations for this project, I will be explicitely looking for evidence in what you write that you understand this technical challenge and can reason effectively about it.
Considerations
As you read through the case study document, try to understand the approach being developed using C++ on a 32 bit machine to solve the problem of creating an arbitrary-precision integer, and evaluate how that approach would have to be modified to work on our 8 bit machines using K&R C.
To help stimulate your thinking and to provide evidence that you are getting
it
, take this modified sample interaction with the calculator program
introduced on the bottom of page 2 of the case study:
Enter value: 30000 --> 30000 Enter operator (+ - * (= to quit)): * Enter value: 3 --> 90000 Enter operator (+ - * (= to quit)): =
Will this work in our CP/M 2.2 environment? Why or why not?
Here's what happens on the version of this program you will soon be investigating:
Enter value: 30000 --> 30000 Enter operator (+ - * (= to quit)): * Enter value: 3 --> 24464 Enter operator (+ - * (= to quit)): =
You should think about this example in detail and be ready to answer questions about it on a test at the start of 2026.
This example should guide you as you take notes while you read through the case study. Strive to show me by what you write that you are understanding both the problem we are trying to solve and the technical challenges we face in doing it.
Some particular challenges we will face on our Intel 8080 platform are on page 76 of the BSD C Reference Manual, where it states:
The following is a section-by-section annotation to the C Reference Manual. For the sake of brevity, some of the items mentioned above will not be pointed out again; any references to floats, longs, statics, initializations, etc., found in the book should be ignored.
On the previous page (75), it states that:
There are no explicitly declarable storage classes. static and register variables do not exist; all variables are either external or automatic, depending on the context in which they are declared.
Tasks
Complete each of the following tasks:
- Download a copy of The Large Integer Case Study in C++.
- Read through page 17, which is all of the sections under the heading Large Integer Case Study in C++. Pay particular attention to the Study Questions on pages 3, 6, 10 and 17, since that is where I will go for inspiration in designing the test you will have when we return. Also look at the code in Appendix A: The Calculator.
-
Create a sub-directory in your git repo named
BigInt. Add a markdown file with your responses to the Study Questions. - Download CALC.C, compile it and run it. This is a version for our systems of the Appendix A code.
- Download BIGINTS0.C and BIGINTS1.C, compile them and run them.
- Download BIGGEST.C, compile it and run it. Add a series of additional experiments that help you understand what is happening.
Evaluation
We agreed that there will be no homework assigned during winter break. That means we don't have time to waste, so you need to stay on task this week to get done what we need to do.
You will receive two grades for your work this week. Your git repositories will be evaluated for notes and programatic investigations showing evidence that you are working to understand this project. This is due Friday, January 19th at 11:59 pm.
On the first day back in class in January, you will have a test on both the readings and the programs provided for you to study.