Smalltalk80LanguageImplementation:Chapter 08

Chapter 8 Numerical Classes

Numerical Classes

Object

    Magnitude
        Character
        Date
        Time

        Number***
            Float***
            Fraction***
            Integer***
                LargeNegativeInteger***
                LargePositiveInteger***
                SmallInteger***

        LookupKey
            Association

    Link

        Process

    Collection

        SequenceableCollection
            LinkedList

                Semaphore

            ArrayedCollection
                Array

                Bitmap
                    DisplayBitmap

                RunArray
                String
                    Symbol
                Text
                ByteArray

            Interval
            OrderedCollection
                SortedCollection
        Bag
        MappedCollection
        Set
            Dictionary
                IdentifyDictionary

    Stream
        PositionableStream
            ReadStream
            WriteStream
                ReadWriteStream
                    ExternalStream
                        FileStream

        Random***

    File
    FileDirectory
    FilePage

    UndefinedObject
    Boolean
        False
        True

    ProcessorScheduler
    Delay
    SharedQueue

    Behavior
        ClassDescription
            Class
            MetaClass

    Point
    Rectangle
    BitBit
        CharacterScanner

        Pen

    DisplayObject
        DisplayMedium
            Form
                Cursor
                DisplayScreen
        InfiniteForm
        OpaqueForm
        Path
            Arc
                Circle
            Curve
            Line
            LinearFit
            Spline

One of the major goals of the Smalltalk programming system is to apply a single metaphor for information processing as uniformly as possible. The Smalltalk metaphor, as described in earlier chapters, is one of objects that communicate by sending messages. This metaphor is very similar to the one used in Simula for implementing simulation systems. One of the greatest challenges to the application of the Smalltalk metaphor to all aspects of a programming system has been in the area of arithmetic. Simula used the object/message metaphor only for the higher level interactions in the simulations it implemented. For arithmetic, as well as most algorithmic control structures, Simula relied on the embedded Algol programming language with its built-in number representations, operations, and syntax. The contention that even the addition of two integers should be interpreted as message-sending met with a certain amount of resistance in the early days of Smalltalk. Experience has demonstrated that the benefits of this extreme uniformity in the programming language outweigh any inconvenience in its implementation. Over several versions of Smalltalk, implementation techniques have been developed to reduce the message-sending overhead for the most common arithmetic operations so that there is now almost no cost for the benefits of uniformity.

Objects that represent numerical values are used in most systems done in Smalltalk (as with most other programming languages). Numbers are naturally used to perform mathematical computations; they are also used in algorithms as indices, counters, and encodings of states or conditions (often called flags). Integral numbers are also used as collections of binary digits (bits) that perform boolean masking operations with each other.

Each different kind of numerical value is represented by a class. The number classes have been implemented so that all numbers behave as if they were of the most general type. The actual class of a particular number object is determined by how much of the full generality is needed to represent its value. Therefore the external protocol of all number objects is inherited from the class Number. Number has three subclasses: Float, Fraction, and Integer. Integer has three subclasses: SmallInteger, LargePositiveInteger, and LargeNegativeInteger. Integral numbers provide further protocol to support treating the number as a sequence of bits. This protocol is specified in the class Integer. Numbers in the system are instances of Float, Fraction, SmallInteger, LargePositiveInteger, or LargeNegativeInteger. Classes Number and Integer specify shared protocol, but they do not specify particular representations for numeric values. Therefore no instances of Number or Integer are created.

Unlike other objects that may change their internal state, the only state of a number is its value, which should never change. The object 3, for example, should never change its state to 4, or disastrous effects could occur.

Protocol of the Number Classes

Number defines the protocol of all numeric objects. Its messages support standard arithmetic operations and comparisons. Most of these must be implemented by subclasses of Number since they depend on the actual representation of values.

The protocol of arithmetic messages consists of the usual binary operators such as +, -, * and /, and several unary and keyword messages for computing the absolute value of a number, the negation of a number, or the integer quotient or remainder of a number. The category for arithmetic messages is as follows.

arithmetic
+ aNumber	Answer the sum of the receiver and the argument, aNumber.
- aNumber	Answer the difference between the receiver and the argument, aNumber.
* aNumber	Answer the result of multiplying the receiver by the argument, aNumber.
/ aNumber	Answer the result of dividing the receiver by the argument, aNumber. Note that since as much precision as possible is retained, if the division is not exact, the result will be an instance of Fraction.
// aNumber	Answer the integer quotient defined by division with truncation toward negative infinity.
\\ aNumber	Answer the integer remainder defined by division with truncation toward negative infinity. This is the modulo operation.
abs	Answer a Number that is the absolute value (positive magnitude) of the receiver.
negated	Answer a Number that is the negation of the receiver.
quo: aNumber	Answer the integer quotient defined by division with truncation toward zero.
rem: aNumber	Answer the integer remainder defined by division with truncation toward zero.
reciprocal	Answer 1 divided by the receiver. Report an error to the user if the receiver is 0.
Number instance protocol

Some examples follow.

expression	result
1 +10	11
5.6 -3	2.6
5 - 2.6	2.4
(-4) abs	4
6 / 2	3
7 /2	(7/2), a Fraction with numerator 7 and denominator 2
7 reciprocal	(1/7), a Fraction with numerator 1 and denominator 7

Arithmetic messages that return integral quotients and remainders from a division operation follow two conventions. One convention truncates the resulting number toward zero, the other toward negative infinity. These are the same for positive results since zero and negative infinity are in the same direction. For negative results, the two conventions round in different directions. The protocol for Number provides for both conventions.

The following table shows the relationships among the selectors.

result	truncate toward negative infinity	truncate toward zero
quotient	//	quo:
remainder	\\	rem:

Examples include:

expression	result
6 quo: 2	3
7 quo: 2	3
(7 quo: 2) + 1	4
7 quo: 2 + 1	2
7 rem: 2	1
7 // 2	3
7 \\ 2	1
7 \\ 2 + 1	2

The result of quo:, rem:, or // is always to return a value whose sign is positive if the receiver and argument have the same sign, and negative if their signs are different. \\ always produces a positive result.

Additional mathematical functions are

mathematical functions
exp	Answer a floating point number that is the exponential of the receiver.
In	Answer the natural log of the receiver.
log: aNumber	Answer the log base aNumber of the receiver.
floorLog: radix	Answer the floor of the log base radix of the receiver, where the floor is the integer nearest the receiver toward negative infinity.
raisedTo: aNumber	Answer the receiver raised to the power of the argument, aNumber.
raisedToInteger: anInteger	Answer the receiver raised to the power of the argument, anInteger, where the argument must be a kind of Integer.
sqrt	Answer a floating point number that is the positive square root of the receiver.
squared	Answer the receiver multiplied by itself.
Number instance protocol

Some examples are

expression	result
2.718284 In	1.0
6 exp	403.429
2 exp	7.38906
7.38906 In	1.99998 (that is, 2)
2 log: 2	1.0
2 floorLog: 2	1
6 log: 2	2.58496
6 floorLog: 2	2
6 raisedTo: 1.2	8.58579
6 raisedToInteger: 2	36
64 sqrt	8.0
8 squared	64

Properties of numbers that deal with whether a number is even or odd and negative or positive can be tested with the following messages.

testing
even	Answer whether the receiver is an even number.
odd	Answer whether the receiver is an odd number.
negative	Answer whether the receiver is less than 0.
positive	Answer whether the receiver is greater than or equal to 0.
strictlyPositive	Answer whether the receiver is greater than 0.
sign	Answer 1 if the receiver is greater than 0, answer -1 if less than 0, else answer 0.
Number instance protocol

Properties of numbers that deal with truncation and round off are supplied by the following protocol.

truncation and round off
ceiling	Answer the integer nearest the receiver toward positive infinity.
floor	Answer the integer nearest the receiver toward negative infinity.
truncated	Answer the integer nearest the receiver toward zero
truncateTo: aNumber	Answer the next multiple of the argument, aNumber, that is nearest the receiver toward zero.
rounded	Answer the integer nearest the receiver.
roundTo: aNumber	Answer the multiple of the argument, aNumber, that is nearest the receiver.
Number instance protocol

Whenever a Number must be converted to an Integer, the message truncated can be used. So we have

expression	result
16.32 ceiling	17
16.32 floor	16
16.32 truncated	16
16.32 truncateTo:5	15
16.32 truncateTo:5.1	15.3
16.32 rounded	16
16.32 roundTo: 6	18
16.32 roundTo:6.3	18.9

The protocol provided in class Number includes various messages for converting a number into another kind of object or a different unit of representation. Numbers can represent various unit measurements such as degrees and radians. The following two messages perform conversions.

converting
degreesToRadians	The receiver is assumed to represent degrees. Answer the conversion to radians.
radiansToDegrees	The receiver is assumed to represent radians. Answer the conversion to degrees.
Number instance protocol

So that

30 degreesToRadians = 0.523599
90 degreesToRadians = 1.5708

Trigonometric and logarithmic functions are included in the protocol for mathematical functions. The receiver for the trigonometric functions cos, sin, and tan is an angle measured in radians; the result of the functions arcCos, arcSin and arcTan is the angle measured in radians.

In the following examples, 30 degrees is given as 0.523599 radians; 90 degrees is 1.5708 radians.

expression	result
0.523599 sin	0.5
0.523599 cos	0.866025
0.523599 tan	0.57735
1.5708 sin	1.0
0.57735 arcTan	0.523551
1.0 arcSin	1.5708

When a kind of Integer is asked to add itself to another kind of Integer, the result returned will naturally also be a kind of Integer. The same is true for the sum of two Floats; the class of the result will be the same as the class of the operands. If the two operands are SmallIntegers and the absolute value of their sum is too large to be represented as a SmallInteger, the result will be a LargePositiveInteger or a LargeNegativeInteger. The determination of the appropriate class of result when the operands are of different classes is somewhat more complicated. Two design criteria are that there be as little loss of information as possible and that commutative operations produce the same result regardless of which operand is the receiver of the message and which is the argument. So for example, 3.1 * 4 will return the same result as 4 * 3.1.

The appropriate representation for the result of operations on numbers of different classes is determined by a numerical measure of generality assigned to each class. Classes said to have more generality will have a larger number for this generality measure. Each class must be able to convert its instances into equal-valued instances of more general classes. The measure of generality is used to decide which of the operands should be converted. In this way, the arithmetic operations obey the law of commutativity with no loss of numerical information. When the differences between two classes of numbers are only a matter of precision (where "precision" is a measure of the information provided in a number), the more precise class is assigned a higher degree of generality. We have arbitrarily assigned approximate numbers a higher generality in cases where precision was not the issue (so, Float is more general than Fraction).

The generality hierarchy for the kinds of numbers in the Smalltalk-80 system, with most general listed first, is

Float

Fraction

LargePositiveInteger, LargeNegativeInteger

SmallInteger

The messages in the Number protocol designed to support the necessary coercions are categorized as "coercing" messages.

coercing
coerce: aNumber	Answer a number representing the argument, aNumber, that is the same kind of Number as the receiver. This method must be defined by all subclasses of Number.
generality	Answer the number representing the ordering of the receiver in the generality hierarchy.
retry: aSymbol coercing: aNumber	An arithmetic operation denoted by the symbol, aSymbol, could not be performed with the receiver and the argument, aNumber, as the operands because of the difference in representation. Coerce either the receiver or the argument, depending on which has the lower generality, and then try the arithmetic operation again. If the symbol is the equals sign, answer false if the argument is not a Number. If the generalities are the same, then retry:coercing: should not have been sent, so report an error to the user.
Number instance protocol

Thus if we try to evaluate 32.45 * 4, the multiplication of a Float by a SmallInteger will result in evaluating the expression

32.45 retry: #* coercing: 4

and the argument 4 will be coerced to 4.0 (Float has higher generality than SmallInteger). Then the multiplication will be carried out successfully.

Defining a hierarchy of the numbers in terms of a numerical measure of generality works for the kinds of numbers provided in the basic Smalltalk-80 system because the generality is transitive for these kinds of numbers. However, it does not provide a technique that can be used for all kinds of numbers.

Intervals (described in detail in Chapter 10) can be created by sending one of two messages to a number. For each element of such an interval, a block can be evaluated with the element as the block value.

intervals
to: stop	Answer an Interval from the receiver up to the argument, stop, with each next element computed by incrementing the previous one by 1.
to: stop by: stop	Answer an Interval from the receiver up to the argument, stop, with each next element computed by incrementing the previous one by step.
to: stop do: aBlock	Create an Interval from the receiver up to the argument, stop, incrementing by 1. Evaluate the argument, aBlock, for each element of the Interval.
to: stop by: step do: aBlock	Create an Interval from the receiver up to the argument, stop, incrementing by step. Evaluate the argument, aBlock, for each element of the Interval.
Number instance protocol

Thus if we evaluate

a ← 0.
10 to: 100 by: 10 do: [ :each | a ← a + each]

the final value of a will be 550.

If a is the array #('one" 'two" 'three' "four' "five'), then each element of the array can be accessed by indices that are in the interval from 1 to the size of the array. The following expression changes each element so that only the initial characters are kept.

1 to: a size do: [:index | a at: index put: ((a at: index) at: 1)]

The resulting array is #('o' 't' 't' "f' "f'). Note that, like an array, elements of a string can be accessed using the messages at: and at:put:. Messages to objects like strings and arrays are detailed in Chapters 9 and 10.

Classes Float and Fraction

The classes Float and Fraction provide two representations of non-integral values. Floats are representations of real numbers that may be approximate; they represent about 6 digits of accuracy with a range between plus or minus 10 raised to the power plus or minus 32. Some examples are

8.0
13.3
0.3
2.5e6
1.27e - 30
-12.987654e12

Fractions are representations of rational numbers that will always be exact. All arithmetic operations on a Fraction answer a reduced fractional result.

Instances of Float can be created by literal notation in methods (for example, 3.14159) or as the result of an arithmetic operation, one argument of which is another Float.

Instances of Fraction can be created as a result of an arithmetic operation if one of the operands is a Fraction and the other is not a Float. (If it were a Float, the result would be a Float since the generality number of Float is higher than that of Fraction). Instances of Fraction can also be created when the mathematical division operation (/) is performed on two Integers and the result is not integral. In addition, class protocol for Fraction supports sending a message of the form numerator: numInteger denominator: denInteger in order to create an instance.

Float responds to the message pi to return the corresponding constant. It adds truncation and round off protocol to return the fraction and integer parts of the receiver (fractionPart and integerPart), and it adds converting protocol to convert the receiver to a Fraction (asFraction). Similarly class Fraction adds converting protocol to convert the receiver to a Float (asFloat).

Integer Classes

Class Integer adds protocol particular to integral numbers. It has three subclasses. One is class SmallInteger, which provides a space-economical representation for a substantial range of integral values that occur frequently in counting and indexing. The representation limits the range to a little less than the magnitudes representable by a single machine word. Large integers, which are represented by instances of LargePositiveInteger or kargeNegativeInteger depending on the sign of the integer, do not have a limit to their magnitude. The cost in providing the generality of large integers is longer computation time. Thus if the result of an arithmetic operation on a large integer is representable as a small integer, it will in fact be a small integer.

In addition to the messages inherited from the class Number, class Integer adds converting protocol (asCharacter, asFloat and asFraction), further printing (printOn: aStream base: b, radix: baseInteger), and enumeratingprotocol. Thus 8 radix: 2 is 2r1000.

For enumerating, it is possible to evaluate a block repetitively an integral number of times using the message timesRepeat: aBlock. Take as an example

a ← 1.
10 timesRepeat: [a ← a + a]

where the block has no arguments. The resulting value of a is 2^10, or 1024.

Class Integer provides factorization and divisibility protocol not specified for numbers in general.

factorization and divisibility
factorial	Answer the factorial of the receiver. The receiver must not be less than 0.
gcd: anInteger	Answer the greatest common divisor of the receiver and the argument, anInteger.
lcm: anInteger	Answer the least common multiple of the receiver and the argument, anInteger.
Integer instance protocol

Examples are

expression	result
3 factorial	6
55 gcd: 30	5
6 lcm: 10	30

In addition to the numerical properties of integers, some algorithms make use of the fact that integers can be interpreted as a sequence of bits. Thus protocol for bit manipulation is specified in Integer.

bit manipulation
allMask: anInteger	Treat the argument anInteger as a bit mask. Answer whether all of the bits that are 1 in anInteger are 1 in the receiver.
anyMask: anInteger	Treat the argument anInteger as a bit mask. Answer whether any of the bits that are 1 in anInteger are 1 in the receiver.
noMask: anInteger	Treat the argument anInteger as a bit mask. Answer whether none of the bits that are 1 in anInteger are 1 in the receiver.
bitAnd: anInteger	Answer an Integer whose bits are the logical and of the receiver's bits and those of the argument anInteger.
bitOr: anInteger	Answer an Integer whose bits are the logical or of the receiver's bits and those of the argument anInteger.
bitXor: anInteger	Answer an Integer whose bits are the logical xor of the receiver's bits and those of the argument anInteger.
bitAt: index	Answer the bit (0 or 1) at position index of the receiver.
bitInvert	Answer an Integer whose bits are the complement of the receiver.
highBit	Answer the index of the high order bit of the binary representation of the receiver.
bitShift: anInteger	Answer an Integer whose value (in two's-complement representation) is the receiver's value (in two's-complement representation) shifted left by the number of bits indicated by the argument, anInteger. Negative arguments shift right. Zeros are shifted in from the right in left shifts. The sign bit is extended in right shifts.
Integer instance protocol

Some examples follow. Note that the default radix for printing an Integer is 10.

expression	result
2r111000111000111	29127
2r101010101010101	21845
2r101000101000101	20805
2r000111000111000	3640
29127 allMask: 20805	true
29127 allMask: 21845	false
29127 anyMask: 21845	true
29127 noMask: 3640	true
29127 bitAnd: 3640	0
29127 bitOr: 3640	32767
32767 radix: 2	2r111111111111111
29127 bitOr: 21845	30167
30167 radix: 2	2r111010111010111
3640 bitShift: 1	7280

Class Random: A Random Number Generator

Many applications require random choices of numbers. Random numbers are useful, for example, in statistical applications and data encryption algorithms. Class Random is a random number generator that is included in the standard Smalltalk-80 system. It provides a simple way of obtaining a sequence of random numbers that will be uniformly distributed over the interval between, but not including, 0.0 and 1.0.

An instance of class Random maintains a seed from which the next random number is generated. The seed is initialized in a pseudo-random way. An instance of Random is sent the message next whenever a new random number is desired.

A random number generator can be created with the expression

rand ← Random new

The expression

rand next

can then be evaluated whenever a new random number is needed. The response is a number (Float) between 0.0 and 1.0.

The implementation of next is based on Lehmer's linear congruential method as presented in Knuth, Volume 1 [D. E. Knuth, The Art of Computer Programming: Fundamental Algorithms, Volume 1, Reading, Mass: Addison Wesley, 1968].

next
| temp |
    "Lehmer's linear congruential method with modulus m = 2 raisedTo: 16, a = 27181 odd, and 5 = a \\ 8, c = 13849 odd, and c / m approximately 0.21132"
    [seed ← 13849 + (27181 * seed) bitAnd: 8r177777.
    temp ← seed / 65536.0.
    temp = 0] whileTrue.
    ↑temp

It is also possible to send an instance of class Random the messages next: anInteger, to obtain an OrderedCollection of anInteger number of random numbers, and nextMatchFor: aNumber, to determine whether the next random number is equal to aNumber.

Suppose we want to select one of 10 integers, 1, ..., 10, using the random number generator rand. The expression to be evaluated is

(rand next * 10) truncated + 1

That is,

expression	result
rand next	a random number between 0 and 1
rand next * 10	a random number between 0 and 10
(rand next * 10) truncated	an integer > = 0 and < = 9
(rand next * 10) truncated + 1	an integer > = 1 and < = 10