Smalltalk80LanguageImplementation:Chapter 08
- Chapter 8 Numerical Classes
Contents
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 |