# From starter code to printing

**Get our starter code for the subclass 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 Mark these pages so you can refer to them easily.

**Define representation**. Skeleton versions of subclasses`NatZero`

and`NatNonzero`

are defined for you in the starter code. Each subclass has superclass`Natural`

.An instance of class

`NatZero`

represents zero.An instance of class

`NatNonzero`

represents a natural number \(X\) of the form \(X' \cdot b + x_0\), where \(X'\) is a natural number, \(b\) is your chosen base, and \(x_0\) is a small-integer digit. Values \(X'\) and \(x_0\) will be stored in instance variables. (When needed, value \(b\) is obtained by sending message`base`

to the*class*.)

In the

`ivars`

declaration for class`NatNonzero`

, replace the`...`

with the instance variables you will use to represent \(X'\) and \(x_0\).

**Implement the**on each subclass. On class`invariant`

method`Natural`

, the`invariant`

method is a subclass responsibility. An instance of subclass`NatZero`

has a trivial invariant. (The one that is always`true`

.) An instance of subclass`NatNonzero`

must satisfy two invariants: (1) \(0 \le x_0 < b\), and (2) \(X'\) and \(x_0\) are not both zero.Define the

`invariant`

method on class`NatZero`

.Define the

`invariant`

method on class`NatNonzero`

.

**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 each subclass.

**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\). Since`NatZero`

and`NatNonzero`

are subclasses of`Natural`

,`fromSmall:`

can return a new instance of either of those subclasses and still respect its contract.Depending on whether \(k\) is zero or nonzero,

`fromSmall:`

will need to create an instance of class`NatZero`

or`NatNonzero`

, respectively. Since \(k\) is a small integer, you can tell the difference by sending it the`isZero`

message.If \(k\) is zero,

`fromSmall:`

will need to create an instance of`NatZero`

by sending message`new`

to class`NatZero`

.`NatZero`

has no instance variables, so no further initialization is required.If \(k\) is nonzero,

`fromSmall:`

will need to create a fresh instance of class`NatNonzero`

. When the`fromSmall:`

class method is given a nonzero \(k\), it should find a small integer \(x_0\) and a natural number \(X'\) such that \[\begin{align}&k = x_0 + X' \mathbin{\cdot}b\\ &0 \le x_0 < b\text{.} \end{align}\] To compute \(x_0\) and \(X'\), you have at your disposal the`div:`

and`mod:`

messages defined on class`Integer`

, plus (recursively!) the`fromSmall:`

method defined on class`Natural`

.Once

`fromSmall:`

has \(x_0\) and \(X'\), it must create a fresh instance of class`NatNonzero`

to hold them. I recommend that you delegate this job to a new class method`first:rest:`

defined on class`Natural`

, which is described below. Given \(x_0\) and \(X'\), class method`fromSmall:`

can simply send this message to class`Natural`

:(Natural first:rest: \(x_0\) \(X'\))

A freshly created natural number should be validated. Decide if you want to use

`validated`

in the`fromSmall:`

class method, in the`first:rest:`

class method below, or both.

**Define class method**. When \(x_0\) is a small integer satisfying \(0 \le x_0 < b\) and \(X'\) is a natural number, calling`first:rest:`

on class`Natural`

(Natural first:rest: \(x_0\) \(X'\))

answers a natural number that represents the value \(x_0 + X' \cdot b\), while maintaining the key invariants on both subclasses:

If \(x_0\) and \(X'\) are both zero,

`first:rest:`

must answer an instance of class`NatZero`

.If either \(x_0\) or \(X'\) is nonzero,

`first:rest:`

must answer a fresh instance of class`NatNonzero`

.As always in Smalltalk, the instance is created in stages:

A new instance is created by sending a message to the

*class*. In this case, the message is`new`

.The new instance is initialized by sending it a private message. This private message is also called

`first:rest:`

, and it must initialize the instance variables that represent \(x_0\) and \(X'\).

The class method

`first:rest:`

is Smalltalk’s analog of the “smart constructor”`times10plus`

that you used on the first ML homework. Since its job is to maintain invariants, the result that it answers would be a fine thing to wrap in`validated`

.**Define private initialization method**on class`first:rest:`

`NatNonzero`

. Private method`first:rest:`

on class`NatNonzero`

has this contract:It receives small integer \(x_0\) and natural number \(X'\), such that \(x_0\) and \(X'\) are not both zero and \(0 \le x_0 < b\).

It mutates the state of

`self`

(the receiver) so the receiver now represents \(x_0 + X' \cdot b\). This means setting instance variables.It answers

`self`

.

Define private method

`first:rest:`

on class`NatNonzero`

.**Test public method**. Now that you can create natural numbers,`isZero`

**use**on both zero and nonzero natural numbers. You will write unit tests that go outside the class definitions (see the block comment in the starter code). As usual,`check-assert`

to test method`isZero`

*indent your unit tests by eight spaces*.The

`check-assert`

form works just as in \(\mu\)Scheme: it’s followed by an expression you expect to be true. But because you can’t print natural numbers yet, you can’t define any variables that hold natural numbers! Instead, use an expression to both*create*a number and then*send*it the`isZero`

message, all in one expression. A good example might be`((Natural fromSmall: 7) isZero)`

.**Define a**for debugging. To help you debug and to write unit tests, you’ll need to print the internal digits of your representation. These are`printrep`

private method*not*decimal digits; they are digits base \(b\). Define a method`printrep`

that prints the digits of your representation separated by commas. It will be easiest to implement it on both subclasses (`NatZero`

and`NatNonzero`

).A zero is printed by printing

`0`

.A nonzero natural number is printed by printing its most significant digits (\(X'\)), then printing a comma, then printing the number’s least significant digit (\(x_0\)). A comma can be printed by

`(', print)`

.

**Test**. To help you test`printrep`

interactively`fromSmall:`

and`printrep`

, we provide 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)) )`

This class, which is included in the starter code, can show you the representation that your

`fromSmall:`

method creates. For example, if you choose base 2 to start with, you should probably hope for one of the following:`-> (DebugNat of: (Natural fromSmall: 5)) ;; doesn't print a leading 0 (OK) 1,0,1 -> (DebugNat of: (Natural fromSmall: 5)) ;; does print a leading 0 (also OK) 0,1,0,1`

**Solidify**. Now that you’ve made something work interactively, it’s time to create archival unit tests. \(\mu\)Smalltalk provides a`printrep`

and`fromSmall:`

with unit tests`check-print`

form you can use to test the way something prints. Confirm your`fromSmall:`

results with unit tests. Supposing your \(b\) is a power of 10 or a power of 2, here are some sketches that may be useful:`(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*.Your unit tests will typically appear in 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`

# Arithmetic with the base and with zero

**Define base-oriented arithmetic**. Keeping in mind that (Natural first:rest: \(x_0\) \(X'\)) = \(x_0 + X' \cdot b\), complete the following algebraic laws:- \(0 \;\mbox{div}\;b = \cdots\)
- \(0 \bmod b = \cdots\)
- \(0 \cdot b = \cdots\)
- \((x_0 + X' \cdot b) \;\mbox{div}\;b = \cdots\)
- \((x_0 + X' \cdot b) \bmod b = \cdots\)
- \(N \cdot b = \cdots\)

Using the first three laws, define and test private methods

`divBase`

,`modBase`

, and`timesBase`

on class`NatZero`

.Using the remaining laws, define and test methods

`divBase`

,`modBase`

, and`timesBase`

on class`NatNonzero`

.**Implement subclass responsibilities for class**. Complete the following algebraic laws:`NatZero`

- Multiplication: \(0 \cdot n = \cdots\)
- Division: \(0 \;\mbox{div}\;n = \cdots\)
- Remainder: \(0 \bmod n = \cdots\)
- Add with carry: \(0 + 0 + c = \cdots\)
- Subtract with borrow: \(0 - 0 - 0 = \cdots\)

And consider these additional laws:

- Add with carry: \(0 + (x_0 + X' \cdot b) + c = (x_0 + X' \cdot b) + 0 + c\)
- Subtract with borrow: \(0 - 0 - 1 < 0\) (not a natural number)
- Comparison: \(0 = 0\)
- Comparison: \(0 < x_0 + X' \cdot b\), where \(x_0>0\) or \(X'>0\)

`NatZero`

:`*`

`sdivmod:with:`

`plus:carry:`

`minus:borrow:`

`compare:withLt:withEq:withGt:`

In all these examples,

*the value of self is always zero*. Exploit it.

# Addition

**Implement add with carry**on nonzero natural numbers.On class

`NatNonzero`

, implement method`plus:carry:`

as described in Appendix B of*Programming Languages: Build, Prove, and Compare.*The “add with carry” \(X+Y+c_0\) is defined as function \(\mathit{adc}(X, Y, c_0)\). That’s computed by (\(X\) plus:carry: \(Y\) \(c_0\)).Assuming \(X = X' \mathbin{\cdot}b + x_0\) and \(Y = Y' \mathbin{\cdot}b + y_0\), function \(\mathit{adc}\) is specified by this law:

\[\mathit{adc}(x_0 + X' \mathbin{\cdot}b, y_0 + Y' \mathbin{\cdot}b, c_0) = z_0 + (X' + Y' + c_1) \mathbin{\cdot}b\text{,}\] \[\begin{align}\text{where }z_0 &= (x_0 + y_0 + c_0) \bmod b\\ c_1 &= (x_0 + y_0 + c_0) \;\mbox{div}\;b \end{align}\] Bit \(c_0\) is called “carry in” and \(c_1\) is “carry out.”

If \(X\) is the receiver and \(Y\) is the argument, natural number \(X\)’ and small integer \(x_0\) are directly available in instance variables. But \(Y'\) and \(y_0\) are

*not*directly available; only \(Y\) is. Fortunately \(Y'\) and \(y_0\) can be obtained by sending messages to \(Y\).**There is no case analysis here.**It is neither necessary nor useful to interrogate \(Y\) about its form. Likewise there is**no need for double dispatch**. Just send messages to \(Y\) demanding \(Y'\) and \(y_0\), and all will be well.*Hints:*To get \(Y'\) and \(y_0\), use special-purpose methods that you have already defined.

Since Smalltalk doesn’t have

`let`

, the idiomatic way to implement the`plus:carry:`

method is to use local variables (**Correction:**earlier version had the wrong value for`sum`

):(method plus:carry: (n c) [locals sum z0 c1]

(set sum ((\(x_0\) + \(y_0\)) + c)) ;;*small-integer arithmetic*

(set z0 (sum mod: \(b\))) ;;*small-integer arithmetic*

(set c1 (sum div: \(b\))) ;;*small-integer arithmetic*

(\(\mathtt{z0} + (X' + Y' + \mathtt{c1}) \mathbin{\cdot}b\)))To create a new natural number, send

`first:rest:`

to class`Natural`

.

**Implement method**. Now that`+`

`plus:carry:`

is defined on both subclasses, go back to class`Natural`

and implement`+`

by sending`plus:carry:`

to`self`

.**Test addition**. Test both`plus:carry:`

and`+`

. Take care to avoid infinite recursion. It will help if your tests for a number`n`

include these expressions:`(n plus:carry: (Natural fromSmall: 0) 1)`

`(n plus:carry: (Natural fromSmall: 1) 0)`

# Division and decimals

**Implement method**on class`sdivmod:with:`

`NatNonzero`

. 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\).

The law for dividing a nonzero natural number by \(v\) with continuation \(K\) is

(\((X' \mathbin{\cdot}b + x_0)\) sdivmod:with: \(v\) \(K\)) \(=\)

(\(X'\) sdivmod:with: \(v\) (block (\(Q\) \(r\))

… compute \(Q'\) and \(r'\) from \(Q\), \(r\), \(x_0\), and \(v\) …

(\(K\) value:value: \(Q'\) \(r'\))))where \(Q'\) and \(r'\) are the new quotient and remainder: \[\begin{align} Q' &= (x_0 + r \mathbin{\cdot}b) \;\mbox{div}\;v + Q \mathbin{\cdot}b\\ r' &= (x_0 + r \mathbin{\cdot}b) \bmod v \end{align}\] Because \(Q'\) is a natural number, it should be built using

`first:rest`

.**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**on class`decimal`

`Natural`

. Method`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.*

# Comparison

**Implement comparison**on class`NatNonzero`

. Implement the method`compare:withLt:withEq:withGt:`

. When given two nonzero natural numbers \(X\) and \(Y\), where \(X = x_0 + X' \mathbin{\cdot}b\), \(Y = y_0 + Y' \mathbin{\cdot}b\), method`compare:withLt:withEq:withGt:`

operates according to this algebraic law: \[\begin{align} (X \; \mathtt{compare\mathord{:}withLt\mathord{:}}&\mathtt{withEq\mathord{:}withGt\mathord{:}}\; Y\; K_<\; K_=\; K_>)\\ &= \left\{ \begin{array}{l} \mbox{{($K_<$ value)}, when $\mathit{compare}(X', Y') = \mathtt{LT}$}\\ \mbox{{($K_=$ value)}, when $\mathit{compare}(X', Y') = \mathtt{EQ}$}\\ \mbox{{($K_>$ value)}, when $\mathit{compare}(X', Y') = \mathtt{GT}$}\\ \end{array} \right. \end{align}\] the \(\mathit{compare}\) function is defined by cases: \[ \mathit{compare}(X' \mathbin{\cdot}b + x_0, Y' \mathbin{\cdot}b + y_0) = \left\{ \begin{array}{l} \mathtt{LT}\mbox{, if $\mathit{compare}(X', Y') = \mathtt{LT}$}\\ \mathtt{GT}\mbox{, if $\mathit{compare}(X', Y') = \mathtt{GT}$}\\ \mathtt{EQ}\mbox{, if $\mathit{compare}(X', Y') = \mathtt{EQ}$ and $x_0 = y_0$}\\ \mathtt{LT}\mbox{, if $\mathit{compare}(X', Y') = \mathtt{EQ}$ and $x_0 < y_0$}\\ \mathtt{GT}\mbox{, if $\mathit{compare}(X', Y') = \mathtt{EQ}$ and $x_0 > y_0$}\\ \end{array} \right. \]Because \(X\) is nonzero,

**this comparison always recursively compares \(X'\) and \(Y'\).**The recursive comparison of \(X'\) with \(Y'\) needs three continuations, determined as follows:Whenever \(X' < Y'\), \(X < Y\), so the first continuation can be \(K_<\).

When \(X' = Y'\), it will be necessary to compare \(x_0\) and \(y_0\). So for the second continuation, you have to pass a block that compares \(x_0\) and \(y_0\), then sends

`value`

to \(K_<\), to \(K_=\), or to_\(K_>\).Whenever \(X' > Y'\), \(X > Y\), so the third continuation can be \(K_>\).

As before, \(x_0\) and \(X'\) are accessible directly in instance variables, but \(y_0\) and \(Y'\) can be obtained only by sending messages to \(Y\).

Implement method

`compare:withLt:withEq:withGt:`

on class`NatNonzero`

.**Implement subclass responsibilities inherited from**. On class`Magnitude`

`Natural`

, implement the methods`<`

and`=`

that are required by class`Magnitude`

. Each method should simply send`compare:withLt:withEq:withGt:`

to`self`

, with appropriate continuations. One line each should be sufficient.

**Test comparisons**. The starter code for class`Natural`

includes this private method:`(method compare-symbol: (aNat) (self compare:withLt:withEq:withGt: aNat {'LT} {'EQ} {'GT}))`

Use

`compare-symbol:`

to test*at least*the following:Zero with zero

Zero with nonzero

*All five*nonzero-with-nonzero cases shown in the specification of the \(\mathit{compare}\) function above

# Subtraction

**Implement**on class`minus:borrow:`

`NatNonzero`

.The “subtract with borrow” \(X+Y-c\) is defined as function \(\mathit{sbb}(X, Y, c)\). That’s computed by (\(X\) minus:borrow: \(Y\) \(c\)). Here \(c\) is called “the borrow bit.”

^{2}The operation is described by these laws: \[\begin{align*} \mathit{sbb}(X' \mathbin{\cdot}b + x_0,Y' \mathbin{\cdot}b + y_0, c) &= \mathit{sbb}(X',Y', 0) \mathbin{\cdot}b + x_0 - y_0 - c \text{, }&\text{if $x_0 - y_0 - c \ge 0$}\\ \mathit{sbb}(X' \mathbin{\cdot}b + x_0, Y' \mathbin{\cdot}b + y_0, c) &= \mathit{sbb}(X', Y', 1) \mathbin{\cdot}b + b + x_0 - y_0 - c \text{, }&\text{if $x_0 - y_0 - c < 0$} \end{align*}\] Notice the case analysis here: If the least significant digits can be subtracted (including the borrow bit), without going negative, then the recursive call borrows \(0\); otherwise the recursive call borrows \(1\) and adds the base \(b\) to a non-recursive computation of the lower-order digit \(b + x_0 - y_0 - c\). This case analysis is best implemented using`ifTrue:ifFalse:`

.**Implement**on class`subtract:withDifference:ifNegative:`

`Natural`

. I recommend implementing`subtract:withDifference:ifNegative:`

by first using`<`

to find a possible negative result, then sending`minus:borrow:`

to`self`

. Implement method`subtract:withDifference:ifNegative:`

just once, on class`Natural`

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

and for the negative case,`check-error`

.

# Multiplication

**Multiply a natural number by a digit**. To multiply two natural numbers, we eventually have to multiply digits. But multiplying digits pairwise is fraught; its far easier to define a new method that multiplies a natural number by a single digit.Multiplication by a digit satisfies this algebraic law: \[\begin{align} (x_0 + X' \mathbin{\cdot}b) \mathbin{\cdot}d = (p \bmod b) &+ (X' \mathbin{\cdot}d + (p \;\mbox{div}\;b)) \mathbin{\cdot}b\text{,}\\ &\text{where } p = x_0 \mathbin{\cdot}d\text{.} \end{align}\] Because \(p\) is the product of two digits, it is possible that \(p \ge b\). In this case, the recursion becomes gnarly: first we multiply \(X'\) by \(d\) recursively, but then we have to add the digit \(p \;\mbox{div}\;b\). It is cleaner and more efficient to define a method that does the multiplication and the addition at one go:

(\(X\) timesDigit:plus: \(d\) \(r\)) \({} = X \mathbin{\cdot}d + r\)

where \(d\) and \(r\) are small integers satisfying \(0 \le d < b\) and \(0 \le r < b\).

Implement

`timesDigit:plus:`

on class`NatZero`

(where \(X=0\))Complete the following algebraic law:

\[\begin{align} (x_0 + X' \mathbin{\cdot}b) &\mathbin{\cdot}d + r = \cdots\text{,}\\ &\text{where } p' = x_0 \mathbin{\cdot}d + r\text{.} \end{align}\]

Using the algebraic law, implement

`timesDigit:plus:`

on class`NatNonzero`

.

**Test method**Using`timesDigit:plus:`

`check-print`

with both zero and nonzero numbers as receviers, write unit tests for`timesDigit:plus:`

.

**Implement multiplication**on class`NatNonzero`

. Multiplication should be implemented**without case analysis.**Multiplication of any nonzero number \(x_0 + X' \mathbin{\cdot}b\) by*any*natural number \(Y\) obeys this algebraic law: \[ (x_0 + X' \mathbin{\cdot}b) \mathbin{\cdot}Y = (x_0 \cdot Y) + (X' \cdot Y) \cdot b \] This law works*without*interrogating \(Y\) about its form of data.The right-hand side of the law includes three products:

Product \((x_0 \cdot Y)\) can be implemented by (\(Y\) timesDigit:plus: \(x_0\) \(0\)). (If you try to compute it by promoting \(x_0\) to a natural number and then multiplying, you’ll run into infinite recursion.)

Product \(X' \cdot Y\) can be computed recursively by sending the

`*`

message. The recursion terminates because the number of digits in the receiver is getting smaller.Product \((X' \cdot Y) \cdot bf\) should

*not*be computed recursively; to multiply a natural number by \(b\) in constant time, send it the`timesBase`

message.

Because there’s just one recursion, total time is quadratic, which is the best you can hope for—a quadratic number of digit-by-digit multiplications are required. If both

`timesDigit:plus:`

and`*`

are implemented efficiently, you’ll be able to compute \(99^{99}\) in a tenth of a second.**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`

.

# 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.