# Starter code and invariants

**Inspect classes**. Look over the three large-integer classes in your`bignum.smt`

file.^{1}Both

`LargePositiveInteger`

and`LargeNegativeInteger`

are subclasses of`LargeInteger`

. The class determines the sign, and these subclasses don’t need their own instance variables: they inherit`magnitude`

(a natural number) from`LargeInteger`

.Zero isn’t special. A zero could be an instance of either subclass, and it’s up to you to be sure that no program can tell the difference between “positive zero” and “negative zero”.

^{2}

**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 `Integer`

page 660 `LargeInteger`

page 676 Mark these pages so you can refer to them easily.

**Choose and document your invariants**. The`LargeInteger`

class defines an`invariant`

method that says`magnitude`

is a natural number. For the subclasses, you must decide what you want to do about zero. Your choices are:Zero is always an instance of

`LargePositiveInteger`

Zero is always an instance of

`LargeNegativeInteger`

Zero may be an instance of either subclass, and it is up to you to ensure that all methods treat “positive zero” and “negative zero” as indistinguishable.

In light of your choice, update the

`invariant`

method of each subclass to replace the`leftAsExercise`

message. The`invariant`

method can mention the instance variable`magnitude`

.

# Zeroes and signs

**Implement**. The starter code defines`isZero`

`isZero`

as a subclass responsibility. The implementation should depend on your invariant.If zero can be an instance of only one subclass, leave

`isZero`

as a subclass responsibility, and define`isZero`

on each subclass. Each subclass definition should answer`true`

or`false`

without further testing.If your invariant permits zero to be an instance of either subclass, implement

`isZero`

once, on the superclass (`LargeInteger`

).

**Implement sign-query methods**. On each subclass, implement methods`isNegative`

,`isNonnegative`

, and`isStrictlyPositive`

. These methods must implement the contracts described in the`Number`

protocol, which appears in Figure 10.17 on page 659.By virtue of being defined on a subclass, each method knows the receiver’s sign. Your invariants may also help you—for example, if zero is always an instance of

`LargeNegativeInteger`

, then`LargePositiveInteger`

can reply`true`

to`isStrictlyPositive`

, unconditionally.**Test sign queries**on nonnegative integers. Using the`fromSmall:`

class method included in the starter code write`check-assert`

unit tests for the three query methods. Because methods`negated`

and`+`

are not yet implemented, you can test nonnegative inputs only.

# Printing

**Define method**. Define a`print`

`print`

method that shows the sign (if negative) and the digits of a large integer. Take care that zero always prints as`0`

, never as`-0`

.

# Negative numbers

**Implement method**. To create a new large signed integer, send message`negated`

`withMagnitude:`

to the*subclass*of the instance you want to create.**Test negation**. Clone and modify your`check-assert`

sign-query tests, and change each one to send`negated`

to the large integer. Alter your expected answers as appropriate.**Test sign queries**on non-positive integers. Use the`negated`

method with`fromSmall:`

to create non-positive large integers and to test all four sign queries. Include tests of “negative zero” and of double negation.**Test printing**with both signs.Write

`check-print`

tests where you negate large integers of both signs. Since`fromSmall:`

still accepts only nonnegative numbers, to negate a negative number you’ll need to send`negated`

twice.Write a

`check-print`

test to confirm that`((LargeInteger fromSmall: 0) negated)`

prints as`0`

, not`-0`

.

# Multiplication

**Implement multiplication**. This is your first encounter with double dispatch. You need to be able to multiply both positive and negative large integers by both positive and negative large integers. Multiplication of large signed integers is governed by these laws, where \(N\) and \(M\) are natural numbers: \[\begin{aligned} +N \mathbin{\cdot}+M &= +(N \mathbin{\cdot}M)\\ +N \mathbin{\cdot}-M &= -(N \mathbin{\cdot}M)\\ -N \mathbin{\cdot}+M &= -(M \mathbin{\cdot}N)\\ -N \mathbin{\cdot}-M &= +(M \mathbin{\cdot}N) \end{aligned}\]Magnitudes \(M\) and \(N\) can be multiplied by sending them the

`*`

message, which is part of the protocol for class`Natural`

.On each subclass, define the

`*`

method and the two sign-aware multiplication methods`multiplyByLargePositiveInteger:`

and`multiplyByLargeNegativeInteger:`

.*All three methods should be implemented without any conditionals or other case analysis.*All the case analysis you need is supplied by method dispatch.**Test double dispatch in multiplication**. As an initial test, you can reuse the strategies you used to test natural numbers. And you can use`ghci`

to create test cases that use both positive and negative integers. But there are many more methods in play here, and you need to test each one. (Smalltalk code is very vulnerable to copy-paste errors.)To test every method, you must hit every case of double dispatch. We recommend that for each case, you run it using the

`messageTrace`

technique described in the homework handout:`({((LargeInteger fromSmall: 4) * (LargeInteger fromSmall: 5))} messageTrace)`

The trace will confirm that message

`multiplyByLargePositiveInteger`

is being sent to class`LargePositiveInteger`

.

# Addition

**Implement addition**. Addition requires more double dispatch. You need to be able to add both positive and negative large integers to both positive and negative large integers. Addition of large signed integers is governed by these laws, where \(N\) and \(M\) are natural numbers: \[\begin{aligned} +N + +M &= +(N+M) \\ +N + -M &= +(N-M)\mbox{, when $N \ge M$}\\ +N + -M &= -(M-N)\mbox{, when $N < M$}\\ -N + +M &= +(M-N)\mbox{, when $M \ge N$}\\ -N + +M &= -(N-M)\mbox{, when $M < N$}\\ -N + -M &= -(M+N) \end{aligned}\]Magnitudes \(M\) and \(N\) can be added or subtracted by sending them one of the messages

`+`

,`-`

, or`subtract:withDifference:ifNegative:`

, which are part of the protocol for class`Natural`

.On each subclass, define the

`+`

method and the two sign-aware addition methods`addLargePositiveIntegerTo:`

and`addLargeNegativeIntegerTo:`

.There are two easy cases: large positive plus large positive and large negative plus large negative. Like multiplication, these cases don’t require any conditionals or other case analysis.

For the mixed cases, positive plus negative and vice versa, each method needs one conditional to find out if a difference is going negative. You can implement that conditional in continuation-passing style, using

`Natural`

method`subtract:withDifference:ifNegative:`

. Or if you don’t mind making two passes over the digits, you could use methods`<`

and`ifTrue:ifFalse:`

(which ultimately is also continuation-passing style).

**Test double dispatch in addition**. To make sure double dispatch is correct, your tests should all the relevant algebraic laws. As with multiplication, test every method.If your natural numbers have been well tested, you shouldn’t need to worry about testing that the magnitude grows correctly. But if you wish, you can copy your natural-number tests and modify them to use large integers. You can also change their signs.

# Negative small integers

**Test negative integers with**. Now that addition works, the`fromSmall:`

`fromSmall:`

class method should work with negative arguments. Test it in two ways:Using

`check-assert`

, test all four sign-query methods on a large integer created from a small negative integer.Using

`check-print`

, test that a large integer created from a small negative integer prints as expected.

# Division and modulus

**Implement modulus**. If \(I\) is a large signed integer and \(v\) is a small nonzero integer, \[\begin{aligned} I \bmod v &= I - (v \mathbin{\cdot}(I \;\mbox{div}\;v)) \end{aligned}\]Implement this law as method

`smod:`

on class`LargeInteger`

. Remember this: before you can multiply \(v\) by \(I \;\mbox{div}\;v\), you have to promote \(v\) to a large integer.**Test division and modulus**. Every case of the rounding rules is tested by one of the following examples:`;; tests given with the homework (check-print ( 7 div: 4) 1) (check-print (-7 div: 4) -2) (check-print ( 7 div: -4) -2) (check-print (-7 div: -4) 1) (check-print ( 7 mod: 4) 3) (check-print (-7 mod: 4) 1) (check-print ( 7 mod: -4) -1) (check-print (-7 mod: -4) -3)`

Copy these tests into your

`bignum.smt`

file, and confirm that they pass.

# Finishing up

**Run randomly generated integration tests**. Just as for`Natural`

, we provide some tests for large integers. Our randomly generated tests can be run as follows:`echo '(use bignum.smt) (use bignum-tests.smt)' | usmalltalk -qq`

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