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

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

Class	Page
`Magnitude`	page 659
`Natural`	page 662
`Array`	pages 653, 656, and 657

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²
To count meaningful digits, we refer to the “degree” of the representation.
1. 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.
1. 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.
1. 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.
2. Implement digit:put:, and makeEmpty:.
3. Implement doDigitIndices:.
4. Implement degree.
5. Implement trim, which sets the degree as small as possible given the current contents of the digits.
6. 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 digits: with printrep. To print your representation, method 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 invariant method . Class 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 zero
- The 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 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 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:
1. A new instance is created by sending a message to the class.
2. 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 mod 10~~ $k \bmod b$ to temp and replace $k$ by ~~k div 10~~ $k \;\mbox{div}\;b$, where $b$ is the base of natural numbers.
You can now answer ((self new) digits: temp).

Test class method fromSmall:. 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.

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 subtract:withDifference:ifNegative. If the receiver is $X$ and the argument is $Y$, the 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.
1. Make a copy of the receiver.
2. Mutate the copy in place by sending it setSdiv:remainder.
3. 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 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. 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.

Multiplication

Implement multiplication. Multiplication follows the same pattern as addition and subtraction:
1. 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.
2. Using a doubly nested doDigitIndices: loop, mutate $Z$ until all the partial products have been accumulated.
3. 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.
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.
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.

You can even try base 2, but computing hundred-digit numbers may take a second or two.↩
Why not have all digits be meaningful? Because if you always assume that all digits are meaningful, the space you use will double at every multiplication.↩