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

Large Integers: A Step-by-Step Guide

Starter code and invariants

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

  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.

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

  1. Implement isZero. The starter code defines 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).

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

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

  1. Define method print. Define a 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

  1. Implement method negated. To create a new large signed integer, send message withMagnitude: to the subclass of the instance you want to create.

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

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

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

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

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

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

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

  1. Test negative integers with fromSmall:. Now that addition works, the 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

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

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

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

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

  1. They are included in the array starter code and the subclass starter code.↩

  2. Except by using one of the reflective methods, like class, isKindOf:, and so on.↩