# From starter code to printing

**Get our starter code for the array representation**and rename it to`bignum.smt`

.

**Choose a base**for natural numbers.A small base helps with debugging.

A large base helps with performance.

Start with a small base and then change it later. Because it might change, you must store the value in only

*one*place in your code. We will do this the way the book recommends:- Update the private class method
`base`

so that sending`(Natural base)`

always answers the base. Choose a base that is not 10 and that will make it moderately easy to read the internal representation. Good choices include 8, 16, 100, and 1,000.^{1}

**Bookmark relevant protocols**Class Natural inherits from Magnitude, and the specifications of the methods you are implementing are found in the book:

Class Page `Magnitude`

page 659 `Natural`

page 662 `Array`

pages 653, 656, and 657 Mark these pages so you can refer to them easily.

**Define representation**. Your class`Natural`

will need at least two instance variables:An array that can hold digits

Something that tells you how many digits are meaningful

^{2}

To count meaningful digits, we refer to the “degree” of the representation.

- In the
`ivars`

declaration for class`Natural`

, replace the`...`

with the instance variables you will use to represent the digits and the degree of a natural number.

The degree of a natural number is the power of the base to which the most significant nonzero digit is raised, so a one-digit number has degree zero. That makes the degree one less than the number of meaningful digits.

Next to your

`ivars`

form, add a comment of the form`A (self) == ...`

which says what natural number an instance stands for. The comment should look a lot like the definition of the abstraction function for the array of digits on page 679 of the textbook. Just figure out how to express

`degree`

and \(x_i\) in terms of your representation.

**Implement basic digit manipulations**. Figure 10.24 on page 680 of the textbook suggests a bind of private messages that provide basic tools for manipulating an array of digits.Implement private instance method

`digit:`

. Method`digit:`

must not fail even if the index given is arbitrarily large. Take advantage of method`at:ifAbsent:`

, which is defined on instances of class`Array`

.Implement

`digit:put:`

, and`makeEmpty:`

.Implement

`doDigitIndices:`

.Implement

`degree`

.Implement

`trim`

, which sets the degree as small as possible given the current contents of the digits.Now implement

`digits:`

. Take advantage of class method`withAll:`

on class`Array`

. This method is normally a homework exercise, but an implementation is included with the starter code. After writing digits into the array instance variable, the`digits:`

method should use`trim`

to set the receiver’s degree. Finally, the`digits:`

method should answer`self`

.

**Test**. To print your representation, method`digits:`

with`printrep`

`printrep`

is included with your starter code, as is a wrapper class called`DebugNat`

:`(class DebugNat [subclass-of Object] [ivars nat] ; a natural number (class-method of: (aNat) ((self new) init: aNat)) (method init: (n) (set nat n) self) ; private (method print () (nat printrep)) )`

Using

`DebugNat`

and`printrep`

, test your`digits:`

method. For example, the following test should pass:`;;; make natural number from digits, least significant first (check-print (DebugNat of: ((Natural new) digits: '(1 2 3))) 3,2,1)`

**Test basic digit manipulations**. Using`digits:`

to create natural numbers as needed, test private methods`digit:`

,`digit:put:`

, and`makeEmpty:`

. Because these methods mutate the representation, you will need to create a new, global array variable for each test.

**Implement the**. Class`invariant`

method`Natural`

has an`invariant`

method that is left as an exercise. Invariants of the array representation include the following:Every digit \(x_i\) is in the range \(0 \le x_i < b\).

If the number has degree \(d\) than for \(0 \le i \le d\), digit \(x_i\) is stored in the array.

For every \(j > d\),

~~(self digit: \(d\))~~(self digit: \(j\)) is zeroThe degree \(d\) is as small as possible. That implies that either \(d = 0\) or \(x_d > 0\).

Most of these invariants can be checked. Complete the

`invariant`

method so they*are*checked.**Study the**. Past students have written,`validated`

method*A key issue we ran into that we found out late into the process was when creating the number zero in some arithmetic operations, we were using a constructor that did not enforce the invariant. It would be very helpful if the specification put this as a common error or a grave mistake, because most of the logic was correct.*Study the

`validated`

method defined on class`Natural`

. In your implementation of methods on class`Natural`

, wherever you would write an expression \(e\) that creates a new natural number, consider using (\(e\) validated) instead.**Define public method isZero**on class`Natural`

. (An array represents zero when all of its digits are zero.)

**Test public method isZero**. Using class method`new`

and private instance method`digits:`

, test method`isZero`

on both zero and nonzero natural numbers.

**Define initialization method**.`fromSmall:`

on class`Natural`

`fromSmall:`

is a*class*method that takes a positive small integer \(k\) and returns a new*instance*of class`Natural`

that represents \(k\).As always happens in Smalltalk, a new instance is created in stages:

A new instance is created by sending a message to the

*class*.The new instance is initialized by sending it a private message.

To implement (self fromSmall: \(k\)), I recommend first computing a list of digits. Then create a new instance of

`Natural`

by sending`new`

to the class, and finally initialize the new instance by sending`digits:`

with the list of digits.To get the list of digits, try using a local variable

`temp`

with a`whileTrue:`

loop:- Set
`temp`

to`(List new)`

. - As long as \(k\) is nonzero, add
\(k \bmod b\) to*k mod 10*`temp`

and replace \(k\) by\(k \;\mbox{div}\;b\), where \(b\) is the base of natural numbers.*k div 10*

You can now answer

`((self new) digits: temp)`

.

**Test class method**. Supposing your \(b\) is a power of 10 or a power of 2, here are some sketches that may be useful:`fromSmall:`

`(check-print (DebugNat of: (Natural fromSmall: 0)) 0) (check-print (DebugNat of: (Natural fromSmall: ((Natural base) * (Natural base)))) 1,0,0) ;; or it might have a leading zero (check-print (DebugNat of: (Natural fromSmall: 1)) ...) (check-print (DebugNat of: (Natural fromSmall: 1000)) ...) (check-print (DebugNat of: (Natural fromSmall: 1234)) ...) (check-print (DebugNat of: (Natural fromSmall: 4096)) ...)`

As usual,

*indent your unit tests by eight spaces*.You may include unit tests in your file

`bignum.smt`

, but as noted in the assignment,*the entire file must load in less than 2 CPU seconds*. You may instead choose to put your unit tests in a separate file,`longtests.smt`

, where they may run for as long as you like. To run these tests you can use this shell command:`$ echo '(use bignum.smt) (use longtests.smt)' | usmalltalk -qq`

# Equality

**Implement equality comparison**Implement`=`

. To make the comparison relatively easy, use private methods`digit:`

and`doDigitIndices:`

. Comparing natural numbers of different degree requires care, but there is a simple, elegant way to do it—try to find it.

# Addition

You’ll implement all the arithmetic methods, starting with `+`

, to the same pattern:

Allocate a new, empty

`Natural`

\(Z\) with enough digits to hold the result.Compute the result by mutating the digits of \(Z\), in place.

Trim \(Z\) to its final degree.

Return \(Z\).

Once trimmed and returned, the object representing \(Z\) is never mutated again. *The receiver of a message must never mutate its own digits.*

**Implement method**. Use the algorithm on pages S17 to S19 of Appendix B. The algorithm loops on an index \(i\), and at at each iteration, it computes one digit \(z_i\) and one carry bit \(c_{i+1}\):`+`

\[\begin{aligned} z_i &= (x_i + y_i + c_i) \bmod b\\ c_{i+1} &= (x_i + y_i + c_i) \;\mbox{div}\;b\end{aligned}\]

Digits \(x_i\) and \(y_i\) are obtained by sending

`digit:`

to a natural number, and \(z_i\) is assigned by sending`digit:put:`

to \(Z\). Carry bit \(c_0\) is zero, and \(c_i\) is obtained by the addition of digits \(x_{i-1}\) and \(y_{i-1}\).The carry bits don’t all need to be stored; you can define a single local variable

`c`

to hold the carry bit. Initialize it to \(0\) and update it on every iteration.The loop should be implemented using the

`doDigitIndices:`

method.Don’t forget to

`trim`

.**Test addition**. It will help you find bugs early to design tests aware of your base:Tests that do not invoke the carry bit

Tests that do invoke the carry bit

Tests that require growing the array

A potential hazard is accidently mutating the operands. For example, (\(X\) + \(Y\)) should not mutate the representations of \(X\) or \(Y\).

Be mindful and check the size of the resulting array and the invariants on the resulting

`degree`

. If you encounter errors with size or`degree`

, double check that`trim`

is working properly.

# Subtraction and comparison

**Implement**. If the receiver is \(X\) and the argument is \(Y\), the`subtract:withDifference:ifNegative`

`subtract:withDifference:ifNegative:`

method implements \(Z \mathrel{:=} X - Y\) using the algorithm on pages S19 to S20 of Appendix B.The algorithm resembles the algorithm for addition, but the carry bit is called a “borrow,” and it works a little differently. When we’re computing a digit of \(Z=X-Y\), everything depends on whether the difference \(x_i-y_i-c_i\) goes negative. If not, it’s all glorious: \[\begin{aligned} \text{When $x_i-y_i-c_i \ge 0$, }\mskip 40mu z_i &= (x_i - y_i - c_i)\\ c_{i+1} &= 0\end{aligned}\] Otherwise, we have to borrow \(b\) from a more significant digit: \[\begin{aligned} \text{When $x_i-y_i-c_i < 0$, }\mskip 40mu z_i &= b + (x_i - y_i - c_i)\\ c_{i+1} &= 1\end{aligned}\] The second case exploits the identity \[z_{i+1} \mathbin{\cdot}b^{i+1} + z_i \mathbin{\cdot}b^i = (z_{i+1} -1) \mathbin{\cdot}b^{i+1} + (z_i + b) \mathbin{\cdot}b^i.\] If when the dust settles, \(c_n=1\), then we tried to borrow from a digit that’s not there. That means the difference is negative and therefore is not representable as a natural number—and the

`subtract:withDifference:ifNegative:`

method must transfer control to its failure continuation.Don’t forget to

`trim`

.**Test subtraction**. Method`-`

uses`subtract:withDifference:ifNegative:`

. Test it using`check-print`

, and for the negative case,`check-error`

.**Implement the remaining comparison method**. Implement the`<`

method. Use method`subtract:withDifference:ifNegative:`

with this law: \[X < Y \equiv X - Y < 0\text.\]

# Division and decimals

**Implement division and modulus**. To avoid taking time exponential in the number of digits, division has to be implemented simultaneously with modulus. In the ML modules assignment, simultaneity is accomplished by returning a record that contains both quotient and remainder. In Smalltalk it is accomplished using continuation-passing style (the same way that`ifTrue:ifFalse:`

is implemented, as shown in Section 10.4.3 in*Programming Languages: Build, Prove, and Compare*).When \(X\) is a natural number, \(v\) is a small integer, and \(K\) is a continuation, (\(X\) sdivmod:with: \(v\) \(K\)) results in evaluating (\(K\) value:value: \(Q'\) \(r'\)), where \(Q' = X \;\mbox{div}\;v\) and \(r' = X \bmod v\).

Just like addition and subtraction,

`sdivmod:with:`

should be implemented using a three-part strategy. In this case, the strategy begins not with an empty`Natural`

but with a copy of the receiver.Make a copy of the receiver.

Mutate the copy in place by sending it

`setSdiv:remainder`

.Send the copy and the remainder to the continuation.

A cheap and cheerful way to make a copy of the receiver is to add zero to it.

Method

`setSdiv:remainder`

mutates the receiver, dividing it by the small-integer divisor, and it answers the remainder, which is of class`SmallInteger`

. The algorithm loops*down*over index \(i\), starting with \(i=n\) and going down to \(i=0\). At each iteration, the algorithm computes a digit \(q_i\) of the quotient, and it computes an intermediate remainder \(r_i\). That remainder is then named \(r'_{i-1}\), where it is combined with digit \(x_{i-1}\) to be divided by \(d\). Values \(q_i\) and \(r_i\) are given by these equations: \[\begin{align}q_i &= (r'_i \mathbin{\cdot}b + x_i) \;\mbox{div}\; d& r_i &= (r'_i \mathbin{\cdot}b + x_i) \bmod d\\ &&r'_{i-1} &= r_i\\ &&r'_n &= 0\\ &&r&= r_0 \end{align}\] At each step, quotient digit \(q_i\) is written into the receiver’s representation, and the remainder goes into the next step. The final remainder is what is answered from the method.Implement methods

`setSdiv:remainder`

and`sdivmod:with:`

.**Test**using`sdivmod:with:`

`DebugNat`

. Test division and modulus using the`sdiv:`

and`smod:`

methods provided, which use`sdivmod:with`

. Write`check-print`

unit tests using`DebugNat`

. Also write`check-assert`

tests (with`isKindOf:`

) that confirm the classes of the results: a quotient should be a kind of natural number, whereas a remainder should be a kind of small integer.**Implement public method**. Method`decimal`

`decimal`

must answer a standard`List`

. To convert`self`

to a list of decimal digits, I recommend using mutable local variables:Initialize an empty, mutable list.

Initialize a local variable \(Z\) equal to

`self`

.As long as \(Z\) is not zero, use

`sdivmod:with:`

to pass \(Z \;\mbox{div}\;10\) and \(Z \bmod 10\) to a continuation. The continuation should use`addFirst:`

to add \(Z \bmod 10\) to the front of the list of digits, and it should replace \(Z\) by \(Z \;\mbox{div}\;10\).You can iterate this step using

`whileTrue:`

or`whileFalse:`

.When \(Z\) is zero, you’re almost finished. Just make sure the list of digits isn’t empty—if it is, add zero to it.

Answer the list.

**Change the**defined on class`print`

method`Natural`

so it sends`print-with-decimal`

, not`printrep`

.**Unit-test the new**with true decimals. Check your work by cloning and modifying your old`print`

`check-print`

unit tests:Copy and paste your unit tests for

`fromSmall:`

,`plus:carry:`

, and`+`

.In each copy, remove (DebugNat of: \(\cdots\)), and change the expected output to use standard decimal notation. As in this example:

`(check-print (DebugNat of: (Natural fromSmall: 5)) 1,0,1) ;; old version (check-print (Natural fromSmall: 5) 5) ;; new version`

Re-run all the tests.

*Both your old tests and your new tests should continue to work.*

# Multiplication

**Implement multiplication**. Multiplication follows the same pattern as addition and subtraction:Allocate a new, empty (zero) number \(Z\) with enough digits to hold the result. The product \(X\mathbin{\cdot}Y\) might need as many digits as \(X\) and \(Y\) put together.

Using a doubly nested

`doDigitIndices:`

loop, mutate \(Z\) until all the partial products have been accumulated.Finally

`trim`

the result and return it.

To multiply two natural numbers represented as arrays, we compute \[\begin{align*} X \mathbin{\cdot}Y &= \bigg(\sum_i x_i b^i\bigg) \mathbin{\cdot}\bigg(\sum_j y_j b^j\bigg)\\ &= \sum_i \sum_j (x_i \mathbin{\cdot}y_j) \mathbin{\cdot}b^{i+j} \end{align*}\] The partial products are added into \(Z\) one at a time.

Each partial product \((x_i \mathbin{\cdot}y_j) \mathbin{\cdot}b^{i+j}\) might require two digits to represent it. Those digits are called \(z_{\mathit{hi}}\) and \(z_{\mathit{lo}}\), and they are given by these equations: \[\begin{align*} z_{\mathit{hi}} &= (x_i \mathbin{\cdot}y_j) \;\mbox{div}\;b\\ z_{\mathit{lo}} &= (x_i \mathbin{\cdot}y_j) \bmod b\\ x_i \mathbin{\cdot}y_j &= z_{\mathit{lo}} + z_{\mathit{hi}} \mathbin{\cdot}b, \end{align*}\] Digit \(z_{\mathit{lo}}\) gets added into the \(b^{i+j}\) position, and \(z_{\mathit{hi}}\) gets added into the \(b^{i+j+1}\) position.

Implement method

`*`

.**Test multiplication**. Use`check-print`

to test products that produce large numbers. Start with test candidates of the form \((X+1)\mathbin{\cdot}(X-1)\), because the correct answer is always \(X^2 - 1\), which is easy to compute by hand.You might continue by computing large powers. Powers are already implemented on class

`Number`

, and our bignum starter code extends class`Natural`

with the`squared`

,`coerce:`

, and`raisedToInteger:`

methods from the`Number`

protocol. So you should be able to run these tests:`(check-print ((Natural fromSmall: 10) raisedToInteger: 10) 10000000000) (check-print ((Natural fromSmall: 9) raisedToInteger: 9) 387420489) (check-print ((Natural fromSmall: 99) raisedToInteger: 99) ;; result broken into multiple lines for readability; they must be rejoined 36972963764972677265718790562880544059566876428174110243025997242355257 04552775234214106500101282327279409788895483265401194299967694943594516 21570193644014418071060667659301384999779999159200499899)`

If your multiplication is terribly slow, you may run up against the CPU limit built into

`usmalltalk`

. To disable the limit, you can put your long-running tests into file`longtests.smt`

, and run them like this:`echo '(use bignum.smt) (use longtests.smt)' | env BPCOPTIONS=nothrottle usmalltalk -qq`

instead of just

`usmalltalk`

.Write a unit test that computes \(2\mathbin{\cdot}2\mathbin{\cdot}2\mathbin{\cdot}2\mathbin{\cdot}2 = 32\), then uses

`degree`

to confirm that the number of digits has*not*doubled at every multiplication.

# Finishing up

**Finalize the base**of natural numbers. You want it as large as it can be without causing arithmetic overflow. If you have unit tests that use`DebugNat`

or`printrep`

, remove them or comment them out.**Run randomly generated integration tests**. We provide some tests for class`Natural`

. We used a random-number generator to create relatively big tests that exercise many methods at once—especially the all-important`decimal`

method. If your code passes our tests, it should give you some confidence. But if your code fails one of our tests, the failure won’t tell you what went wrong. That’s why these tests come last, after your own unit tests.Our randomly generated tests can be run as follows:

`echo '(use bignum.smt) (use natural-tests.smt)' | usmalltalk -qq`

**Confirm formatting**of unit tests. Make sure all unit tests and their supporting definitions are indented 8 spaces.