CS 105:	Modules	Calendar	Office Hours	Syllabus	ML	Coding Style	Coding Rubric

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

Class	Page
`Magnitude`	page 659
`Natural`	page 662

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 invariant method on each subclass. On class 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.
1. Define the invariant method on class NatZero.
2. Define the invariant method on class NatNonzero.
Study the validated method. Past students have written,

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 first:rest: on class Natural. When $x_0$ is a small integer satisfying $0 \le x_0 < b$ and $X'$ is a natural number, calling

(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:
  1. A new instance is created by sending a message to the class. In this case, the message is new.
  2. 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 first:rest: on class 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.
Why two first:rest: methods?

Why implement first:rest: in both Natural (class method) and NatNonzero (instance method)?
- For complicated initialization, we always need two methods: a class method to create a fresh instance, and an instance method to initialize instance variables.
- Putting the class method on class Natural helps make it safe to use the method even when $x_0$ and $X'$ are both zero. That design is going to simplify the code you write later.
Test public method isZero. Now that you can create natural numbers, use check-assert to test method isZero 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, 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 printrep private method for debugging. To help you debug and to write unit tests, you’ll need to print the internal digits of your representation. These are 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 printrep interactively. To help you test 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 printrep and fromSmall:with unit tests. Now that you’ve made something work interactively, it’s time to create archival unit tests. $\mu$Smalltalk provides a 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.
Avoid this common mistake

Here and below, avoid the common mistake of returning an object that represents the right number but is of the wrong class. Methods divBase and timesBase must answer a natural number; method modBase must answer a small integer. The mistake can be prevented by writing a check-assert unit test that tests the class of a result, something like this one:
```
  (check-assert (3 isKindOf: SmallInteger))
```
The isKindOf: message is in the protocol for all objects, which is described in the book in figure 10.9 on page 646.
Implement subclass responsibilities for class NatZero. Complete the following algebraic laws:
- 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$
Using the laws above, implement the remaining subclass responsibilities on class 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 sdivmod:with: on class 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 sdivmod:with: using 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 decimal on class Natural. Method decimal must answer a standard List. To convert self to a list of decimal digits, I recommend using mutable local variables:
1. Initialize an empty, mutable list.
2. Initialize a local variable $Z$ equal to self.
3. 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:.
4. 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.
5. Answer the list.
Change the print method defined on class Natural so it sends print-with-decimal, not printrep.
Unit-test the new print with true decimals. Check your work by cloning and modifying your old check-print unit tests:
1. Copy and paste your unit tests for fromSmall:, plus:carry:, and +.
2. 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
```
3. 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 Magnitude. On class 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 minus:borrow: on class 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.”² 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 subtract:withDifference:ifNegative: on class 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$.
1. Implement timesDigit:plus: on class NatZero (where $X=0$)
2. 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}\]
3. Using the algebraic law, implement timesDigit:plus: on class NatNonzero.
Test method timesDigit:plus: Using 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.
The test cases for large numbers were created using Haskell. Haskell has an implementation of bignums that uses an optimized representation and runs at native-code speed. Haskell uses standard infix arithmetic, like ML, plus infix ^ is “raise to the power”. The answer for the third test case above was generated as follows:
```
$ ghci
GHCi, version 9.2.2: https://www.haskell.org/ghc/  :? for help
ghci> 99^99    369729637649726772657187905628805440595668764281741102430259972423552570455277523421410650010128232727940978889548326540119429996769494359451621570193644014418071060667659301384999779999159200499899
ghci>
(CTRL+D)
Leaving GHCi.
```
Use ghci to make test cases that use large numbers but finish reasonably quickly for your choice of representation and base.

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.

You can even try base 2, but computing hundred-digit numbers may take a second or two.↩
A bit strange, but the letter $b$ is taken; it stands for the base.↩

Natural Numbers Using Subclasses: A Step-by-Step Guide

From starter code to printing

Why two `first:rest:` methods?

Arithmetic with the base and with zero

Avoid this common mistake

Addition

Division and decimals

Comparison

Subtraction

Multiplication

Finishing up

From starter code to printing

Why two first:rest: methods?

Arithmetic with the base and with zero

Avoid this common mistake

Addition

Division and decimals

Comparison

Subtraction

Multiplication

Finishing up

Why two `first:rest:` methods?