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

Introduction

Mixed arithmetic is the capstone of the assignment.

You seamlessly allow arithmetic and relational operators on a mix of small and large integers.
You extend small-integer arithmetic so that when an intermediate result doesn’t fit in a machine word, it automatically “fails over” to large-integer arithmetic.

You don’t define any new classes; instead, you use addSelector:withMethod: to extend or modify existing classes.

Do not modify file bignum.smt. Instead, get ready by creating a new, empty file mixnum.smt. There is nothing to copy into the file.

Class `SmallInteger`

Implement promotion. To implement a binary method on combination of small and large integers, you first promote the small integer to large, then use the corresponding large-integer method. You will add a new method asLargeInteger to class SmallInteger. (It is already defined on class LargeInteger, where it answers self.)
- The method on class SmallInteger is added using the reflection API addSelector:withMethod:, by executing the following code at top level:
```
(SmallInteger addSelector:withMethod: 'asLargeInteger
   (compiled-method () (... make a large integer from `self` ...)))
```
Complete the code and add it to your file mixnum.smt.
Study SmallInteger. Allocating objects and sending messages to them gets you only so far. Eventually you have to get the machine to do things with bits. In \(\mu\)Smalltalk, the machine is invoked by a syntactic form with the keyword primitive. This form looks like a function call in Impcore: it names the primitive and gives one or more arguments.

Study these excerpts from the definition of the SmallInteger class:
```
(class SmallInteger
    [subclass-of Integer] ; primitive representation
    ...
    (method negated    ()  (0 - self))
    (method print      ()  (primitive printSmallInteger self))
    (method +          (n) (primitive + self n))
    (method -          (n) (primitive - self n))
    (method *          (n) (primitive * self n))
    (method =          (n) (primitive sameObject self n))
    (method <          (n) (primitive < self n))
    (method >          (n) (primitive > self n))
)
```
You will use some of these same primitives in new methods that you will define. And later you will replace some of the primitives with more complicated primitives that detect overflow, as described in Exercise 39.

Multiplication

Implement mixed multiplication The laws for mixed multiplication say only what needs to be promoted. All the laws use the same notation:

\(I\) A large integer

\(i\) A small integer

\(P(i)\) A large integer obtained by promoting a small integer (sending asLargeInteger)

\(\mathbin{\cdot_{\scriptscriptstyle L}}\) Multiplication by a large integer

\(\mathbin{\cdot_{\scriptscriptstyle S}}\) Multiplication by a small integer

\(\mathbin{\cdot_{\scriptscriptstyle LL}}\) Multiplication of two large integers

\(\mathbin{\cdot_{\scriptscriptstyle SS}}\) Multiplication of two small integers (a primitive!)

\(\mathbin{\cdot}\) Multiplication not otherwise specified

The \(\mathbin{\cdot_{\scriptscriptstyle SS}}\) operation, which multiplies two small integers, is the only primitive. Everything else is just allocating objects and sending messages to them.

The multiplication laws start with four laws which encode the double dispatch that method * must implement: \[\begin{aligned} i_1 \mathbin{\cdot}i_2 &= i_2 \mathbin{\cdot_{\scriptscriptstyle S}}i_1\\ i_1 \mathbin{\cdot}I_2 &= I_2 \mathbin{\cdot_{\scriptscriptstyle S}}i_1 \\ I_1 \mathbin{\cdot}i_2 &= i_2 \mathbin{\cdot_{\scriptscriptstyle L}}I_1 \\ I_1 \mathbin{\cdot}I_2 &= I_2 \mathbin{\cdot_{\scriptscriptstyle L}}I_1 \end{aligned}\] The remaining multiplication laws specify what happens when the class of the argument is known: \[\begin{aligned} i_1 \mathbin{\cdot_{\scriptscriptstyle S}}i_2 &= i_2 \mathbin{\cdot_{\scriptscriptstyle SS}}i_1 \text{, ignoring the possibility of overflow}\\ I_1 \mathbin{\cdot_{\scriptscriptstyle S}}i_2 &= I_1 \mathbin{\cdot}P(i_2) \\ i_1 \mathbin{\cdot_{\scriptscriptstyle L}}I_2 &= P(i_1) \mathbin{\cdot}I_2 \\ I_1 \mathbin{\cdot_{\scriptscriptstyle L}}I_2 &= I_1 \mathbin{\cdot_{\scriptscriptstyle LL}}I_2 \text{, as implemented in exercise 38} \end{aligned}\]

Notice the recursion: \(\mathbin{\cdot}\) can call \(\mathbin{\cdot_{\scriptscriptstyle S}}\) which can call \(\mathbin{\cdot}\). To prevent infinite recursion, something has to get smaller at each recursive call:

One thing that might get smaller is the number of small-integer operands to the multiplication.
The other thing that might get smaller is the number of arguments whose sizes are unknown. A specific method like multiplyByLargeNegativeInteger: (\(\mathbin{\cdot_{\scriptscriptstyle L}}\)) has no unknown arguments, where * (\(\mathbin{\cdot}\)) has one, so multiplyByLargeNegativeInteger is smaller.

At each recursive call, either the number of small integers gets smaller, or the number of unknown arguments gets smaller while the number of small integers stays the same.

Using these laws and message addSelector:withMethod:, add methods multiplyBySmallInteger:, multiplyByLargePositiveInteger:, multiplyByLargeNegativeInteger:, and * to class SmallInteger, and add method multiplyBySmallInteger: to class LargeInteger. Be aware of which methods send messages and which methods invoke a primitive. Don’t edit any existing code. Add everything by sending addSelector:withMethod: messages to the existing classes, in mixnum.smt.

Test mixed multiplication. As with large-integer multiplication and addition, you need to test every method. Using the messageTrace technique described in the homework handout, continue to confirm that dispatch is working the way you expected. For example, given
```
  ({((LargeInteger fromSmall: 4) * 5)} messageTrace)
```
The trace will confirm that it sends message * to an instance of class LargePositiveInteger and message multiplyByLargePositiveInteger to an instance of class SmallInteger.

Test all five mixed-multiplication methods using check-print. Add your unit tests to file mixnum.smt.

Addition

Implement mixed addition. Addition uses the exact same promotion laws as multiplication, just with different operations. Using message addSelector:withMethod:, add methods addSmallIntegerTo:, addLargePositiveIntegerTo:, addLargeNegativeIntegerTo:, and + to class SmallInteger, and add method addSmallIntegerTo: to class LargeInteger. As before, be aware of which methods send messages and which methods invoke a primitive.

Put your added methods in file mixnum.smt.
Test mixed addition. Repeat the process described for multiplication, testing each added method one at a time. Confirm the messages you are sending by using messageTrace. Add unit tests to file mixnum.smt.

Overflow

Implement multiplication with overflow. You will now alter the multiplication of small integers so it can deal with overflow. To make this possible, you will have to use a different primitive. Instead of the * primitive, you will use the mulWithOverflow primitive described on page 732. You will find a short example there as well. You will use addSelector:withMethod: to overwrite one of the methods you have already defined with this new compiled method:

(compiled-method (\(i\))
((primitive mulWithOverflow self \(i\) {\((P(\mathtt{self})\mathbin{\cdot}{}i)\)}) value)))

This code works as follows:
- The primitive returns a block.
  - If the multiplication doesn’t overflow, the block holds the product.
  - If the multiplication does overflow, the block is the argument block.
- No matter what block comes back from the primitive, value is sent to it.
If multiplication doesn’t overflow, the method returns the product. If multiplication does overflow, the receiver gets promoted (making the total number of small integers smaller) and the whole cycle starts again.

Add code to your mixnum.smt file to replace method multiplyBySmallInteger: on class SmallInteger.
Test multiplication with overflow. Add unit tests to file mixnum.smt.
Multiplication-testing tricks

All the integer classes inherit from Number, so if you start with a small integer and send it raisedToInteger: with a large power, it should eventually overflow and switch seamlessly to a large integer. Something like (10 raisedToInteger: 40) is definitely too large for a single machine word.

If your base is a power of 10, also test something like (2 raisedToInteger: 100) or (9 raisedToInteger: 99). Something that’s not a multiple of your base. If you like, you can get correct answers from ghci.

You will also want to test overflow in a negative direction. A good technique there is to start with a small, negative literal and use timesRepeat: (textbook, Figure 10.18 on page 660) to keep multiplying by a small, positive integer until the product overflows.

If your multiplication of natural numbers is inefficient, you may run into the CPU cap. Put long-running tests in file longtests.smt, and run them using
```
echo '(use bignum.smt) (use mixnum.smt) (use longtests.smt)' |
   env BPCOPTIONS=nothrottle usmalltalk -qq
```
Implement addition with overflow. Using the same model as you used for multiplication, use addSelector:withMethod: to replace the method that adds two small integers (method addSmallIntegerTo: on class SmallInteger). Instead of the + primitive, use addWithOverflow. In case of overflow, your new method should promote self to a large integer.

Add code to mixnum.smt.
Test addition with overflow. Add unit tests to file mixnum.smt.
Addition-testing tricks

To test overflow, you need to get large numbers, but large numbers are harder to get by addition than by multiplication. To help you, we provide a method that multiplies an integer by 10, using only addition:
```
(Integer addSelector:withMethod: 'times10
  (compiled-method () [locals two four]
     (set two (self + self))
     (set four (two + two))
     ((four + four) + two)))

        (check-print (((10101 times10) times10) times10) 10101000)
```
This method will help you write your unit tests.
Implement subtraction and negation with overflow. Like addition and multiplication, subtraction can overflow. On most numbers, subtraction is implemented by a combination of addition and negation, using the law \[I_1 - I_2 = I_1 + (-I_2)\text.\] Unfortunately doesn’t provide a negation primitive, so in small integers, subtraction is primitive, and negation is implemented using the law \[-i = 0 - i\text.\] Both methods - and negated have to be reimplemented.

You might think that either method could be primitive and implemented in terms of the other. But there is a treacherous loop here: promotion \(P(i)\) uses negated. The only safe way to proceed is as follows:
1. A small integer \(n\) can be negated safely by sending subWithOverflow to \(0\) with argument \(n\). If the subtraction overflows, the overflow block should answer ((\(n\) asLargeInteger) negated)
Using addSelector:withMethod:, replace the existing negated method on class SmallInteger with a new compiled method that implements this idea.
1. Now replace - on SmallInteger with the version of - originally defined on class Number:
  
  (compiled-method (y) (self + (y negated))))
Put all code in file mixnum.smt.

Finishing up

Confirm formatting of unit tests. Scan mixnum.smt and make sure all unit tests are indented 8 spaces.

\(I\)	A large integer
\(i\)	A small integer
\(P(i)\)	A large integer obtained by promoting a small integer (sending `asLargeInteger`)
\(\mathbin{\cdot_{\scriptscriptstyle L}}\)	Multiplication by a large integer
\(\mathbin{\cdot_{\scriptscriptstyle S}}\)	Multiplication by a small integer
\(\mathbin{\cdot_{\scriptscriptstyle LL}}\)	Multiplication of two large integers
\(\mathbin{\cdot_{\scriptscriptstyle SS}}\)	Multiplication of two small integers (a primitive!)
\(\mathbin{\cdot}\)	Multiplication not otherwise specified

Introduction

Class SmallInteger

Multiplication

Addition

Overflow

Multiplication-testing tricks

Addition-testing tricks

Finishing up

Class `SmallInteger`