'From Squeak 2.2 of Sept 23, 1998 on 7 October 1998 at 6:27:38 am'!
Object subclass: #BooleanConnective
	instanceVariableNames: 'left right '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Tarski'!
BooleanConnective subclass: #ConjunctionConnective
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Tarski'!
Object subclass: #ConnectivityGraph
	instanceVariableNames: 'nodes matrix '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Tarski'!
Object subclass: #CylindricalAlgebraicDecomposition
	instanceVariableNames: 'polynomials dimension components '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Tarski'!
BooleanConnective subclass: #DisjunctionConnective
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Tarski'!
BooleanConnective subclass: #ImplicationConnective
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Tarski'!
Magnitude subclass: #Infinity
	instanceVariableNames: 'sign '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Kernel'!
Object subclass: #Matrix
	instanceVariableNames: 'rows '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Kernel'!
Object subclass: #Monomial
	instanceVariableNames: 'literal coefficient '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Polynomials'!
Object subclass: #MonomialLiteral
	instanceVariableNames: 'contents '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Polynomials'!
Object subclass: #MonomialOrdering
	instanceVariableNames: 'indeterminates weighs '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Polynomials'!
Object subclass: #MultiPolynomialDivisor
	instanceVariableNames: 'dividend divisors ordering quotients remainder done '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Polynomials'!
Number subclass: #AlgebraicNumber
	instanceVariableNames: 'polynomial irreducible leftBound rightBound rightValue '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Polynomials'!
Object subclass: #Polynomial
	instanceVariableNames: 'monomials '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Polynomials'!
Object subclass: #PolynomialDivisor
	instanceVariableNames: 'dividend divisor quotient remainder done '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Polynomials'!
Object subclass: #PolynomialEquation
	instanceVariableNames: 'polynomial '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Tarski'!
Object subclass: #PolynomialFactorizer
	instanceVariableNames: 'polynomial factors irreducible done '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Polynomials'!
Object subclass: #PolynomialInequality
	instanceVariableNames: 'polynomial '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Tarski'!
Object subclass: #PolynomialInterpolator
	instanceVariableNames: 'polynomial corrector '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Polynomials'!
Object subclass: #PolynomialPseudoDivisor
	instanceVariableNames: 'dividend divisor indeterminate quotient remainder done '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Polynomials'!
Object subclass: #PolynomialRootFinder
	instanceVariableNames: 'polynomial roots done '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Polynomials'!
PolynomialRootFinder subclass: #AlgebraicPolynomialRootFinder
	instanceVariableNames: 'sturm fourier '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Polynomials'!
Object subclass: #PolynomialRootFunction
	instanceVariableNames: 'polynomials index '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Tarski'!
Object subclass: #PolynomialSet
	instanceVariableNames: 'contents '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Tarski'!
Object subclass: #QuantifiedSentence
	instanceVariableNames: 'prefix matrix '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Tarski'!
Object subclass: #Quantifier
	instanceVariableNames: 'indeterminate '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Tarski'!
Quantifier subclass: #ExistentialQuantifier
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Tarski'!
Object subclass: #RationalFunction
	instanceVariableNames: 'numerator denominator '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Kernel'!
PolynomialRootFinder subclass: #RationalPolynomialRootFinder
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Polynomials'!
Object subclass: #RealInterval
	instanceVariableNames: 'contents '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Kernel'!
Object subclass: #RealLineInterval
	instanceVariableNames: 'left right rightOpen leftOpen '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Kernel'!
Object subclass: #SemialgebraicCell
	instanceVariableNames: 'projection left right '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Tarski'!
RealLineInterval subclass: #SemialgebraicLineCell
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Tarski'!
Object subclass: #SemialgebraicSet
	instanceVariableNames: 'cells '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Tarski'!
Object subclass: #Tuple
	instanceVariableNames: 'contents '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Kernel'!
Quantifier subclass: #UniversalQuantifier
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Mathematics-Tarski'!

!Object methodsFor: 'testing' stamp: 'len 1/20/98 01:46'!
isAlgebraic
	"Answer true if the receiver is an AlgebraicNumber."
	^ false! !

!Object methodsFor: 'testing' stamp: 'len 2/25/98 22:13'!
isComplex
	"Answer true if the receiver is a Complex."
	^ false! !

!Object methodsFor: 'testing' stamp: 'len 1/13/98 21:18'!
isFraction
	"Answer true if the receiver is a Fraction."

	^ false! !

!Object methodsFor: 'testing' stamp: 'len 12/13/97 02:25'!
isInfinity
	"Answer true if the receiver is infinity."

	^ false! !

!Object methodsFor: 'testing' stamp: 'len 1/24/98 14:01'!
isMatrix
	"Answer true if the receiver is a matrix."

	^ false! !

!Object methodsFor: 'testing' stamp: 'len 1/24/98 13:43'!
isMonomial
	"Answer true if the receiver is a monomial."

	^ false! !

!Object methodsFor: 'testing' stamp: 'len 11/24/97 20:46'!
isMonomialLiteral
	"Answer true if the receiver is a monomial literal."

	^ false! !

!Object methodsFor: 'testing' stamp: 'len 1/20/98 01:46'!
isPolynomial
	"Answer true if the receiver is a polynomial."
	^ false! !

!Object methodsFor: 'testing' stamp: 'len 2/25/98 03:17'!
isQuaternion
	"Answer true if the receiver is a Quaternion."

	^ false! !

!Object methodsFor: 'testing' stamp: 'len 1/20/98 01:46'!
isRationalFunction
	"Answer true if the receiver is a rational function."
	^ false! !

!Object methodsFor: 'testing' stamp: 'len 12/13/97 03:00'!
isRealInterval
	"Answer true if the receiver is a real interval."

	^ false! !

!Object methodsFor: 'testing' stamp: 'len 11/28/97 02:08'!
isTuple
	"Answer true if the receiver is a Tuple."
	^ false! !


!AlgebraicNumber class methodsFor: 'instance creation' stamp: 'len 8/5/97 00:13'!
fromRational: anIntegerOrFraction
	"Answer an instance of the receiver representing
	the rational number anIntegerOrFraction."

	| q |
	q _ anIntegerOrFraction asFraction.
	^ self
		polynomial: self polynomialClass x * q denominator - q numerator
		irreducible: true
 		leftBound: anIntegerOrFraction
		rightBound: anIntegerOrFraction! !

!AlgebraicNumber class methodsFor: 'instance creation' stamp: 'len 8/8/97 20:33'!
polynomial: aPolynomial irreducible: aBoolean leftBound: left rightBound: right
	"Answer an instance of the receiver representing the
	unique zero of aPolynomial in the interval (left,right],
	and set the irreducibility flag for aPolynomial to aBoolean."

	^ self new
		polynomial: aPolynomial
		irreducible: aBoolean
		leftBound: left
		rightBound: right! !

!AlgebraicNumber class methodsFor: 'instance creation' stamp: 'len 8/4/97 20:52'!
polynomial: aPolynomial leftBound: left rightBound: right
	"Answer an instance of the receiver representing the
	unique zero of aPolynomial in the interval (left,right],
	and set the irreducibility flag for aPolynomial to aBoolean."

	^ self
		polynomial: aPolynomial irreducible: false
		leftBound: left rightBound: right! !

!AlgebraicNumber class methodsFor: 'related classes' stamp: 'len 11/22/97 23:41'!
polynomialClass
	^ Polynomial! !

!AlgebraicNumber class methodsFor: 'related classes' stamp: 'len 9/14/97 00:16'!
rootFinderClass
	^ AlgebraicPolynomialRootFinder! !

!AlgebraicNumber class methodsFor: 'examples' stamp: 'len 8/4/97 20:49'!
null
	"Answer a null instance of the receiver."

	^ self
		polynomial: self polynomialClass x irreducible: true
		leftBound: 0 rightBound: 0! !

!AlgebraicNumber class methodsFor: 'examples' stamp: 'len 11/17/97 20:58'!
phi
	"Answer the Phidias number or Golden Ratio."

	| x |
	x _ self polynomialClass x.
	^ self polynomial: (x**2 - x - 1) irreducible: true leftBound: 1 rightBound: 2! !

!AlgebraicNumber class methodsFor: 'examples' stamp: 'len 8/28/97 02:44'!
sqrt2
	"Answer an instance of the receiver representing the square root of 2."

	^ self
		polynomial: self polynomialClass x squared - 2
		irreducible: true
 		leftBound: 1 rightBound: 2! !

!AlgebraicNumber class methodsFor: 'examples' stamp: 'len 8/28/97 02:45'!
sqrt: anIntegerOrFraction
	"Answer an instance of the receiver representing
	the square root of the rational argument."

	^ self
		polynomial: self polynomialClass x squared - anIntegerOrFraction
		irreducible: true
 		leftBound: 0 rightBound: (anIntegerOrFraction max: 1)! !


!BooleanConnective commentStamp: '<historical>' prior: 0!
I am an abstract superclass for boolean connectives that are employed in the building of Tarski sentences. My concrete subclases are ConjunctionConnective (AND), DisjunctionConnective (OR) and ImplicationConective.
!

!BooleanConnective methodsFor: 'accessing-private' stamp: 'len 12/18/97 19:42'!
left: anObject
	left _ anObject! !

!BooleanConnective methodsFor: 'accessing-private' stamp: 'len 12/18/97 19:42'!
right: anObject
	right _ anObject! !

!BooleanConnective methodsFor: 'accessing' stamp: 'len 12/31/97 02:44'!
bounded
	"Answer the collection of bounded indeterminates."

	^ self left bounded addAll: self right bounded; yourself! !

!BooleanConnective methodsFor: 'accessing' stamp: 'len 12/31/97 02:44'!
free
	"Answer the collection of free indeterminates."

	| answer |
	answer _ self indeterminates.
	self bounded do: [ :each | answer remove: each ifAbsent: []].
	^ answer! !

!BooleanConnective methodsFor: 'accessing' stamp: 'len 12/18/97 20:41'!
indeterminates
	"Answer the indeterminates of the receiver."

	^ self left indeterminates addAll: self right indeterminates; yourself! !

!BooleanConnective methodsFor: 'accessing' stamp: 'len 12/18/97 19:42'!
left
	"Answer the left component of the receiver."

	^ left! !

!BooleanConnective methodsFor: 'accessing' stamp: 'len 12/19/97 21:47'!
polynomials
	"Answer the polynomial set of the receiver."

	^ self left polynomials addAll: self right polynomials; yourself! !

!BooleanConnective methodsFor: 'accessing' stamp: 'len 12/18/97 19:42'!
right
	"Answer the right component of the receiver."

	^ right! !

!BooleanConnective methodsFor: 'arithmetic' stamp: 'len 12/18/97 19:44'!
& anObject
	"Answer the conjunction of the receiver with the argument."

	^ ConjunctionConnective left: self right: anObject! !

!BooleanConnective methodsFor: 'arithmetic' stamp: 'len 12/18/97 19:48'!
-> anObject
	"Answer the implication of the argument from the receiver."

	^ ImplicationConnective left: self right: anObject! !

!BooleanConnective methodsFor: 'arithmetic' stamp: 'len 12/21/97 21:24'!
exists: anInteger
	"Answer the quantification of the reciever by the
	existential quantifier in the anInteger-th indeterminate."

	^ QuantifiedSentence quantifier: (Quantifier exists: anInteger) matrix: self! !

!BooleanConnective methodsFor: 'arithmetic' stamp: 'len 12/21/97 21:25'!
forAll: anInteger
	"Answer the quantification of the reciever by the
	universal quantifier in the anInteger-th indeterminate."

	^ QuantifiedSentence quantifier: (Quantifier forAll: anInteger) matrix: self! !

!BooleanConnective methodsFor: 'arithmetic' stamp: 'len 12/18/97 19:49'!
not
	"Answer the negation of the receiver."

	self subclassResponsibility! !

!BooleanConnective methodsFor: 'arithmetic' stamp: 'len 12/18/97 19:45'!
| anObject
	"Answer the disjunction of the receiver with the argument."

	^ DisjunctionConnective left: self right: anObject! !

!BooleanConnective methodsFor: 'operations' stamp: 'len 12/26/97 18:46'!
normalized
	"Answer a copy of the receiver with the indeterminates renamed
	such that the same indeterminate does not ocur as free and bound."

	| last bounded answer |
	last _ self indeterminates asSortedCollection last.
	bounded _ self right bounded.
	answer _ self copy.
	(self left free select: [ :some | bounded includes: some])
			do: [answer rename: some to: (last _ last + 1)].
	^ answer! !

!BooleanConnective methodsFor: 'operations' stamp: 'len 12/31/97 02:19'!
prenex
	"Answer the prenex form of the receiver."

	^ self reduced normalized privatePrenex! !

!BooleanConnective methodsFor: 'operations' stamp: 'len 12/26/97 18:38'!
reduced
	"Answer a copy of the receiver with the redundant quantifiers removed."

	^ self class left: self left reduced right: self right reduced! !

!BooleanConnective methodsFor: 'operations' stamp: 'len 12/26/97 18:48'!
rename: anInteger to: anotherInteger
	"Rename the anInteger-th indeterminate of the receiver to anotherInteger."

	self left rename: anInteger to: anotherInteger.
	self right rename: anInteger to: anotherInteger! !

!BooleanConnective methodsFor: 'testing' stamp: 'len 12/18/97 20:27'!
isQuantifierFree
	"Answer true if the receiver is quantifier-free."

	^ self left isQuantifierFree and: [self right isQuantifierFree]! !

!BooleanConnective methodsFor: 'testing' stamp: 'len 12/18/97 19:43'!
isSolution: anObject
	"Answer true if the argument is solution of the receiver."

	self subclassResponsibility! !

!BooleanConnective methodsFor: 'private' stamp: 'len 12/31/97 02:26'!
privatePrenex
	"Answer the prenex form of the receiver.
	Assume the receiver is reduced and normalized."

	| lp rp prefix matrix |
	lp _ self left privatePrenex.
	rp _ self right privatePrenex.
	prefix _ lp prefix copy addAll: rp prefix; yourself.
	matrix _ self class left: lp matrix right: rp matrix.
	^ QuantifiedSentence prefix: prefix matrix: matrix! !


!BooleanConnective class methodsFor: 'instance creation' stamp: 'len 12/18/97 19:46'!
left: anObject right: anotherObject
	"Answer a new instance of the receiver with left
	and right components given by the arguments."

	^ self new left: anObject; right: anotherObject! !


!Collection methodsFor: 'accessing'!
anElement
	self do: [ :any | ^any].
	^nil! !


!Bag methodsFor: 'adding' stamp: 'len 6/1/1998 03:21'!
addAll: aCollection
	"Refer to the comment in Collection|addAll:."

	(aCollection isKindOf: Bag) ifFalse: [^ super addAll: aCollection].
	aCollection contents associationsDo: [ :each |
		self add: each key withOccurrences: each value].
	^ aCollection! !

!Bag methodsFor: 'enumerating' stamp: 'len 6/1/1998 03:23'!
detect: aBlock ifNone: exceptionBlock 
	"Refer to the comment in Collection|detect:ifNone:."

	self contents keysDo: [:each | (aBlock value: each) ifTrue: [^ each]].
	^ exceptionBlock value! !

!Bag methodsFor: 'enumerating' stamp: 'len 6/1/1998 03:25'!
select: aBlock 
	"Refer to the comment in Collection|select:."

	| newCollection |
	newCollection _ self species new.
	self contents associationsDo: [:each |
		(aBlock value: each key)
			ifTrue: [newCollection add: each key withOccurrences: each value]].
	^ newCollection! !

!Bag methodsFor: 'private'!
contents
	^contents
! !

!Bag methodsFor: 'comparing' stamp: 'len 6/1/1998 03:27'!
= aBag
	| otherContents |
	(aBag isKindOf: Bag) ifFalse: [^ false].
	contents size = (otherContents _ aBag contents) size ifFalse: [^ false].
	contents associationsDo: [ :assoc |
		(otherContents at: assoc key ifAbsent: [^ false]) = assoc value ifFalse: [^ false]].
	^ true! !

!Bag methodsFor: 'comparing' stamp: 'len 6/1/1998 03:27'!
hash
	^ self contents hash! !


!ConjunctionConnective commentStamp: '<historical>' prior: 0!
My instances are conjunctions of two Tarski sentences.

For an example try this:
	| x y |
	x _ Polynomial x.
	y _ Polynomial y.
	ConjunctionConnective left: (x squared + y squared gneq: 1) right: (x eq: 1).
!

!ConjunctionConnective methodsFor: 'arithmetic' stamp: 'len 12/18/97 19:49'!
not
	"Answer the negation of the receiver."

	^ self left not | self right not! !

!ConjunctionConnective methodsFor: 'testing' stamp: 'len 12/18/97 19:43'!
isSolution: anObject
	"Answer true if the argument is solution of the receiver."

	^ (self left isSolution: anObject) and: [self right isSolution: anObject]! !

!ConjunctionConnective methodsFor: 'printing' stamp: 'len 12/18/97 20:14'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	aStream
		nextPut: $(; print: self left; nextPut: $);
		nextPutAll: ' /\ ';
		nextPut: $(; print: self right; nextPut: $)! !


!ConnectivityGraph commentStamp: '<historical>' prior: 0!
My instances are graphs represented by an ordered set of vertices and the adjacency matrix defining the edges and arcs. This representation is specially useful when trying to decide whether there exist a path joining two of the graph's vertices.
!

!ConnectivityGraph methodsFor: 'initialization' stamp: 'len 1/9/98 21:22'!
initialize
	self nodes: OrderedCollection new! !

!ConnectivityGraph methodsFor: 'accessing-private' stamp: 'len 1/9/98 21:22'!
nodes: aCollection
	nodes _ aCollection! !

!ConnectivityGraph methodsFor: 'accessing' stamp: 'len 1/9/98 21:24'!
add: anObject
	"Add the argument to the nodes of the receiver. Answer the argument."

	^ self nodes add: anObject! !

!ConnectivityGraph methodsFor: 'accessing' stamp: 'len 1/9/98 21:40'!
addAll: aCollection
	"Add the elements in the argument to the nodes
	of the receiver. Answer the argument."

	aCollection do: [ :each | self add: each].
	^ aCollection! !

!ConnectivityGraph methodsFor: 'accessing' stamp: 'len 1/9/98 21:44'!
addArrowFrom: anObject to: anotherObject
	"Add an arrow from anObject to anotherObject."

	self matrix
		atRow: (self nodes indexOf: anObject)
		column: (self nodes indexOf: anotherObject)
		put: 1! !

!ConnectivityGraph methodsFor: 'accessing' stamp: 'len 1/9/98 21:44'!
addEdgeFrom: anObject to: anotherObject
	"Add an edge from anObject to anotherObject."

	self addArrowFrom: anObject to: anotherObject;
		addArrowFrom: anotherObject to: anObject! !

!ConnectivityGraph methodsFor: 'accessing' stamp: 'len 1/9/98 21:46'!
matrix
	"Answer the adjacency matrix of the receiver."

	matrix isNil ifTrue: [matrix _ Matrix null: self nodes size @ self nodes size].
	^ matrix! !

!ConnectivityGraph methodsFor: 'accessing' stamp: 'len 1/9/98 21:22'!
nodes
	"Answer the nodes of the receiver."

	^ nodes! !

!ConnectivityGraph methodsFor: 'testing' stamp: 'len 1/12/98 23:25'!
connects: anObject with: anotherObject
	"Answer true if the receiver connects anObject with anotherObject."

	0 to: self nodes size do: [ :each |
		(self connects: anObject with: anotherObject byAPathOfLength: each)
			ifTrue: [^ true]].
	^ false! !

!ConnectivityGraph methodsFor: 'testing' stamp: 'len 1/9/98 21:49'!
connects: anObject with: anotherObject byAPathOfLength: anInteger
	"Answer true if the receiver connects anObject
	with anotherObject by a path of length anInteger."

	^ ((self matrix raisedToInteger: anInteger)
		atRow: (self nodes indexOf: anObject)
		column: (self nodes indexOf: anotherObject)) = 1! !


!ConnectivityGraph class methodsFor: 'instance creation' stamp: 'len 1/24/98 15:00'!
new
	^ super new initialize! !


!CylindricalAlgebraicDecomposition commentStamp: '<historical>' prior: 0!
My instances decompose R^n into connected components (SemialgebraicCells) such that a given set of polynomials keeps sign-invariant over each of the components. This decomposition is called Cylindrical Algebraic Decomposition (CAD), and what is obtainded is called a Cell Complex of R^n. Each of the components is a SemialgebraicCell (or SemialgebraicLineCell in R^1).

The univariate case is easy. Suppose we have to find the CAD of R with respect to the polynomial set {f1, ..., fn}. Then we find all the real roots of f1, ..., fn, a1 < a2 < ... < am, and the CAD we were looking for is:
	[-infinity, a1), [a1, a1], (a1, a2), [a2, a2], (a2, a3), ... [am, am], (am, +infinity].
All this can be effectively computed when using Sturm theory when the polynomials have rational coefficients. See the comments in AlgebraicNumber and AlgebraicPolynomialRootFinder. Each component can be asked for a sample point in it, and the sample points can be constructed in this way:
	the sample point of [-infinity, a1) is a1 - 1;
	the sample point of (am, +infinity] is am + 1;
	the sampel point of [ai, ai] is ai;
	and the sample point of (ai, a{i+1}) is ai + a{i+1} / 2 (the middle).

An example: decide wether the sentence x^2 + 1 > 0 is true or false. First we find the CAD of R with respect to {x^2 + 1}. The roots of x^2 + 1 are -1 and 1, so the CAD is
	[-infinity, -1), [-1, -1], (-1, 1), [1, 1] and (1, +infinity]
and the respective sample points are
	-2, -1, 0, 1 and 2.
We know that the polynomial x^2 + 1 is sign invariant over each of the components of the CAD, so if it's positive in all the components, it's positive over all R. So we evaluate x^2 + 1 at each of the sample points and check that it's positive, and then we can conclude that the sentence is true.

The construction of the CAD in the multivariate case is performed inductively. Suppose we want the CAD of R^k with respect to the set of real polynomials F = {f1, ..., fn} in k indeterminates. Then we produce another set of polynomials Phi(F) = {g1, ..., gm} in k-1 indeterminates that have some nice properties that makes this construction valid (for more information on this see Algorithmic Algebra, B. Mishra, Springer-Verlag, 1993). Now we inductively compute K', the CAD of R^{k-1} with respect to Phi(F), and name the components C1, ... Ct. Each component can be asked for a sample point in it. Let f = f1 f2 ... fn (the product of the polynomials in F). Furthermore, we define the functions zj:R^{k-1} -> R to be at the point (a1, ..., a{k-1}) the j-th root of f(a1, ..., a{k-1}, x) as univariate polynomial in x. Phi(F) is defined in such a way to make the number of roots of f be invariant over each C in K', and to make each zj to be a continuous function over each C in K'. Finally we can construct K, the CAD of R^k. Each cell in K will be of two kinds:
	1. For each cell C in K', C x [-infinity, +infinity].
	2. For each cell C in K', suppose the number of roots of f are r. Then we have the following cells:
		C0* = {(p, x) | x < z1(p), p in C}
		C1 = {(p, x) | x = z1(p), p in C}
		C1* = {(p, x) | z1(p < x < z2(p), p in C}
		C2 = {(p, x) | x = z2(p), p in C}
			...
		Cm = {(p, x) | x = zm(p), p in C}
		Cm* = {(p, x) | zm(p) < x, p in C}.
Sample points for each of the cells constructed can be easyly computed.

Finally, we cite the Collin's Theorem. Given a finite set of multivariate polynomials F in Q[x1,...,xn] we can effectively construct the followings:
	o. An F-sign-invariat cylindrical algebraic decomposition K of R^n into semialgebraic connected cells. Each cell C in K is homeomorphic to R^d for some 0 <= d <= n.
	o. A sample algebraic point in each cell in K and defining polynomials for each sample point.
	o. Quantifier-free defining sentences for each cell C in K.

!

!CylindricalAlgebraicDecomposition methodsFor: 'accessing-private' stamp: 'len 12/12/97 20:12'!
components: aCollection
	components _ aCollection! !

!CylindricalAlgebraicDecomposition methodsFor: 'accessing-private' stamp: 'len 12/12/97 20:07'!
dimension: anInteger
	dimension _ anInteger! !

!CylindricalAlgebraicDecomposition methodsFor: 'accessing-private' stamp: 'len 12/12/97 20:07'!
polynomials: aPolynomialSet
	polynomials _ aPolynomialSet! !

!CylindricalAlgebraicDecomposition methodsFor: 'accessing' stamp: 'len 12/12/97 20:12'!
components
	"Answer the components of the receiver."

	self decompose.
	^ components! !

!CylindricalAlgebraicDecomposition methodsFor: 'accessing' stamp: 'len 12/12/97 23:33'!
dimension
	"Answer the dimension of the ambient of the receiver."

	^ dimension! !

!CylindricalAlgebraicDecomposition methodsFor: 'accessing' stamp: 'len 12/12/97 20:13'!
done
	"Answer true if the receiver has performed the decomposition."

	^ components notNil! !

!CylindricalAlgebraicDecomposition methodsFor: 'accessing' stamp: 'len 12/12/97 23:32'!
polynomials
	"Answer the polynomial set defining the receiver."

	^ polynomials! !

!CylindricalAlgebraicDecomposition methodsFor: 'enumerating' stamp: 'len 12/12/97 20:11'!
do: aBlock
	"Enumerate the components of the receiver."

	self components do: aBlock! !

!CylindricalAlgebraicDecomposition methodsFor: 'operations' stamp: 'len 2/13/98 19:20'!
decompose
	"Perform the cylindrical algebraic decomposition."

	| cells roots point functions f |
	self done ifTrue: [^ self].
	self dimension < 1 ifTrue: [^ self components: Array new].
	self dimension = 1 ifTrue: [^ self decomposeUnivariate].
	cells _ OrderedCollection new.
	(self class polynomials: self phi dimension: self dimension - 1) do: [ :each |
		point _ (each sample, Polynomial x).
		roots _ Set new.
		self polynomials do: [ :some |
			f _ (some valueAt: point) mapCoefficients: [ :coeff |
					coeff isAlgebraic ifTrue: [coeff asRational] ifFalse: [coeff]].
			roots addAll: (AlgebraicPolynomialRootFinder polynomial: f) roots].
		roots isEmpty
			ifTrue: [cells add:
						(SemialgebraicCell
							projection: each
							between: Infinity negative and: Infinity positive)]
			ifFalse: [functions _ (1 to: roots size)
						collect: [ :some | PolynomialRootFunction
											polynomials: self polynomials index: some].
					cells add: (SemialgebraicCell
								projection: each
								between: Infinity negative
								and: functions first).
					1 to: functions size - 1 do: [ :index |
						cells
							add: (SemialgebraicCell
									projection: each
									between: (functions at: index)
									and: (functions at: index));
							add: (SemialgebraicCell
									projection: each
									between: (functions at: index)
									and: (functions at: index + 1))].
					cells add: (SemialgebraicCell
								projection: each
								between: functions last
								and: functions last).
					cells add: (SemialgebraicCell
								projection: each
								between: functions last
								and: Infinity positive)]].
	self components: cells! !

!CylindricalAlgebraicDecomposition methodsFor: 'private' stamp: 'len 2/13/98 19:44'!
decomposeUnivariate
	"Perform the cylindrical algebraic decomposition in the univariate case.
	It's easy. Suppose we have to find the CAD of R with respect to the polynomial
	set {f1, ..., fn}. Then we find all the real roots of f1, ..., fn, a1 < a2 < ... < am,
	and the CAD we were looking for is:
		[-infinity, a1), [a1, a1], (a1, a2), [a2, a2], ... [am, am], (am, +infinity]."

	| roots intervals |
	roots _ Set new.
	self polynomials do: [ :each |
		roots addAll: (AlgebraicPolynomialRootFinder polynomial: each) roots].
	roots isEmpty
		ifTrue: [^ self components:
					(Array with: (SemialgebraicLineCell
									between: Infinity negative
									and: Infinity positive))].
	roots _ roots asSortedCollection.
	intervals _ OrderedCollection new.
	intervals add: (SemialgebraicLineCell between: Infinity negative and: roots first).
	1 to: roots size - 1 do: [ :each |
		intervals
			add: (SemialgebraicLineCell between: (roots at: each) and: (roots at: each));
			add: (SemialgebraicLineCell between: (roots at: each) and: (roots at: each + 1))].
	intervals
		add: (SemialgebraicLineCell between: roots last and: roots last);
		add: (SemialgebraicLineCell between: roots last and: Infinity positive).
	self components: intervals! !

!CylindricalAlgebraicDecomposition methodsFor: 'private' stamp: 'len 2/13/98 19:38'!
phi
	"Answer a set of polynomials in n-1 indeterminates
	which completly characterizes the connected maximal
	F-delineable subsets of R^{n-1}. (where F is the polynomial
	set of the receiver and n is the number of indeterminates).
	See >>decompose."

	| answer deg f g |
	answer _ PolynomialSet new.
	self polynomials do: [ :each |
		deg _ each degreeIn: self dimension.
		0 to: deg do: [ :i |
			answer add: (each coefficientAt: i in: self dimension) asPolynomial].
		0 to: deg - 1 do: [ :i |
			answer add:
				(each psc: i with: (each derivativeIn: self dimension)
						in: self dimension) asPolynomial]].
	1 to: self polynomials size - 1 do: [ :i |
		i + 1 to: self polynomials size do: [ :j |
			f _ self polynomials at: i.
			g _ self polynomials at: j.
			0 to: ((f degreeIn: self dimension) min: (g degreeIn: self dimension)) do: [ :m |
				answer add: (f psc: m with: g in: self dimension) asPolynomial]]].
	^ answer collect: [ :each | each / each head coefficient]! !

!CylindricalAlgebraicDecomposition methodsFor: 'printing' stamp: 'len 12/13/97 04:43'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	aStream
		nextPutAll: self class name;
		nextPutAll: ' on R^'; print: self dimension;
		nextPutAll: ' by '; print: self polynomials! !


!CylindricalAlgebraicDecomposition class methodsFor: 'instance creation' stamp: 'len 2/7/98 19:11'!
polynomials: aPolynomialSet dimension: anInteger
	"Answer a new instance of the receiver representing the
	cylindrical algebraic decomposition of R^n (n = anInteger)
	in cells sign invariant by aPolynomialSet."

	^ self new polynomials: aPolynomialSet; dimension: anInteger! !


!DisjunctionConnective commentStamp: '<historical>' prior: 0!
My instances are disjunctions of two Tarski sentences.

For an example try this:
	| x y |
	x _ Polynomial x.
	y _ Polynomial y.
	DisjunctionConnective
		left: (x squared + y squared lneq: 1) right: (x squared + y squared eq: 1).
!

!DisjunctionConnective methodsFor: 'arithmetic' stamp: 'len 12/18/97 19:50'!
not
	"Answer the negation of the receiver."

	^ self left not & self right not! !

!DisjunctionConnective methodsFor: 'testing' stamp: 'len 12/18/97 19:44'!
isSolution: anObject
	"Answer true if the argument is solution of the receiver."

	^ (self left isSolution: anObject) or: [self right isSolution: anObject]! !

!DisjunctionConnective methodsFor: 'printing' stamp: 'len 12/18/97 20:14'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	aStream
		nextPut: $(; print: self left; nextPut: $);
		nextPutAll: ' \/ ';
		nextPut: $(; print: self right; nextPut: $)! !


!ImplicationConnective commentStamp: '<historical>' prior: 0!
My instances are implications whose predicate and conclusion are Tarski sentences.

For an example try this:
	| x y |
	x _ Polynomial x.
	y _ Polynomial y.
	ImplicationConnective left: (x squared + y squared eq: 0) right: (x eq: 0).
!

!ImplicationConnective methodsFor: 'arithmetic' stamp: 'len 12/18/97 19:52'!
not
	"Answer the negation of the receiver."

	^ self left -> self right not! !

!ImplicationConnective methodsFor: 'testing' stamp: 'len 12/18/97 19:47'!
isSolution: anObject
	"Answer true if the argument is solution of the receiver."

	^ (self left isSolution: anObject) = (self right isSolution: anObject)! !

!ImplicationConnective methodsFor: 'printing' stamp: 'len 12/18/97 20:15'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	aStream
		nextPut: $(; print: self left; nextPut: $);
		nextPutAll: ' -> ';
		nextPut: $(; print: self right; nextPut: $)! !


!Infinity commentStamp: '<historical>' prior: 0!
My instances are the real +infinity or -infinity.

For some examples try these:
	Infinity positive * Infinity negative.
	Infinity positive * 2.
	Infinity positive - 7811234871239847.
	Infinity negative / -199.
	Infinity positive reciprocal.
	Infinity positive > Infinity negative.
	Infinity negative < -19238479182374598172349871234.
	Infinity negative > 0.
	Infinity negative min: Infinity positive.

The following are examples of undeterminations (they produce an error):
	Infinity positive + Infinity negative.
	Infinity positive * 0.
	Infinity positive / Infinity positive.
	Infinity positive raisedToInteger: 0.
!

!Infinity methodsFor: 'accessing-private' stamp: 'len 10/9/97 20:16'!
sign: anInteger
	sign _ anInteger! !

!Infinity methodsFor: 'accessing' stamp: 'len 10/9/97 20:17'!
sign
	"Answer the sign of the receiver."

	^ sign! !

!Infinity methodsFor: 'arithmetic' stamp: 'len 11/14/97 14:49'!
* anObject
	"Answer the product of the receiver by the argument."

	anObject = 0 ifTrue: [^ self errorUndetermined].
	^ self class sign: self sign * anObject sign! !

!Infinity methodsFor: 'arithmetic' stamp: 'len 12/13/97 02:26'!
+ anObject
	"Answer the sum of the receiver and the argument."

	(anObject isInfinity and: [self sign ~= anObject sign])
		ifTrue: [^ self errorUndetermined].
	^ self! !

!Infinity methodsFor: 'arithmetic' stamp: 'len 11/12/97 21:30'!
- anObject
	"Answer the difference between the receiver and the argument."

	^ self + anObject negated! !

!Infinity methodsFor: 'arithmetic' stamp: 'len 10/9/97 20:24'!
/ anObject
	"Answer the division of the receiver by the argument."

	^ self * anObject reciprocal! !

!Infinity methodsFor: 'arithmetic' stamp: 'len 11/12/97 21:31'!
negated
	"Answer a copy of the receiver with the sign changed."

	^ self class sign: self sign negated! !

!Infinity methodsFor: 'arithmetic' stamp: 'len 10/17/97 04:11'!
raisedToInteger: anInteger
	"Answer the receiver raised to the integer anInteger."

	anInteger = 0 ifTrue: [^ self errorUndetermined].
	anInteger negative ifTrue: [^ 0].
	^ anInteger odd ifTrue: [self] ifFalse: [self negated]! !

!Infinity methodsFor: 'arithmetic' stamp: 'len 11/12/97 21:32'!
reciprocal
	"Answer zero. (1 / self)"

	^ 0! !

!Infinity methodsFor: 'arithmetic' stamp: 'len 10/17/97 04:09'!
squared
	"Answer the square of the receiver."

	^ self class positive! !

!Infinity methodsFor: 'comparing' stamp: 'len 12/13/97 02:26'!
< anObject
	"Answer true if the receiver is lower than the argument."

	anObject isInfinity ifTrue: [^ self sign < anObject sign].
	^ self negative! !

!Infinity methodsFor: 'comparing' stamp: 'len 11/14/97 14:35'!
= anObject
	"Answer true if the receiver equals the argument."

	^ self class == anObject class and: [self sign = anObject sign]! !

!Infinity methodsFor: 'comparing' stamp: 'len 12/13/97 02:26'!
> anObject
	"Answer true if the receiver is greater than the argument."

	anObject isInfinity ifTrue: [^ self sign > anObject sign].
	^ self positive! !

!Infinity methodsFor: 'comparing' stamp: 'len 11/14/97 14:35'!
hash
	"Answer the hash value of the receiver."

	^ self sign hash! !

!Infinity methodsFor: 'testing' stamp: 'len 12/13/97 02:25'!
isInfinity
	"Answer true if the receiver is infinity."

	^ true! !

!Infinity methodsFor: 'testing' stamp: 'len 11/14/97 14:50'!
negative
	"Answer true if the receiver is negative."

	^ self sign negative! !

!Infinity methodsFor: 'testing' stamp: 'len 11/14/97 14:50'!
positive
	"Answer true if the receiver is positive."

	^ self sign positive! !

!Infinity methodsFor: 'testing' stamp: 'len 11/14/97 14:51'!
strictlyPositive
	"Answer true if the receiver is strictly positive."

	^ self positive! !

!Infinity methodsFor: 'private' stamp: 'len 10/9/97 20:29'!
errorUndetermined
	^ self error: 'undetermined'! !

!Infinity methodsFor: 'printing' stamp: 'len 10/9/97 20:13'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	self negative ifTrue: [aStream nextPut: $-].
	aStream nextPutAll: 'infinity'! !


!Infinity class methodsFor: 'instance creation' stamp: 'len 10/17/97 04:07'!
negative
	"Answer a new instance of the receiver representing -infinity."

	^ self sign: -1! !

!Infinity class methodsFor: 'instance creation' stamp: 'len 10/17/97 04:07'!
positive
	"Answer a new instance of the receiver representing +infinity."

	^ self sign: 1! !

!Infinity class methodsFor: 'instance creation' stamp: 'len 10/9/97 20:27'!
sign: anInteger
	"Answer a new instance of the receiver with sign anInteger."

	^ self new sign: anInteger! !


!Matrix commentStamp: '<historical>' prior: 0!
My instances are matrices.
Each instance stores the collection of its rows (instances of Tuple).

For an exmaple try this:
	Matrix fromString:
		'0 1 -3 1
		2 0 1 5
		1 -5 7 1
		3 1 5 5'.
!

!Matrix methodsFor: 'initialization' stamp: 'len 10/5/97 20:55'!
initialize
	self rows: OrderedCollection new! !

!Matrix methodsFor: 'initialization' stamp: 'len 5/28/1998 18:55'!
initialize: aPoint
	self rows: ((1 to: aPoint x) collect: [ :each | self class tupleClass dimension: aPoint y])! !

!Matrix methodsFor: 'accessing-private'!
rows
	^ rows
! !

!Matrix methodsFor: 'accessing-private' stamp: 'len 7/18/97 02:37'!
rows: anArray
	rows _ anArray! !

!Matrix methodsFor: 'accessing' stamp: 'len 11/28/97 02:30'!
addRow: aTuple
	"Add the argument at the end of the rows of the receiver. Answer the argument."

	^ self rows add: aTuple! !

!Matrix methodsFor: 'accessing' stamp: 'len 11/27/97 04:07'!
at: aPoint
	"Answer the element at the row y and the column x,
	where the argument is x@y."

	^ self atRow: aPoint y column: aPoint x! !

!Matrix methodsFor: 'accessing' stamp: 'len 11/27/97 04:07'!
at: aPoint put: anObject
	"Put the argument at the place in the row y
	and column x, where aPoint is x@y."

	^ self atRow: aPoint y column: aPoint x put: anObject! !

!Matrix methodsFor: 'accessing' stamp: 'len 11/28/97 02:03'!
atColumn: anInteger
	"Answer the column at the given position."

	^ self class tupleClass
		dimension: self numberOfRows
		fromBlock: [ :each | self atRow: each column: anInteger]! !

!Matrix methodsFor: 'accessing' stamp: 'len 11/28/97 02:30'!
atColumn: anInteger put: aTuple
	"Put the elements of the vector aTuple in the column anInteger. Answer aTuple."

	1 to: self numberOfRows do: [ :each |
		self atRow: each column: anInteger put: (aTuple at: each)].
	^ aTuple! !

!Matrix methodsFor: 'accessing' stamp: 'len 2/14/98 14:21'!
atRow: anInteger
	"Answer the row at the given place."

	^ self rows at: anInteger! !

!Matrix methodsFor: 'accessing'!
atRow: rowInteger column: columnInteger
	"Answer the element at the given place."

	^ (self atRow: rowInteger) at: columnInteger! !

!Matrix methodsFor: 'accessing'!
atRow: rowInteger column: columnInteger put: anObject
	"Put the element anObject at the given place."

	^ (self atRow: rowInteger) at: columnInteger put: anObject! !

!Matrix methodsFor: 'accessing' stamp: 'len 11/28/97 02:31'!
atRow: anInteger put: aTuple
	"Put aTuple at the given row. Answer aTuple."

	^ self rows at: anInteger put: aTuple! !

!Matrix methodsFor: 'accessing' stamp: 'len 11/27/97 01:56'!
dimension
	"Answer the dimension of the receiver."

	^ self numberOfColumns @ self numberOfRows! !

!Matrix methodsFor: 'accessing' stamp: 'len 8/21/97 00:50'!
lastColumn
	"Answer the last column of the receiver."

	^ self atColumn: self numberOfColumns! !

!Matrix methodsFor: 'accessing' stamp: 'len 10/5/97 21:04'!
numberOfColumns
	"Answer the number of columns in the receiver."

	^ self rows isEmpty ifTrue: [0] ifFalse: [self rows first dimension]! !

!Matrix methodsFor: 'accessing' stamp: 'len 10/5/97 21:04'!
numberOfRows
	"Answer the number of rows in the receiver."

	^ self rows size! !

!Matrix methodsFor: 'arithmetic' stamp: 'len 1/24/98 14:02'!
* anObject
	"Answer the product of the receiver by the argument."

	anObject isMatrix ifTrue: [^ self dotProduct: anObject].
	anObject isTuple ifTrue: [^ self dotProduct: anObject asColumnMatrix].
	^ self collect: [ :each | each * anObject]! !

!Matrix methodsFor: 'arithmetic' stamp: 'len 11/28/97 02:16'!
+ aMatrix
	"Answer the sum of the receiver and the argument."

	aMatrix dimension = self dimension
		ifFalse: [^ self errorDimensionNotMatch].

	^ self class rows:
		((1 to: self numberOfRows)
			collect: [ :each | (self atRow: each) + (aMatrix atRow: each)])
! !

!Matrix methodsFor: 'arithmetic' stamp: 'len 7/18/97 02:41'!
- anObject
	"Answer the difference of the receiver and the argument."

	 ^ self + anObject negated! !

!Matrix methodsFor: 'arithmetic' stamp: 'len 7/18/97 02:41'!
/ anObject
	"Answer the division of the receiver by the argument."

	^ self * anObject reciprocal! !

!Matrix methodsFor: 'arithmetic' stamp: 'len 2/18/98 18:56'!
dotProduct: aMatrix
	"Answer the dot product of the receiver with the argument."

	aMatrix numberOfRows = self numberOfColumns
		ifFalse: [^ self errorDimensionNotMatch].

	^ self class
		dimension: aMatrix numberOfColumns @ self numberOfRows
		fromBlock: [ :each | (self atRow: each y) scalar: (aMatrix atColumn: each x)]! !

!Matrix methodsFor: 'arithmetic' stamp: 'len 11/28/97 02:16'!
negated
	"Answer the additive inverse of the receiver."

	^ self class rows: (self rows collect: [ :each | each negated])! !

!Matrix methodsFor: 'arithmetic' stamp: 'len 11/11/97 00:41'!
raisedToInteger: anInteger
	"Answer the receiver raised to the power anInteger."

	anInteger = 0 ifTrue: [^ self identity].
	anInteger = 1 ifTrue: [^ self].
	anInteger > 1
		ifTrue: [^ (self * self raisedToInteger: anInteger // 2)
				* (self raisedToInteger: anInteger \\ 2)].
	^ (self raisedToInteger: anInteger negated) reciprocal! !

!Matrix methodsFor: 'arithmetic' stamp: 'len 8/23/97 17:29'!
reciprocal
	"Answer the multiplicative inverse of the receiver."

	^ self adjoint / self determinant! !

!Matrix methodsFor: 'arithmetic' stamp: 'len 8/14/97 18:40'!
squared
	"Answer the square of the receiver."

	^ self * self! !

!Matrix methodsFor: 'enumerating' stamp: 'len 11/28/97 02:16'!
collect: aBlock
	"Answer a copy of the receiver with the coefficients mapped by aBlock."

	^ self class rows: (self rows collect: [ :each | each collect: aBlock])! !

!Matrix methodsFor: 'enumerating' stamp: 'len 10/5/97 21:49'!
do: aBlock
	"Enumerate the entries of the receiver."

	self rowsDo: [ :each | each do: aBlock]! !

!Matrix methodsFor: 'enumerating' stamp: 'len 10/5/97 21:49'!
rowsDo: aBlock
	"Enumerate the rows of the receiver."

	self rows do: aBlock! !

!Matrix methodsFor: 'operations' stamp: 'len 9/7/97 01:00'!
adjoint
	"Answer the adjoint matrix of the receiver, i.e. the matrix
	such that multiplicated at the left by the receiver equals the
	scalar matrix with the determinant of the receiver in the diagonal."

	^ (self characteristic shift: -1) negated valueAt: self! !

!Matrix methodsFor: 'operations' stamp: 'len 12/13/97 15:37'!
characteristic
	"Answer the characteristic polynomial of the receiver."

	^ self class polynomialClass coefficients: self berkowitz asArray reversed! !

!Matrix methodsFor: 'operations' stamp: 'len 9/1/97 23:33'!
cofactor: aPoint
	"Answer the cofactor i@j of the receiver."

	^ (aPoint x + aPoint y) even
		ifTrue: [(self minor: aPoint) determinant]
		ifFalse: [(self minor: aPoint) determinant negated]! !

!Matrix methodsFor: 'operations' stamp: 'len 8/14/97 18:41'!
comatrix
	"Answer the co-matrix of the receiver (i.e., the
	 matrix '(a{ij})' where 'a{ij}' is the cofactor 'ij')."

	^ self adjoint transposed! !

!Matrix methodsFor: 'operations' stamp: 'len 9/7/97 01:00'!
companion
	"Answer the companion matrix of the receiver."

	^ self class companion: self characteristic! !

!Matrix methodsFor: 'operations' stamp: 'len 10/7/1998 06:14'!
determinant
	"Answer the determinant of the receiver."

	^ self characteristic independentCoefficient! !

!Matrix methodsFor: 'operations' stamp: 'len 11/28/97 02:04'!
diagonal
	"Answer the diagonal of the receiver as a vector."

	^ self class tupleClass
		dimension: (self numberOfRows min: self numberOfColumns)
		fromBlock: [ :each | self atRow: each column: each]! !

!Matrix methodsFor: 'operations' stamp: 'len 10/5/97 21:59'!
mapCoefficients: aBlock
	"Answer a copy of the receiver with the coefficients mapped by aBlock."

	^ self collect: aBlock! !

!Matrix methodsFor: 'operations' stamp: 'len 11/27/97 01:59'!
minor: aPoint
	"Answer the matrix obtained removing the column y and
	 the row x from the receiver, where aPoint is x@y."

	| x y |
	^ self class
		dimension: self numberOfColumns - 1 @ (self numberOfRows - 1)
		fromBlock: [ :each |
			each x < aPoint x ifTrue: [x _ each x] ifFalse: [x _ each x + 1].
			each y < aPoint y ifTrue: [y _ each y] ifFalse: [y _ each y + 1].
			self atRow: y column: x]! !

!Matrix methodsFor: 'operations' stamp: 'len 9/1/97 23:34'!
trace
	"Answer the trace of the receiver."

	| answer |
	answer _ self atRow: 1 column: 1.
	2 to: (self numberOfRows min: self numberOfColumns) do: [ :each |
		answer _ answer + (self atRow: each column: each)].
	^ answer! !

!Matrix methodsFor: 'operations' stamp: 'len 8/12/97 21:12'!
transposed
	"Answer the transpose of the receiver."

	| answer |
	answer _ self class new.
	1 to: self numberOfColumns do:
		[ :each | answer addRow: (self atColumn: each)].
	^ answer! !

!Matrix methodsFor: 'operations' stamp: 'len 10/5/97 22:02'!
valueAt: anObject
	"Answer the receiver evaluated at the argument."

	^ self collect: [ :each | each valueAt: anObject]! !

!Matrix methodsFor: 'comparing' stamp: 'len 10/5/97 22:03'!
= anObject
	"Answer true if the receiver equals the argument."

	^ self class == anObject class and: [self rows = anObject rows]! !

!Matrix methodsFor: 'comparing' stamp: 'len 10/5/97 22:03'!
hash
	"Answer the hash value for the receiver."

	^ self rows hash! !

!Matrix methodsFor: 'testing' stamp: 'len 10/5/97 21:47'!
isEmpty
	"Answer true if the receiver has no entries."

	^ self rows isEmpty! !

!Matrix methodsFor: 'testing' stamp: 'len 1/24/98 14:01'!
isMatrix
	"Answer true if the receiver is a matrix."

	^ true! !

!Matrix methodsFor: 'testing' stamp: 'len 7/18/97 02:47'!
isNull
	"Answer true if the receiver is null."

	self rows do: [ :each | each isNull ifFalse: [^false]].
	^ true! !

!Matrix methodsFor: 'testing' stamp: 'len 8/23/97 19:17'!
isOrthogonal
	"Answer true if the receiver is an orthogonal matrix."

	^ self isSquare and: [self * self transposed = self identity]! !

!Matrix methodsFor: 'testing' stamp: 'len 8/28/97 19:00'!
isSelfAdjoint
	"Answer true if the receiver is a self-adjoint matrix."

	^ self = self adjoint transposed! !

!Matrix methodsFor: 'testing' stamp: 'len 8/14/97 18:44'!
isSingular
	"Answer true if the receiver is a singular matrix."

	^ self determinant isNull! !

!Matrix methodsFor: 'testing' stamp: 'len 9/5/97 13:33'!
isSkewSymmetric
	"Answer true if the receiver is a skew-symmetric matrix."

	^ self negated = self transposed! !

!Matrix methodsFor: 'testing' stamp: 'len 8/12/97 21:15'!
isSquare
	"Answer true if the receiver is a square matrix."

	^ self numberOfRows = self numberOfColumns! !

!Matrix methodsFor: 'testing' stamp: 'len 8/12/97 21:13'!
isSymmetric
	"Answer true if the receiver is a symmetric matrix."

	^ self = self transposed! !

!Matrix methodsFor: 'converting' stamp: 'len 11/22/97 23:47'!
adaptFraction: aFraction
	"If I am involved in arithmetic with a Fraction, convert the Fraction."
	^ self identity * aFraction! !

!Matrix methodsFor: 'converting' stamp: 'len 11/22/97 23:46'!
adaptInteger: anInteger
	"If I am involved in arithmetic with an Integer, convert the Integer."
	^ self identity * anInteger! !

!Matrix methodsFor: 'converting' stamp: 'len 11/22/97 23:47'!
adaptToFraction
	"If I am involved in arithmetic with a Fraction, do not convert me."
	^ self! !

!Matrix methodsFor: 'converting' stamp: 'len 11/22/97 23:46'!
adaptToInteger
	"If I am involved in arithmetic with an Integer, do not convert me."
	^ self! !

!Matrix methodsFor: 'converting' stamp: 'len 11/28/97 02:23'!
asTuple
	"Answer the receiver converted to Tuple."

	| answer |
	self rowsDo: [ :each |
		answer _ answer isNil ifTrue: [each] ifFalse: [answer, each]].
	^ answer! !

!Matrix methodsFor: 'copying' stamp: 'len 10/5/97 20:55'!
copy
	"Anwer a copy of the receiver."

	^ self class basicNew rows: self rows copy! !

!Matrix methodsFor: 'copying' stamp: 'len 11/24/97 01:42'!
copyFrom: aPoint to: anotherPoint
	"Answer the submatrix of the receiver from aPoint to anotherPoint."

	| start |
	start _ aPoint - (1@1).
	^ self class
		dimension: anotherPoint - start
		fromBlock: [ :each | self at: start + each]! !

!Matrix methodsFor: 'constants' stamp: 'len 5/28/1998 19:21'!
identity
	^ self class dimension: self dimension scalar: self identityCoefficient! !

!Matrix methodsFor: 'constants' stamp: 'len 10/16/97 03:15'!
identityCoefficient
	| element |
	(self isEmpty or: [(element _ self atRow: 1 column: 1) isNil]) ifFalse: [^ element identity].
	^ self class identityCoefficient! !

!Matrix methodsFor: 'constants' stamp: 'len 5/28/1998 19:22'!
null
	^ self class dimension: self dimension scalar: self nullCoefficient! !

!Matrix methodsFor: 'constants' stamp: 'len 10/16/97 03:16'!
nullCoefficient
	| element |
	(self isEmpty or: [(element _ self atRow: 1 column: 1) isNil]) ifFalse: [^ element null].
	^ self class nullCoefficient! !

!Matrix methodsFor: 'private' stamp: 'len 5/28/1998 19:21'!
berkowitz
	"Answer a vector containing the coefficients of the characteristic
	polynomial of the receiver. It's calculated using the Berkowitz algorithm,
	that uses small space in comparision with the classical gaussian elimination."

	| vect C Ar R S Q |

	self numberOfRows = 1 ifTrue: [
		^ self class tupleClass
			with: self identityCoefficient negated with: (self at: 1@1)].
	self numberOfRows = 2 ifTrue: [
		^ self class tupleClass
			with: self identityCoefficient
			with: ((self at: 1@1) + (self at: 2@2)) negated
			with: (self at: 1@1) * (self at: 2@2) - ((self at: 2@1) * (self at: 1@2))].

	vect _ self class tupleClass
		with: self identityCoefficient
		with: (self at: 2@2) negated - (self at: 1@1)
		with: (self at: 2@2) * (self at: 1@1) -
			  ((self at: 2@1) * (self at: 1@2)).

	3 to: self numberOfRows do: [ :r |
		C _ self class dimension: r @ (r+1) scalar: self nullCoefficient.
		Ar _ self copyFrom: 1@1 to: r - 1 @ (r - 1).

		R _ (self atRow: r) copyFrom: 1 to: r - 1.
		S _ (self atColumn: r) copyFrom: 1 to: r - 1.

		C at: 1@1 put: self identityCoefficient negated.
		C at: 1@2 put: (self at: r@r).
		C at: 1@3 put: (R scalar: S).

		Q _ (Ar * S) asTuple.

		C at: 1@4 put: (R scalar: Q).

		3 to: r - 1 do: [ :i |
			Q _ (Ar * Q) asTuple.
			C at: 1 @ (i+2) put: (R scalar: Q)].

		2 to: r do: [ :i |
			0 to: r+1-i do: [ :j |
				C at: i @ (i+j) put: (C at: 1 @ (j+1))]].

		vect _ (C * vect) asTuple].

	^ vect! !

!Matrix methodsFor: 'private' stamp: 'len 11/13/97 19:50'!
berkowitz: x
	| polcar vect r power |

	r _ self numberOfRows + 1.
	vect _ self berkowitz.
	polcar _ x null.
	power _ x identity.
	r to: 1 by: -1 do: [ :i |
		polcar _ (power mapCoefficients: [ :each | each * (vect at: i)]) + polcar.
		power _ power * x].

	^ r odd ifTrue: [polcar] ifFalse: [polcar negated]! !

!Matrix methodsFor: 'private' stamp: 'len 8/13/97 21:50'!
errorDimensionNotMatch
	self error: 'dimension not match'! !

!Matrix methodsFor: 'printing' stamp: 'len 9/1/97 23:36'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	| pads string pad |
	pads _ (1 to: self numberOfColumns) collect: [ :each | 0].
	self rows do: [ :each |
		1 to: each dimension do: [ :index |
			pads at: index put: ((pads at: index) max: (each at: index) printString size)]].
	self rows do: [ :each |
		aStream nextPut: $[.
		1 to: each dimension - 1 do: [ :index |
			string _ (each at: index) printString.
			pad _ (pads at: index) - string size.
			pad // 2 timesRepeat: [aStream space].
			aStream nextPutAll: string.
			pad // 2 + (pad \\ 2) + 3 timesRepeat: [aStream space]].
		string _ (each at: each dimension) printString.
		pad _ (pads at: each dimension) - string size.
		pad // 2 timesRepeat: [aStream space].
		aStream nextPutAll: string.
		pad // 2 + (pad \\ 2) timesRepeat: [aStream space].
		aStream nextPut: $]; cr]! !

!Matrix methodsFor: 'printing' stamp: 'len 9/1/97 23:36'!
printTeXOn: aStream
	"Print a representation of the receiver on the stream aStream."

	aStream nextPutAll: '\pmatrix'; cr.
	self rows do: [ :each |
		1 to: each dimension - 1 do: [ :index |
			aStream print: (each at: index); nextPutAll: ' & '].
		aStream print: (each at: each dimension); nextPutAll: ' \cr'; cr].
	aStream nextPutAll: '\endmatrix'
! !


!Matrix class methodsFor: 'instance creation' stamp: 'len 11/27/97 01:54'!
companion: aPolynomial
	"Answer the companion matrix of the receiver."

	| dim null id |
	null _ aPolynomial nullCoefficient.
	id _ aPolynomial identityCoefficient.
	dim _ aPolynomial degree max: 0.
	^ self dimension: dim @ dim fromBlock: [ :each |
		each y < dim
			ifTrue: [each x - 1 = each y ifTrue: [id] ifFalse: [null]]
			ifFalse: [(aPolynomial coefficientAt: each x - 1) negated]]! !

!Matrix class methodsFor: 'instance creation' stamp: 'len 8/14/97 18:47'!
dimension: aPoint
	"Answer a new instance of the receiver representing
	a matrix of the dimension given by the argument."

	^ self basicNew initialize: aPoint! !

!Matrix class methodsFor: 'instance creation' stamp: 'len 11/28/97 02:04'!
dimension: aPoint fromBlock: aBlock
	| answer |
	answer _ self new.
	1 to: aPoint y do: [ :each |
		answer addRow:
			(self tupleClass
				dimension: aPoint x
				fromBlock: [ :some | aBlock value: some @ each])].
	^ answer! !

!Matrix class methodsFor: 'instance creation' stamp: 'len 10/20/97 22:07'!
dimension: aPoint scalar: anObject
	"Answer a new instance of the receiver representing the
	scalar matrix with anObject in the diagonal."

	| null |
	null _ anObject null.
	^ self dimension: aPoint fromBlock: [ :each |
		each x = each y ifTrue: [anObject] ifFalse: [null]]! !

!Matrix class methodsFor: 'instance creation' stamp: 'len 11/28/97 02:04'!
fromString: aString
	"Answer a new instance of the receiver with
	the entries read from aString."

	| stream answer |
	stream _ ReadStream on: aString.
	answer _ self new.
	[stream atEnd] whileFalse: [
		answer addRow:
			(self tupleClass fromArray:
				(stream nextLine asArrayOfSubstrings
					collect: [ :each | each asNumber]))].
	^ answer! !

!Matrix class methodsFor: 'instance creation' stamp: 'len 8/12/97 21:10'!
new
	"Answer a new instance of the receiver."

	^ super new initialize! !

!Matrix class methodsFor: 'instance creation' stamp: 'len 1/9/98 21:33'!
null: aPoint
	"Answer the null (rational) matrix of dimension aPoint."

	^ self dimension: aPoint scalar: self nullCoefficient! !

!Matrix class methodsFor: 'instance creation' stamp: 'len 11/28/97 02:17'!
rows: aCollection
	"Answer a new instance of the receiver with rows from aCollection."

	^ self basicNew rows: aCollection! !

!Matrix class methodsFor: 'related classes' stamp: 'len 11/23/97 00:07'!
polynomialClass
	^ Polynomial! !

!Matrix class methodsFor: 'related classes' stamp: 'len 11/28/97 02:18'!
tupleClass
	^ Tuple! !

!Matrix class methodsFor: 'constants' stamp: 'len 8/30/97 01:04'!
identityCoefficient
	^ 1! !

!Matrix class methodsFor: 'constants' stamp: 'len 8/30/97 01:04'!
nullCoefficient
	^ 0! !

!Matrix class methodsFor: 'examples' stamp: 'len 11/28/97 02:16'!
vandermonde: anInteger
	"Answer the anInteger-th Vandermonde matrix."

	| row rows |
	row _ (1 to: anInteger) collect: [ :each | self polynomialClass x: each].
	rows _ (1 to: anInteger) collect: [ :each |
		self tupleClass
			fromArray: (row collect: [ :some | some raisedToInteger: each - 1])].
	^ self rows: rows! !


!Monomial commentStamp: '<historical>' prior: 0!
My instances are monomials in one or many variables.
Each Monomial has a coefficient and a MonomialLiteral (power product).
!

!Monomial methodsFor: 'accessing-private'!
coefficient: value
	coefficient _ value
! !

!Monomial methodsFor: 'accessing-private'!
literal: aLiteral
	literal _ aLiteral
! !

!Monomial methodsFor: 'accessing' stamp: 'len 10/18/97 02:13'!
coefficient
	"Answer the coefficient of the receiver."

	^ coefficient
! !

!Monomial methodsFor: 'accessing' stamp: 'len 11/6/97 20:58'!
indeterminates
	"Answer the indeterminates of the receiver."

	^ self literal indeterminates! !

!Monomial methodsFor: 'accessing' stamp: 'len 10/18/97 02:13'!
literal
	"Answer the literal part of the receiver."

	^ literal
! !

!Monomial methodsFor: 'arithmetic' stamp: 'len 1/24/98 13:46'!
* anObject
	"Answer the product of the receiver by the argument."

	anObject isMonomial
		ifTrue: [^ self class
					coefficient: self coefficient * anObject coefficient
					literal: self literal * anObject literal].
	anObject isMonomialLiteral
		ifTrue: [^ self class
					coefficient: self coefficient
					literal: self literal * anObject].
	anObject isPolynomial ifTrue: [^ self asPolynomial * anObject].
	^ self class
		coefficient: self coefficient * anObject
		literal: self literal! !

!Monomial methodsFor: 'arithmetic' stamp: 'len 2/5/98 20:06'!
+ anObject
	"Answer the sum of the receiver with the argument."

	(anObject isMonomial and: [anObject literal = self literal])
		ifTrue: [^ self class
					coefficient: self coefficient + anObject coefficient
					literal: self literal].
	^ self asPolynomial + anObject! !

!Monomial methodsFor: 'arithmetic' stamp: 'len 11/23/97 00:30'!
- anObject
	"Answer the difference between the receiver with the argument."

	^ self + anObject negated! !

!Monomial methodsFor: 'arithmetic' stamp: 'len 1/24/98 13:47'!
/ anObject
	"Answer the exact division of the receiver by the argument."

	anObject isMonomial
		ifTrue: [^ self class
					coefficient: self coefficient / anObject coefficient
					literal: self literal / anObject literal].
	anObject isMonomialLiteral
		ifTrue: [^ self class
					coefficient: self coefficient
					literal: self literal / anObject].
	anObject isPolynomial ifTrue: [^ self asPolynomial / anObject].
	^ self class
		coefficient: self coefficient / anObject
		literal: self literal! !

!Monomial methodsFor: 'arithmetic' stamp: 'len 10/18/97 02:14'!
negated
	"Answer the additive inverse of the receiver."

	^ self class
		coefficient: self coefficient negated
		literal: self literal! !

!Monomial methodsFor: 'operations' stamp: 'len 10/18/97 02:15'!
degree
	"Answer the degree of the receiver."

	^ self isNull ifTrue: [Infinity negative] ifFalse: [self literal degree]! !

!Monomial methodsFor: 'operations' stamp: 'len 10/18/97 02:15'!
degreeIn: anInteger
	"Answer the degree of the receiver in the anInteger-th indeterminate."

	^ self isNull ifTrue: [Infinity negative] ifFalse: [self literal degreeIn: anInteger]! !

!Monomial methodsFor: 'operations' stamp: 'len 11/22/97 19:53'!
derivative
	"Answer the derivative of the receiver."

	^ self derivativeIn: 1! !

!Monomial methodsFor: 'operations' stamp: 'len 1/27/98 23:29'!
derivativeIn: anInteger
	"Answer the derivative of the receiver in the anInteger-th indeterminate."

	| degree |
	(degree _ self degreeIn: anInteger) <= 0 ifTrue: [^ self null].
	^ self class
		coefficient: self coefficient * degree
		literal: (self literal copy at: anInteger put: degree - 1; yourself)! !

!Monomial methodsFor: 'operations' stamp: 'len 11/23/97 00:57'!
valueAt: anObject
	"Answer the value of the receiver at the argument."

	^ self coefficient * (self literal valueAt: anObject)! !

!Monomial methodsFor: 'comparing' stamp: 'len 9/1/97 19:16'!
= aMonomial
	"Answer true if the receiver equals the argument."

	^ self class == aMonomial class
		and: [aMonomial literal = self literal
			and: [aMonomial coefficient = self coefficient]]! !

!Monomial methodsFor: 'comparing' stamp: 'len 9/1/97 19:17'!
hash
	"Answer the hash value for the receiver."

	^ self literal hash + self coefficient hash
! !

!Monomial methodsFor: 'testing' stamp: 'len 9/1/97 19:17'!
isConstant
	"Answer true if the receiver is constant."

	^ self isNull or: [self degree = 0]! !

!Monomial methodsFor: 'testing' stamp: 'len 1/24/98 13:42'!
isMonomial
	"Answer true if the receiver is a monomial."

	^ true! !

!Monomial methodsFor: 'testing' stamp: 'len 9/1/97 19:17'!
isNull
	"Answer true if the receiver is the null monomial."

	^ self coefficient isNull
! !

!Monomial methodsFor: 'testing' stamp: 'len 11/23/97 01:20'!
isUnivariateIn: anInteger
	"Answer true if the receiver is an univariate
	monomial in the anInteger-th indeterminate."

	^ (self degreeIn: anInteger) = self degree! !

!Monomial methodsFor: 'converting' stamp: 'len 1/24/98 13:48'!
adaptFraction: aFraction
	"If I am involved in arithmetic with a Fraction, convert the Fraction."
	^ self identity * aFraction! !

!Monomial methodsFor: 'converting' stamp: 'len 7/12/97 23:06'!
adaptInteger: anInteger
	"If I am involved in arithmetic with an Integer, convert the Integer."
	^ self identity * anInteger! !

!Monomial methodsFor: 'converting' stamp: 'len 1/24/98 13:48'!
adaptToFraction
	"If I am involved in arithmetic with a Fraction, do not convert me."
	^self! !

!Monomial methodsFor: 'converting'!
adaptToInteger
	"If I am involved in arithmetic with an Integer, do not convert me."
	^self! !

!Monomial methodsFor: 'converting' stamp: 'len 10/20/97 00:28'!
asPolynomial
	"Convert the receiver to a polynomial."

	^ self class polynomialClass fromMonomial: self! !

!Monomial methodsFor: 'converting' stamp: 'len 11/23/97 01:13'!
univariateIn: anInteger
	"Answer the receiver as univariate monomial in the anInteger-th indeterminate."

	| d |
	^ (d _ self degreeIn: anInteger) < self degree
		ifTrue: [self class
					coefficient: (self copyWithout: anInteger) asPolynomial
					literal: (self literal class x: anInteger to: d)]
		ifFalse: [self]! !

!Monomial methodsFor: 'copying' stamp: 'len 10/22/97 01:31'!
complete: anInteger with: anotherInteger
	"Answer a copy of the receiver of degree anInteger
	completing with a power of anotherInteger."

	^ self class
		coefficient: self coefficient
		literal: (self literal complete: anInteger with: anotherInteger)! !

!Monomial methodsFor: 'copying' stamp: 'len 2/6/98 13:29'!
copy
	"Answer a copy of the receiver."

	^ self class
		coefficient: self coefficient
		literal: self literal copy! !

!Monomial methodsFor: 'copying' stamp: 'len 10/22/97 21:49'!
copyWithout: anInteger
	"Answer a copy of the receiver with the anInteger-th indeterminate removed."

	^ self class coefficient: self coefficient literal: (self literal copyWithout: anInteger)! !

!Monomial methodsFor: 'constants' stamp: 'len 11/7/97 06:28'!
identity
	"Answer the monomial that is the constant identity."

	^ self class coefficient: self coefficient identity literal: self literal class identity! !

!Monomial methodsFor: 'constants' stamp: 'len 11/7/97 06:28'!
null
	"Answer the monomial that is the constant null."

	^ self class coefficient: self coefficient null literal: self literal class identity! !

!Monomial methodsFor: 'printing-private' stamp: 'len 11/23/97 01:53'!
printCoefficientOn: aStream
	"Print the coefficient of the receiver on the stream aStream."

	| string numeric |
	string _ self coefficient printString.
	string first = $-
		ifTrue: [aStream nextPut: $-. string _ self coefficient negated printString].
	numeric _ (string detect: [ :each | each isDigit not] ifNone: []) isNil.
	aStream nextPutAll:
		((numeric or: [string first = $(]) ifTrue: [string] ifFalse: ['(', string, ')'])! !

!Monomial methodsFor: 'printing' stamp: 'len 9/1/97 19:21'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	| coef |
	coef _ self coefficient.
	self isConstant ifTrue: [self printCoefficientOn: aStream. ^ self].
	coef = coef identity ifFalse: [
		coef = coef identity negated
			ifTrue: [aStream nextPut: $-]
			ifFalse: [self printCoefficientOn: aStream]].
	self literal printOn: aStream! !

!Monomial methodsFor: 'printing' stamp: 'len 9/1/97 19:21'!
printOn: aStream withNames: aDictionary
	"Print a representation of the receiver on the stream aStream
	using the the names in aDictionary for the indeterminates."

	| coef |
	coef _ self coefficient.
	self isConstant ifTrue: [self printCoefficientOn: aStream. ^ self].
	coef = coef identity ifFalse: [
		coef = coef identity negated
			ifTrue: [aStream nextPut: $-]
			ifFalse: [self printCoefficientOn: aStream]].
	self literal printOn: aStream withNames: aDictionary! !


!Monomial class methodsFor: 'instance creation' stamp: 'len 11/22/97 19:46'!
coefficient: anObject degree: anInteger
	"Answer an instance of the receiver representing the
	monomial of degree anInteger with argument anObject."

	^ self x: 1 to: anInteger coefficient: anObject! !

!Monomial class methodsFor: 'instance creation' stamp: 'len 10/18/97 02:11'!
coefficient: anObject literal: aMonomialLiteral
	"Answer a new instance of the receiver with
	coefficient anObject and literal aMonomialLiteral."

	^ self new coefficient: anObject; literal: aMonomialLiteral! !

!Monomial class methodsFor: 'instance creation' stamp: 'len 2/5/98 00:38'!
constant: anObject
	"Answer an instance of the receiver representing the constant anObject."

	^ self coefficient: anObject literal: self monomialLiteralClass identity! !

!Monomial class methodsFor: 'instance creation' stamp: 'len 11/22/97 19:46'!
degree: anInteger coefficient: anObject
	"Answer an instance of the receiver representing the
	monomial of degree anInteger with argument anObject."

	^ self coefficient: anObject degree: anInteger! !

!Monomial class methodsFor: 'instance creation' stamp: 'len 10/22/97 01:33'!
literal: aMonomialLiteral coefficient: anObject
	"Answer a new instance of the receiver with
	coefficient anObject and literal aMonomialLiteral."

	^ self coefficient: anObject; literal: aMonomialLiteral! !

!Monomial class methodsFor: 'instance creation' stamp: 'len 10/22/97 01:36'!
x: anInteger
	"Answer an instance of the receiver representing
	monomial with the sole anInteger-th indeterminate
	with degree 1 and with coefficient 1."

	^ self x: anInteger coefficient: self identityCoefficient! !

!Monomial class methodsFor: 'instance creation' stamp: 'len 10/22/97 01:36'!
x: anInteger coefficient: anObject
	"Answer an instance of the receiver representing
	monomial with the sole anInteger-th indeterminate
	with degree 1 and with coefficient anObject."

	^ self x: anInteger to: 1 coefficient: anObject! !

!Monomial class methodsFor: 'instance creation' stamp: 'len 10/22/97 01:37'!
x: anInteger to: anotherInteger
	"Answer an instance of the receiver representing
	monomial with the sole anInteger-th indeterminate
	with degree 1 and with coefficient 1."

	^ self x: anInteger to: anotherInteger coefficient: self identityCoefficient! !

!Monomial class methodsFor: 'instance creation' stamp: 'len 2/5/98 00:38'!
x: anInteger to: anotherInteger coefficient: anObject
	"Answer an instance of the receiver representing
	monomial with the sole anInteger-th indeterminate
	raised to anotherInteger and with coefficient anObject."

	^ self coefficient: anObject literal: (self monomialLiteralClass x: anInteger to: anotherInteger)! !

!Monomial class methodsFor: 'constants' stamp: 'len 9/1/97 21:25'!
identityCoefficient
	^ 1! !

!Monomial class methodsFor: 'constants' stamp: 'len 9/1/97 21:25'!
nullCoefficient
	^ 0! !

!Monomial class methodsFor: 'related classes' stamp: 'len 2/5/98 00:37'!
monomialLiteralClass
	^ MonomialLiteral! !

!Monomial class methodsFor: 'related classes' stamp: 'len 11/23/97 00:13'!
polynomialClass
	^ Polynomial! !


!MonomialLiteral commentStamp: '<historical>' prior: 0!
My instances are power products of one or many variables,
i.e. the literal part of monomials.
!

!MonomialLiteral methodsFor: 'initialization' stamp: 'len 10/23/97 22:39'!
initialize: anInteger
	self contents: ((1 to: anInteger) collect: [ :each | 0])! !

!MonomialLiteral methodsFor: 'accessing-private' stamp: 'len 10/18/97 02:06'!
contents
	^ contents! !

!MonomialLiteral methodsFor: 'accessing-private' stamp: 'len 11/6/97 20:11'!
contents: anArray
	contents _ anArray! !

!MonomialLiteral methodsFor: 'accessing' stamp: 'len 12/4/97 00:51'!
at: anInteger
	"Answer the exponent of the anInteger-th indeterminate."

	^ (anInteger <= self size and: [anInteger > 0])
		ifTrue: [self contents at: anInteger] ifFalse: [0]! !

!MonomialLiteral methodsFor: 'accessing' stamp: 'len 1/27/98 23:28'!
at: anInteger put: anotherInteger
	"Set the exponent of the anInteger-th indeterminate to anotherInteger.
	Answer anotherInteger."

	anInteger > self size ifTrue: [
		anInteger = 0
			ifTrue: [^ anotherInteger]
			ifFalse: [self contents:
						self contents, ((self size + 1 to: anInteger) collect: [ :each | 0])]].
	anInteger < 1
		ifTrue: [^ anotherInteger ~= 0 ifTrue: [self halt] ifFalse: [anotherInteger]].
	^ self contents at: anInteger put: anotherInteger! !

!MonomialLiteral methodsFor: 'accessing' stamp: 'len 11/6/97 20:36'!
indeterminates
	"Answer the indeterminates of the receiver."

	^ 1 to: self size! !

!MonomialLiteral methodsFor: 'accessing' stamp: 'len 10/22/97 22:31'!
lastIndeterminate
	"Answer the leading indeterminate of the receiver
	(the last indeterminate effectively present)."

	| answer |
	answer _ 0.
	self do: [ :each | answer _ answer max: each].
	^ answer! !

!MonomialLiteral methodsFor: 'accessing' stamp: 'len 11/6/97 20:35'!
size
	"Answer the number of indeterminates of the receiver."

	^ self contents size! !

!MonomialLiteral methodsFor: 'arithmetic' stamp: 'len 11/6/97 20:49'!
* aMonomialLiteral
	"Answer the product of the receiver by the argument."

	| answer |
	(self size < aMonomialLiteral size) ifTrue: [^ aMonomialLiteral * self].
	answer _ self copy.
	aMonomialLiteral do: [ :each |
		answer at: each put: (self at: each) + (aMonomialLiteral at: each)].
	^ answer! !

!MonomialLiteral methodsFor: 'arithmetic' stamp: 'len 10/18/97 19:02'!
/ aMonomialLiteral
	"Answer the exact division of the receiver by the argument."

	| answer |
	answer _ self copy.
	aMonomialLiteral do: [ :each |
		(answer at: each put: (self at: each) - (aMonomialLiteral at: each))
			negative ifTrue: [^ self error: 'not exact division']].
	^ answer! !

!MonomialLiteral methodsFor: 'enumerating' stamp: 'len 11/6/97 20:30'!
do: aBlock
	"Enumerate the indeterminates of the receiver."

	(1 to: self size) do: [ :each | (self at: each) = 0 ifFalse: [aBlock value: each]]! !

!MonomialLiteral methodsFor: 'mathematical functions' stamp: 'len 11/6/97 20:30'!
gcd: aMonomialLiteral
	"Answer the greatest common divisor of the receiver and the argument."

	| answer |
	answer _ self class new: self size.
	self do: [ :each |
		answer at: each put: ((self at: each) min: (aMonomialLiteral at: each))].
	^ answer! !

!MonomialLiteral methodsFor: 'mathematical functions' stamp: 'len 1/27/98 23:31'!
lcm: aMonomialLiteral
	"Answer the least common multiple of the receiver and the argument."

	| answer max |
	answer _ self class new: (max _ self size max: aMonomialLiteral size).
	(1 to: max) do: [ :each |
		answer at: each put: ((self at: each) max: (aMonomialLiteral at: each))].
	^ answer! !

!MonomialLiteral methodsFor: 'operations' stamp: 'len 10/18/97 01:53'!
degree
	"Answer the degree of the receiver. By the degree is meant the
	sum of the powers to which the indererminates appear."

	| answer |
	answer _ 0.
	self do: [ :each | answer _ answer + (self at: each)].
	^ answer! !

!MonomialLiteral methodsFor: 'operations' stamp: 'len 10/18/97 02:01'!
degreeIn: anInteger
	"Answer the degree of the receiver in the indeterminate
	given by the argument, i.e. the power to which the
	indeterminate appears."

	^ self at: anInteger! !

!MonomialLiteral methodsFor: 'operations' stamp: 'len 12/13/97 05:24'!
valueAt: anObject
	"Answer the value of the receiver at the argument."

	| answer next |
	1 to: anObject size do: [ :each |
		next _ (anObject at: each) raisedToInteger: (self at: each).
		answer _ answer isNil ifTrue: [next] ifFalse: [next * answer]].
	^ answer! !

!MonomialLiteral methodsFor: 'comparing' stamp: 'len 10/22/97 23:58'!
< aMonomialLiteral
	"Answer the receiver is below the argument."

	^ (self >= aMonomialLiteral) not! !

!MonomialLiteral methodsFor: 'comparing' stamp: 'len 10/23/97 00:00'!
<= aMonomialLiteral
	"Answer the receiver is below or equal to the argument."

	^ (self > aMonomialLiteral) not! !

!MonomialLiteral methodsFor: 'comparing' stamp: 'len 10/18/97 02:04'!
= aMonomialLiteral
	"Answer true if the receiver equals the argument."

	self degree = aMonomialLiteral degree ifFalse: [^ false].
	self do: [ :each | (self at: each) = (aMonomialLiteral at: each) ifFalse: [^ false]].
	^ true! !

!MonomialLiteral methodsFor: 'comparing' stamp: 'len 2/5/98 00:46'!
> aMonomialLiteral
	"Answer true if the receiver is greater than
	the argument in the total lexicographic ordering."

	| n m |
	(n _ self degree) > (m _ aMonomialLiteral degree) ifTrue: [^ true].
	n < m ifTrue: [^ false].
	1 to: (self lastIndeterminate max: aMonomialLiteral lastIndeterminate) do: [ :each |
		(self at: each) < (aMonomialLiteral at: each) ifTrue: [^ false].
		(self at: each) > (aMonomialLiteral at: each) ifTrue: [^ true]].
	^ false! !

!MonomialLiteral methodsFor: 'comparing' stamp: 'len 2/5/98 00:46'!
>= aMonomialLiteral
	"Answer true if the receiver is greater than or equal
	to the argument in the total lexicographic ordering."

	| n m |
	(n _ self degree) > (m _ aMonomialLiteral degree) ifTrue: [^ true].
	n < m ifTrue: [^ false].
	1 to: (self lastIndeterminate max: aMonomialLiteral lastIndeterminate) do: [ :each |
		(self at: each) < (aMonomialLiteral at: each) ifTrue: [^ false].
		(self at: each) > (aMonomialLiteral at: each) ifTrue: [^ true]].
	^ true! !

!MonomialLiteral methodsFor: 'comparing' stamp: 'len 10/18/97 02:05'!
hash
	"Answer the hash value of the receiver."

	| sum |
	sum _ 0.
	self do: [ :each | sum _ (self at: each) * each + sum].
	^ sum hash! !

!MonomialLiteral methodsFor: 'testing' stamp: 'len 10/18/97 20:22'!
divides: aMonomialLiteral
	"Answer true if the receiver divedes the argument."

	self do: [ :each | (aMonomialLiteral at: each) < (self at: each) ifTrue: [^ false]].
	^ true! !

!MonomialLiteral methodsFor: 'testing' stamp: 'len 10/23/97 04:14'!
isMonomialLiteral
	"Answer true if the receiver is a monomial literal."

	^ true! !

!MonomialLiteral methodsFor: 'copying' stamp: 'len 10/22/97 01:31'!
complete: anInteger with: anotherInteger
	"Answer a copy of the receiver of degree anInteger completing
	with a power of the indeterminate anotherInteger."

	| deg |
	(deg _ self degree) = anInteger ifTrue: [^ self].
	^ self copy
		at: anotherInteger put: (anInteger - deg + (self at: anotherInteger));
		yourself! !

!MonomialLiteral methodsFor: 'copying' stamp: 'len 11/6/97 20:53'!
copy
	^ self class new contents: self contents copy! !

!MonomialLiteral methodsFor: 'copying' stamp: 'len 10/22/97 01:29'!
copyWithout: anInteger
	"Answer a copy of the receiver with the anInteger-th indeterminate removed."

	^ self copy at: anInteger put: 0; yourself! !

!MonomialLiteral methodsFor: 'copying' stamp: 'len 10/22/97 01:28'!
copyWithoutAll: aCollection
	"Answer a copy of the receiver with all the
	indeterminates in the argument removed."

	| answer |
	answer _ self copy.
	aCollection do: [ :each | answer at: each put: 0].
	^ answer! !

!MonomialLiteral methodsFor: 'printing-private' stamp: 'len 12/21/97 20:53'!
defaultNames
	"Answer the default names for the indeterminates."

	^ self class defaultNames! !

!MonomialLiteral methodsFor: 'printing' stamp: 'len 7/13/97 00:44'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	self printOn: aStream withNames: self defaultNames! !

!MonomialLiteral methodsFor: 'printing' stamp: 'len 1/27/98 23:27'!
printOn: aStream withNames: namesDictionary
	"Print a representation of the receiver on the stream aStream
	using the names in namesDictionary for the indeterminates."

	| exp |
	self degree = 0 ifTrue: [aStream print: 1. ^ self].
	(self indeterminates select: [ :each | (self at: each) > 0])
		asSortedCollection do: [ :each |
			aStream nextPutAll:
				(namesDictionary
					at: each
					ifAbsent: ['{x', each printString, '}']).
			(exp _ (self degreeIn: each) printString) = '1'
				ifFalse: [aStream nextPut: $^.
						exp size = 1
							ifTrue: [aStream nextPutAll: exp]
							ifFalse: [aStream nextPut: ${; nextPutAll: exp; nextPut: $}]]]! !


!MonomialLiteral class methodsFor: 'instance creation' stamp: 'len 11/7/97 06:17'!
identity
	"Answer the identity literal (i.e., the literal without indeterminates)."

	^ self new: 0! !

!MonomialLiteral class methodsFor: 'instance creation' stamp: 'len 11/6/97 20:09'!
new: anInteger
	"Answer a new instance of the receiver representing
	the empty literal of anInteger indeterminates."

	^ self new initialize: anInteger! !

!MonomialLiteral class methodsFor: 'instance creation' stamp: 'len 10/23/97 22:37'!
new: anInteger x: anotherInteger
	"Answer a new instance of the receiver representing the a literal
	of anInteger indeterminates, one of those (the anotherInteger-th)
	is effectively present with degree 1."

	^ self new: anInteger x: anInteger to: 1! !

!MonomialLiteral class methodsFor: 'instance creation' stamp: 'len 10/23/97 22:38'!
new: anInteger x: anotherInteger to: thirthInteger
	"Answer a new instance of the receiver representing the a literal
	of anInteger indeterminates, one of those (the anotherInteger-th)
	is effectively present with degree thirthInteger."

	^ (self new: anInteger) at: anotherInteger put: thirthInteger; yourself! !

!MonomialLiteral class methodsFor: 'instance creation' stamp: 'len 10/22/97 01:38'!
x: anInteger
	"Answer a new instance of the receiver with only one indeterminate: the argument."

	^ self x: anInteger to: 1! !

!MonomialLiteral class methodsFor: 'instance creation' stamp: 'len 11/7/97 06:25'!
x: anInteger to: anotherInteger
	"Answer a new instance of the receiver with only one
	indeterminate, anInteger, raised to anotherInteger."

	^ self new: anInteger x: anInteger to: anotherInteger! !

!MonomialLiteral class methodsFor: 'related classes' stamp: 'len 11/22/97 19:58'!
monomialClass
	^ Monomial! !

!MonomialLiteral class methodsFor: 'constants' stamp: 'len 12/26/97 17:57'!
defaultNames
	"Answer the default names for the indeterminates."

	| names last |
	last _ 0.
	MonomialLiteral allSubInstancesDo: [ :each | last _ last max: each size].
	last <= 3 ifTrue: [^ Dictionary with: 1 -> #x with: 2 -> #y with: 3 -> #z].
	names _ Dictionary new.
	1 to: last do: [ :each | names add: each -> ('{x', each printString, '}')].
	^ names! !


!MonomialOrdering commentStamp: '<historical>' prior: 0!
My instances are orderings for the monomial literals.

For literals in n variables, there are n!! (n factorial) orderings, and in certain aplications, such Groebner bases, it's desirable to easily construct new monomial orderings.

Each MonomialOrdering fix the ordering of the variables mantaining an ordered collection with them. Furthermore, each MonomialOrdering posseses a list of "weights", which are n-tuples (if there are n variables), and these "weights" fix the ordering of all the literals.

Let's take a look at the way "weights" work. Suppose you have two literals:
	a = x1^a1 x2^a2 ... xn^an
	b = x1^b1 x2^b2 ... xn^bn
where some of the ai or bi may be 0. And suppose the variables are ordered x1 < x2 < ... < xn. If we are asked for the truth of a < b, we enumerate the weights and for each one, (w1, w2, ..., wn) we do:
	asum = a1 w1 + a2 w2 + ... + an wn,
	bsum = b1 w1 + b2 w2 + ... + bn wn;
if asum < bsum, then a < b; if asum > bsum, then a > b; if asum = bsum, we continue with the next weight, until there are no more weights (then, a should equal b...).

There is a theorem claiming that for any monomial ordering in a finite number of variables, there are a collection of weights which models that ordering. So, with this scheme we are able to contruct any ordering.

If looking for examples, see the class method category named 'examples'.
!

!MonomialOrdering methodsFor: 'accessing-private' stamp: 'len 2/2/98 01:23'!
indeterminates: aCollection
	indeterminates _ aCollection! !

!MonomialOrdering methodsFor: 'accessing-private' stamp: 'len 2/5/98 01:14'!
weighs: aCollectionOfTuples
	weighs _ aCollectionOfTuples! !

!MonomialOrdering methodsFor: 'accessing' stamp: 'len 2/3/98 00:54'!
headOf: aPolynomial
	"Answer the head of the argument."

	| answer |
	aPolynomial do: [ :each |
		answer _ (answer isNil or: [self is: each literal gneq: answer literal])
			ifTrue: [each] ifFalse: [answer]].
	^ answer! !

!MonomialOrdering methodsFor: 'accessing' stamp: 'len 2/2/98 01:23'!
indeterminates
	"Answer the indeterminates of the receiver."
	^ indeterminates! !

!MonomialOrdering methodsFor: 'accessing' stamp: 'len 2/18/98 18:56'!
is: aLiteral gneq: bLiteral
	"Answer true if the first argument is greater than the second."

	| left right a b |
	left _ Tuple
		dimension: self indeterminates size
		fromBlock: [ :each | aLiteral at: (self indeterminates at: each)].
	right _ Tuple
		dimension: self indeterminates size
		fromBlock: [ :each | bLiteral at: (self indeterminates at: each)].
	self weighs do: [ :each |
		(a _ each scalar: left) > (b _ each scalar: right) ifTrue: [^ true].
		a < b ifTrue: [^ false]].
	^ false! !

!MonomialOrdering methodsFor: 'accessing' stamp: 'len 2/2/98 02:18'!
weighs
	"Answer the weighs of the receiver."
	^ weighs! !

!MonomialOrdering methodsFor: 'arithmetic' stamp: 'len 2/5/98 01:15'!
* aMonomialOrdering
	"Answer the product of the recever by the argument."

	| newWeighs null |
	newWeighs _ OrderedCollection new.
	null _ aMonomialOrdering weighs first null.
	self weighs do: [ :each | newWeighs add: each, null].
	null _ self weighs first null.
	aMonomialOrdering weighs do: [ :each | newWeighs add: null, each].
	^ self class
		indeterminates: self indeterminates, aMonomialOrdering indeterminates
		weighs: newWeighs! !

!MonomialOrdering methodsFor: 'arithmetic' stamp: 'len 2/5/98 01:18'!
, aMonomialOrdering
	"Answer the concatenation of the recever and the argument."

	self indeterminates = aMonomialOrdering indeterminates ifFalse: [^ self halt].
	^ self class
		indeterminates: self indeterminates
		weighs: (self weighs copy addAll: aMonomialOrdering weighs)! !

!MonomialOrdering methodsFor: 'arithmetic' stamp: 'len 2/3/98 02:09'!
inverse
	"Answer the inverse of the receiver."

	^ self class
		indeterminates: self indeterminates reversed
		weighs: self weighs! !

!MonomialOrdering methodsFor: 'arithmetic' stamp: 'len 2/3/98 02:09'!
reverse
	"Answer the reverse of the receiver."

	^ self class
		indeterminates: self indeterminates
		weighs: (self weighs collect: [ :each | each negated])! !

!MonomialOrdering methodsFor: 'printing' stamp: 'len 2/3/98 01:27'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	aStream nextPutAll: self class name; space.
	self indeterminates do: [ :each |
		aStream nextPutAll: ' {x', each printString, '} '].
	self weighs do: [ :each | aStream print: each; space]! !


!MonomialOrdering class methodsFor: 'instance creation' stamp: 'len 2/5/98 01:13'!
indeterminates: aCollection weighs: aCollectionOfTuples
	"Answer a new instance of the receiver with the
	indeterminates and weighs given by the arguments."

	^ self new indeterminates: aCollection; weighs: aCollectionOfTuples! !

!MonomialOrdering class methodsFor: 'examples' stamp: 'len 2/3/98 01:39'!
lex: aCollection
	"Answer the lexicographic order with
	the indeterminates of aCollection."

	| weighs n |
	n _ aCollection size.
	weighs _ (1 to: n) collect: [ :each | (Tuple null: n) at: each put: 1; yourself].
	^ self indeterminates: aCollection weighs: weighs! !

!MonomialOrdering class methodsFor: 'examples' stamp: 'len 2/3/98 01:38'!
revlex: aCollection
	"Answer the reverse lexicographic ordering
	with the indeterminates of aCollection."

	^ (self lex: aCollection) reverse! !

!MonomialOrdering class methodsFor: 'examples' stamp: 'len 2/3/98 02:16'!
tlex: aCollection
	"Answer the total (or graded) lexicographic ordering
	with the indeterminates of aCollection."

	| weighs |
	weighs _ OrderedCollection new.
	weighs add: (Tuple dimension: aCollection size fromBlock: [ :each | 1]).
	weighs addAll: (self lex: aCollection) weighs.
	^ self indeterminates: aCollection weighs: weighs! !

!MonomialOrdering class methodsFor: 'examples' stamp: 'len 2/3/98 02:17'!
trevlex: aCollection
	"Answer the total (or graded) reverse lexicographic
	ordering with the indeterminates of aCollection."

	| weighs |
	weighs _ OrderedCollection new.
	weighs add: (Tuple dimension: aCollection size fromBlock: [ :each | 1]).
	weighs addAll: (self revlex: aCollection) weighs.
	^ self indeterminates: aCollection weighs: weighs! !


!MultiPolynomialDivisor methodsFor: 'initialization' stamp: 'len 1/24/98 11:58'!
divide: aPolynomial by: aTupleOfPolynomials
	self dividend: aPolynomial.
	self divisors: aTupleOfPolynomials.
	self done: false! !

!MultiPolynomialDivisor methodsFor: 'accessing-private' stamp: 'len 1/24/98 11:59'!
done: aBoolean
	done _ aBoolean! !

!MultiPolynomialDivisor methodsFor: 'accessing-private' stamp: 'len 1/24/98 12:00'!
quotients: aTupleOfPolynomials
	quotients _ aTupleOfPolynomials! !

!MultiPolynomialDivisor methodsFor: 'accessing-private' stamp: 'len 1/24/98 12:00'!
remainder: aPolynomial
	remainder _ aPolynomial
	! !

!MultiPolynomialDivisor methodsFor: 'accessing' stamp: 'len 1/24/98 12:04'!
dividend
	"Answer the dividend of the receiver."

	^ dividend! !

!MultiPolynomialDivisor methodsFor: 'accessing' stamp: 'len 1/24/98 12:04'!
dividend: aPolynomial
	dividend _ aPolynomial.
	self done: false! !

!MultiPolynomialDivisor methodsFor: 'accessing' stamp: 'len 1/24/98 12:04'!
divisors
	"Answer the divisors of the receiver."

	^ divisors! !

!MultiPolynomialDivisor methodsFor: 'accessing' stamp: 'len 1/24/98 12:04'!
divisors: aTupleOfPolynomials
	divisors _ aTupleOfPolynomials.
	self done: false! !

!MultiPolynomialDivisor methodsFor: 'accessing' stamp: 'len 1/24/98 11:59'!
done
	"Answer true if the quotient and the remainder have been computed."

	^ done! !

!MultiPolynomialDivisor methodsFor: 'accessing' stamp: 'len 2/5/98 01:06'!
ordering
	"Answer the monomial ordering used by the receiver."

	^ ordering! !

!MultiPolynomialDivisor methodsFor: 'accessing' stamp: 'len 2/5/98 01:06'!
ordering: aMonomialOrdering
	"Change the monomial ordering used by the receiver."

	ordering _ aMonomialOrdering! !

!MultiPolynomialDivisor methodsFor: 'accessing' stamp: 'len 1/24/98 12:05'!
quotients
	"Answer the quotients of the receiver."

	self divide.
	^ quotients! !

!MultiPolynomialDivisor methodsFor: 'accessing' stamp: 'len 1/24/98 12:05'!
remainder
	"Answer the remainder of the receiver."

	self divide.
	^ remainder! !

!MultiPolynomialDivisor methodsFor: 'operations' stamp: 'len 4/20/98 20:29'!
divide
	"Perform the division algorithm computing quotients and remainder."

	| p s quots rem null index fi q headp headfi |
	self done ifTrue: [^ self].
	null _ self dividend null.
	quots _ (1 to: self divisors size) collect: [ :each | null].
	rem _ null.
	s _ self divisors size.
	p _ self dividend.
	[p isNull] whileFalse: [
		headp _ self ordering headOf: p.
		index _ (1 to: s)
			detect: [ :one |
				(headfi _ self ordering headOf: (fi _ self divisors at: one)) literal
					divides: headp literal]
			ifNone: [].
		index isNil
			ifTrue: [rem _ rem + headp.
					p _ p - headp]
			ifFalse: [quots at: index put: (quots at: index) + (q _ headp / headfi).
					p _ p - (fi * q)]].
	self quotients: quots; remainder: rem; done: true! !

!MultiPolynomialDivisor methodsFor: 'printing' stamp: 'len 1/24/98 12:49'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	aStream print: self dividend; nextPutAll: ' = '.
	(1 to: self divisors size) do: [ :each |
		aStream
			nextPut: $(; print: (self quotients at: each); nextPut: $);
			nextPut: $(; print: (self divisors at: each); nextPut: $);
			nextPutAll: ' + '].
	aStream print: self remainder! !


!MultiPolynomialDivisor class methodsFor: 'instance creation' stamp: 'len 2/5/98 01:05'!
divide: aPolynomial by: aTupleOfPolynomials
	"Answer a multivariate division algorithm to
	divide aPolynomial by aTupleOfPolynomials."

	| indets |
	indets _ aPolynomial indeterminates.
	aTupleOfPolynomials do: [ :each | indets addAll: each indeterminates].
	^ self divide: aPolynomial by: aTupleOfPolynomials
		ordering: (MonomialOrdering tlex: indets asSortedCollection)! !

!MultiPolynomialDivisor class methodsFor: 'instance creation' stamp: 'len 2/5/98 01:04'!
divide: aPolynomial by: aTupleOfPolynomials ordering: aMonomialOrdering
	"Answer a multivariate division algorithm to divide aPolynomial
	by aTupleOfPolynomials using the ordering aMonomialOrdering."

	^ self new
		ordering: aMonomialOrdering;
		divide: aPolynomial by: aTupleOfPolynomials! !


!Number methodsFor: 'arithmetic' stamp: 'len 2/18/98 18:58'!
conjugated
	"Answer the complex conjugation of the receiver."

	^ self! !

!Number methodsFor: 'mathematical functions' stamp: 'len 1/5/98 20:49'!
norm
	"Answer the norm of the receiver."

	^ self abs! !

!Number methodsFor: 'mathematical functions' stamp: 'len 1/5/98 20:49'!
norm2
	"Answer the squared norm of the receiver."

	^ self squared! !

!Number methodsFor: 'testing' stamp: 'len 1/20/98 01:46'!
isNull
	"Answer true if the receiver is null."
	^ self = 0! !

!Number methodsFor: 'testing'!
isRational
	"Answer true if the receiver is a rational number, i.e. a Fraction or an Integer."
	^ false! !

!Number methodsFor: 'converting' stamp: 'len 11/28/97 02:05'!
, anObject
	"Answer the 2 dim Tuple with the receiver in the
	first coordinate and the argument in the second."

	^ Tuple with: self with: anObject! !

!Number methodsFor: 'converting' stamp: 'len 1/20/98 01:45'!
adaptComplex: aComplex
	"If I am involved in arithmetic with a Complex, do not convert it."
	^ aComplex! !

!Number methodsFor: 'converting' stamp: 'len 2/25/98 03:22'!
adaptQuaternion: aQuaternion
	"If I am involved in arithmetic with a Quaternion, do not convert it."
	^ aQuaternion! !

!Number methodsFor: 'converting' stamp: 'len 12/13/97 05:20'!
asPolynomial
	"Answer a constant polynomial from the receiver."

	^ Polynomial constant: self! !

!Number methodsFor: 'constants' stamp: 'len 1/20/98 01:45'!
identity
	"Answer the identity element."
	^ 1! !

!Number methodsFor: 'constants' stamp: 'len 1/20/98 01:46'!
null
	"Answer the null element."
	^ 0! !


!AlgebraicNumber methodsFor: 'initialization' stamp: 'len 11/18/97 01:33'!
polynomial: aPolynomial irreducible: aBoolean leftBound: left rightBound: right
	self polynomial: aPolynomial.
	self irreducible: aBoolean.
	self leftBound: left.
	self rightBound: right.
"	self irreducible
		ifTrue: [self polynomial: aPolynomial]
		ifFalse: [
			self polynomial:
				(aPolynomial squareFreeFactorizationOLD asSet
					detect: [ :one | (one valueAt: left) sign ~= (one valueAt: right)])]."
	self normalize! !

!AlgebraicNumber methodsFor: 'accessing-private' stamp: 'len 8/4/97 19:28'!
irreducible: aBoolean
	irreducible _ aBoolean! !

!AlgebraicNumber methodsFor: 'accessing-private' stamp: 'len 8/4/97 19:28'!
leftBound: aFraction
	leftBound _ aFraction! !

!AlgebraicNumber methodsFor: 'accessing-private' stamp: 'len 11/17/97 22:47'!
polynomial: aPolynomial
	polynomial _ aPolynomial! !

!AlgebraicNumber methodsFor: 'accessing-private' stamp: 'len 11/18/97 03:54'!
rightBound: aFraction
	rightBound _ aFraction.
	rightValue _ nil! !

!AlgebraicNumber methodsFor: 'accessing-private' stamp: 'len 11/18/97 01:07'!
rightValue
	rightValue isNil ifTrue: [rightValue _ self polynomial valueAt: self rightBound].
	^ rightValue! !

!AlgebraicNumber methodsFor: 'accessing-private' stamp: 'len 11/18/97 00:05'!
rightValue: aFraction
	rightValue _ aFraction! !

!AlgebraicNumber methodsFor: 'accessing' stamp: 'len 8/4/97 19:28'!
index
	"Answer the index of the receiver as zero of its minimal polynomial."

	self notYetImplemented! !

!AlgebraicNumber methodsFor: 'accessing' stamp: 'len 8/18/97 18:58'!
irreducible
	"Answer true if the polynomial of the receiver
	is in fact the minimal, i.e. if it's irreducible."

	^ irreducible! !

!AlgebraicNumber methodsFor: 'accessing' stamp: 'len 8/4/97 19:28'!
leftBound
	"Answer the current left rational bound of the receiver."

	^ leftBound! !

!AlgebraicNumber methodsFor: 'accessing' stamp: 'len 11/17/97 22:49'!
polynomial
	"Answer the polynomial that defines the receiver."

	^ polynomial! !

!AlgebraicNumber methodsFor: 'accessing' stamp: 'len 8/4/97 19:28'!
rightBound
	"Answer the current right rational bound of the receiver."

	^ rightBound! !

!AlgebraicNumber methodsFor: 'arithmetic' stamp: 'len 1/30/98 01:03'!
* aNumber
	"Answer the product of the receiver by aNumber."

	| f ll lr rl rr left right |

	aNumber isAlgebraic
		ifFalse: [^ (aNumber adaptAlgebraic: self) * aNumber adaptToAlgebraic].

	aNumber isNull ifTrue: [^ aNumber].
	f _ self class rootFinderClass polynomial:
		(self polynomial zeroProduct: aNumber polynomial).
	ll _ self leftBound * aNumber leftBound.
	rr _ self rightBound * aNumber rightBound.
	lr _ self leftBound * aNumber rightBound.
	rl _ self rightBound * aNumber leftBound.
	left _ ((ll min: rr) min: lr) min: rl.
	right _ ((ll max: rr) max: lr) max: rl.
	[f moreThanOneRootBetween: left and: right] whileTrue: [
		self refine. aNumber refine.
		ll _ self leftBound * aNumber leftBound.
		rr _ self rightBound * aNumber rightBound.
		lr _ self leftBound * aNumber rightBound.
		rl _ self rightBound * aNumber leftBound.
		left _ ((ll min: rr) min: lr) min: rl.
		right _ ((ll max: rr) max: lr) max: rl].
	^ self class polynomial: f polynomial leftBound: left rightBound: right! !

!AlgebraicNumber methodsFor: 'arithmetic' stamp: 'len 1/30/98 01:03'!
+ aNumber
	"Answer the sum of the receiver with aNumber."

	| f left right |
	aNumber isAlgebraic
		ifFalse: [^ (aNumber adaptAlgebraic: self) + (aNumber adaptToAlgebraic)].
	f _ self class rootFinderClass polynomial:
		(self polynomial zeroAddition: aNumber polynomial).
	left _ self leftBound + aNumber leftBound.
	right _ self rightBound + aNumber rightBound.
	[f moreThanOneRootBetween: left and: right] whileTrue: [
		self refine.
		aNumber refine.
		left _ self leftBound + aNumber leftBound.
		right _ self rightBound + aNumber rightBound].
	^ self class polynomial: f polynomial leftBound: left rightBound: right! !

!AlgebraicNumber methodsFor: 'arithmetic' stamp: 'len 8/28/97 01:42'!
- anObject
	"Answer the difference between the receiver and the argument."

	^ self + anObject negated! !

!AlgebraicNumber methodsFor: 'arithmetic' stamp: 'len 8/28/97 01:42'!
/ anObject
	"Answer the division of the receiver by the argument."

	^ self * anObject reciprocal! !

!AlgebraicNumber methodsFor: 'arithmetic' stamp: 'len 8/5/97 00:25'!
negated
	"Answer the additive inverse of the receiver."

	^ self class
		polynomial: self polynomial zeroNegation
		irreducible: self irreducible
		leftBound: self rightBound negated
		rightBound: self leftBound negated! !

!AlgebraicNumber methodsFor: 'arithmetic' stamp: 'len 8/5/97 00:25'!
reciprocal
	"Answer the multiplicative inverse of the receiver."

	self isNull ifTrue: [^ self error: 'division by zero'].
	^ self class
		polynomial: self polynomial zeroReciprocal
		irreducible: self irreducible
		leftBound: self rightBound reciprocal
		rightBound: self leftBound reciprocal! !

!AlgebraicNumber methodsFor: 'mathematical functions' stamp: 'len 8/8/97 20:54'!
sign
	"Answer 1, -1 or 0, depending on the sign of the receiver."

	^ self leftBound sign! !

!AlgebraicNumber methodsFor: 'mathematical functions' stamp: 'len 8/4/97 20:39'!
sqrt
	"Answer the square root of the receiver."

	self notYetImplemented! !

!AlgebraicNumber methodsFor: 'mathematical functions' stamp: 'len 11/6/97 19:43'!
squared
	"Answer the square of the receiver."

	| x odd even |
	x _ self polynomial x.
	odd _ self polynomial odd.
	even _ self polynomial even.
	^ self class
		polynomial: odd squared * x - even squared
		leftBound: self leftBound squared
		rightBound: self rightBound squared! !

!AlgebraicNumber methodsFor: 'truncation and round off' stamp: 'len 12/17/97 20:53'!
truncated
	"Answer the integer nearest the receiver toward zero."

	| trunc |
	(self rightBound - self leftBound) truncated > 0 ifTrue: [self refineToError: 9/10].
	^ (trunc _ self rightBound truncated) = self rightBound
		ifTrue: [self refineAt: trunc.
				self rightBound truncated]
		ifFalse: [trunc]! !

!AlgebraicNumber methodsFor: 'refining' stamp: 'len 12/17/97 20:32'!
bisectionRefine
	"Refine the rational interval approximation of the receiver using the bisection rule."

	self refineAt: self leftBound + self rightBound / 2! !

!AlgebraicNumber methodsFor: 'refining' stamp: 'len 8/4/97 20:41'!
error
	"Answer the maximun current error in the
	rational approximation of the receiver."

	^ self rightBound - self leftBound! !

!AlgebraicNumber methodsFor: 'refining' stamp: 'len 11/17/97 23:03'!
refine
	"Refine the rational interval approximation of the receiver."

	self bisectionRefine! !

!AlgebraicNumber methodsFor: 'refining' stamp: 'len 12/17/97 20:45'!
refineAt: aFraction
	"Refine the rational interval approximation of the receiver
	to one of both (leftBound, aFraction] or (aFraction, rightBound]."

	| value |
	self rightValue sign = (value _ self polynomial valueAt: aFraction) sign
		ifTrue: [self rightBound: aFraction; rightValue: value]
		ifFalse: [self leftBound: aFraction].
	value = 0 ifTrue: [self leftBound: aFraction. self rightBound: aFraction]! !

!AlgebraicNumber methodsFor: 'refining' stamp: 'len 8/5/97 00:17'!
refineToError: aNumber
	"Refine the receiver up to get an approximation error < aNumber."

	[self error >= aNumber] whileTrue: [self refine]! !

!AlgebraicNumber methodsFor: 'refining' stamp: 'len 8/4/97 19:34'!
refined
	"Answer a copy of the receiver refined."

	^ self copy refine! !

!AlgebraicNumber methodsFor: 'converting' stamp: 'len 12/13/97 03:12'!
adaptFloat: aFloat
	"If I am involved in arithmetic with a Float, do not convert the Float."
	^ aFloat! !

!AlgebraicNumber methodsFor: 'converting' stamp: 'len 9/15/97 00:01'!
adaptFraction: aFraction
	"If I am involved in arithmetic with a Fraction, convert the Fraction."
	^ self class fromRational: aFraction! !

!AlgebraicNumber methodsFor: 'converting' stamp: 'len 9/15/97 00:00'!
adaptInteger: anInteger
	"If I am involved in arithmetic with an Integer, convert the Integer."
	^ self class fromRational: anInteger! !

!AlgebraicNumber methodsFor: 'converting' stamp: 'len 8/4/97 22:37'!
adaptToFloat
	"If I am involved in arithmetic with a Float, convert me to Float."
	^ self asFloat! !

!AlgebraicNumber methodsFor: 'converting' stamp: 'len 8/4/97 22:28'!
adaptToFraction
	"If I am involved in arithmetic with a Fraction, do not convert me."
	^ self! !

!AlgebraicNumber methodsFor: 'converting' stamp: 'len 8/4/97 22:36'!
adaptToInteger
	"If I am involved in arithmetic with an Integer, do not convert me."
	^ self! !

!AlgebraicNumber methodsFor: 'converting' stamp: 'len 11/18/97 01:05'!
asFloat
	"Answer a Float approximation of the receiver."

	self refineToError: 0.000001.
	^ (self leftBound + self rightBound / 2) asFloat! !

!AlgebraicNumber methodsFor: 'converting' stamp: 'len 2/6/98 21:50'!
asRational
	"Convert the receiver to Fraction or Integer."

	| alpha |
	self leftBound = self rightBound ifTrue: [^ self leftBound].
	self polynomial degree < 2
		ifTrue: [alpha _ self polynomial independentCoefficient
						/ self polynomial leadingCoefficient.
				self rightBound: alpha. self leftBound: alpha. ^ alpha].
	(RationalPolynomialRootFinder polynomial: self polynomial)
		roots do: [ :each | (each between: self leftBound and: self rightBound)
						ifTrue: [self rightBound: each. self leftBound: each. ^ each]].
	self error: 'cannot convert to rational'! !

!AlgebraicNumber methodsFor: 'comparing' stamp: 'len 12/17/97 20:21'!
< anObject
	"Answer whether the receiver is less than the argument."

	anObject isAlgebraic ifFalse: [^ (self - anObject) sign = -1].
	(self = anObject) ifTrue: [^ false].
	[self overlaps: anObject] whileTrue: [self refine. anObject refine].
	^ self rightBound < anObject leftBound! !

!AlgebraicNumber methodsFor: 'comparing' stamp: 'len 2/25/98 22:18'!
= anObject
	"Answer true if the receiver equals the argument."

	anObject isNumber ifFalse: [^ false].
	self == anObject ifTrue: [^ true].
	anObject isAlgebraic
		ifFalse: [^ (anObject adaptAlgebraic: self) = anObject adaptToAlgebraic].
	(self overlaps: anObject) ifFalse: [^ false].
	(self polynomial gcd: anObject polynomial) isConstant
		ifTrue: [^ false].
	^ (self - anObject) isNull! !

!AlgebraicNumber methodsFor: 'comparing' stamp: 'len 12/13/97 03:56'!
hash
	"Answer the hash value for the receiver."

	^ self truncated hash! !

!AlgebraicNumber methodsFor: 'testing' stamp: 'len 8/4/97 19:28'!
isAlgebraic
	"Answer true if the receiver is an AlgebraicNumber."

	^ true! !

!AlgebraicNumber methodsFor: 'testing' stamp: 'len 8/4/97 22:00'!
isNull
	"Answer true if the receiver is null."

	^ self leftBound = 0 and: [self rightBound = 0]! !

!AlgebraicNumber methodsFor: 'testing' stamp: 'len 2/6/98 21:50'!
isRational
	"Answer true if the receiver is a rational number."

	self polynomial degree < 2 ifTrue: [^ true].
	self rightBound = self leftBound ifTrue: [^ true].
	(RationalPolynomialRootFinder polynomial: self polynomial)
		roots do: [ :each | (each between: self leftBound and: self rightBound)
						ifTrue: [self rightBound: each. self leftBound: each. ^ true]].
	^ false! !

!AlgebraicNumber methodsFor: 'testing' stamp: 'len 12/19/97 02:26'!
overlaps: anAlgebraic
	"Answer true if the bounds of the receiver overlaps the bounds of the argument."

	^ (self leftBound max: anAlgebraic leftBound)
		<= (self rightBound min: anAlgebraic rightBound)! !

!AlgebraicNumber methodsFor: 'private' stamp: 'len 11/18/97 03:54'!
normalize
	"Change the representation of the receiver to a new one
	such that 0 is not in the rational approximation interval
	if the receiver is not null."

	| p value |
	self leftBound sign = self rightBound sign ifTrue: [^ self].
	p _ 1 / (1 + self polynomial normInfinite).
	value _ self polynomial valueAt: p negated.
	value sign ~= (self polynomial valueAt: self leftBound) sign
		ifTrue: [self rightBound: p negated; rightValue: value]
		ifFalse: [(self polynomial valueAt: p) sign ~= self rightValue sign
				ifTrue: [self leftBound: p]
				ifFalse: [self leftBound: 0; rightBound: 0]]! !

!AlgebraicNumber methodsFor: 'printing' stamp: 'len 11/7/97 06:06'!
printOn: aStream
	"Print a representation of the receiver in the stream aStream."

	aStream print: (self asFloat roundTo: 0.00001); nextPutAll: '..'

	"aStream
		nextPutAll: self class name;
		space;
		nextPut: $(;
		print: self polynomial;
		nextPutAll: '; ~ ';
		print: self asFloat;
		nextPut: $)"! !


!Float methodsFor: 'converting' stamp: 'len 12/13/97 03:13'!
adaptAlgebraic: anAlgebraicNumber
	"If I am involved in arithmetic with an AlgebraicNumber,
	convert the AlgebraicNumber."

	^ anAlgebraicNumber asFloat! !

!Float methodsFor: 'converting' stamp: 'len 12/13/97 03:13'!
adaptToAlgebraic
	"If I am involved in arithmetic with an AlgebraicNumber, do not convert me."

	^ self! !


!Fraction methodsFor: 'converting' stamp: 'len 1/20/98 01:44'!
adaptAlgebraic: anAlgebraicNumber
	"If I am involved in arithmetic with an AlgebraicNumber,
	do not convert the AlgebraicNumber."
	^ anAlgebraicNumber! !

!Fraction methodsFor: 'converting' stamp: 'len 1/20/98 01:44'!
adaptToAlgebraic
	"If I am involved in arithmetic with an AlgebraicNumber,
	convert me to an AlgebraicNumber."
	^ self asAlgebraic! !


!Integer methodsFor: 'testing' stamp: 'len 8/30/97 03:13'!
isPrime
	"Answer true if the receiver is a positive prime number."
	#AddedByLEN.

	"Easy cases:"
	self <= 1 ifTrue: [^ false].
	self even ifTrue: [^ self = 2].
	"(#(3 5 7 11 13 17 19 23 29 31 37) includes: self) ifTrue: [^ true]."

	3 to: ((1 bitShift: self highBit // 2 + 1) min: self - 1) by: 2 do:
		[:each | self \\ each = 0 ifTrue: [^ false]].
	^ true! !

!Integer methodsFor: 'testing' stamp: 'len 8/28/97 20:51'!
isPrimeMillerRabin: anInteger
	"Answer true if the receiver is prime with probability of error
	less than '(1/4)^anInteger', or false if the receiver is composite.
	Uses the Miller-Rabin test."

	| samples b k minusOne n0 t satisfied x |
	(self negative or: [self even]) ifTrue: [^ false].
	minusOne _ self - 1.
	samples _ 1 to: minusOne.
	k _ minusOne lowBit - 1.
	n0 _ self - 1 bitShift: k negated.
	anInteger timesRepeat: [
		b _ samples atRandom.
		(self gcd: b) = 1 ifFalse: [^ false].
		t _ 0.
		x _ b raisedToInteger: n0 mod: self.
		(x = 1 or: [x = minusOne]) ifFalse: [
			[x _ x squared \\ self.
			t _ t + 1.
			satisfied _ x = minusOne.
			satisfied not and: [t < k]] whileTrue.
			satisfied ifFalse: [^ false]]].
	^ true! !

!Integer methodsFor: 'testing' stamp: 'len 8/20/97 02:25'!
isPrimeSolovayStrassen: anInteger
	"Answer true if the receiver is prime with probability less
	than '(1/2)^anInteger', or false if the receiver is composite.
	Uses the Solovay-Strassen test."

	| samples b minusOne power |
	(self negative or: [self even]) ifTrue: [^ false].
	minusOne _ self - 1.
	samples _ 1 to: minusOne.
	power _ minusOne bitShift: -1.
	anInteger timesRepeat: [
		b _ samples atRandom.
		(self gcd: b) = 1 ifFalse: [^ false].
		(b raisedToInteger: power mod: self) = ((b jacobi: self) \\ self)
			ifFalse: [^ false halt]
	].
	^ true! !

!Integer methodsFor: 'testing'!
isRational
	"Answer true if the receiver is a rational number, i.e. a Fraction or an Integer."
	^ true! !

!Integer methodsFor: 'mathematical functions' stamp: 'len 7/16/97 02:13'!
descendentPower: n
	"Answer the descendent power of the receiver raised to the argument."
	| mid |
	n = 0 ifTrue: [^ 1].
	n = 1 ifTrue: [^ self].
	n negative ifTrue: [^ (self descendentPower: n negated) reciprocal].
	mid _ n bitShift: -1.
	^ n even ifTrue: [
		(self - mid descendentPower: mid) * (self descendentPower: mid)
	] ifFalse: [
		(self - mid descendentPower: mid + 1) * (self descendentPower: mid)
	]! !

!Integer methodsFor: 'mathematical functions' stamp: 'len 7/14/97 01:19'!
divisors
	"Answer the collection of positive divisors of the receiver."

	| answer |
	#AddedByLEN.
	self negative ifTrue: [^ self abs divisors].
	answer _ Set new.
	1 to: (self bitShift: -2) + 1 do: [ :each |
		self \\ each = 0 ifTrue: [answer add: each; add: self // each]
	].
	^ answer! !

!Integer methodsFor: 'mathematical functions' stamp: 'len 10/2/97 01:36'!
divisorsDo: aBlock
	"Enumerate the positive divisors of the receiver."

	#AddedByLEN.
	self divisors do: aBlock! !

!Integer methodsFor: 'mathematical functions'!
factorial
	"Answer the factorial of the receiver.
	Create an error notification if the receiver is negative."

	self = 0 ifTrue: [^1].
	self < 0
		ifTrue: [self error: 'factorial invalid for: ' , self printString]
		ifFalse: [^ self descendentPower: self - 1]! !

!Integer methodsFor: 'mathematical functions' stamp: 'len 10/10/97 01:16'!
factors
	"Answer a collection with the prime factors of the receiver."

	| n p answer times |
	#AddedByLEN.
	n _ self abs.
	n <= 1 ifTrue: [^ Bag new].
	answer _ Bag new.
	n even ifTrue: [
		answer add: 2 withOccurrences: (times _ n lowBit - 1).
		n _ n bitShift: times negated].

	p _ 3.
	[p <= n] whileTrue: [
		p isPrime ifTrue: [
			times _ 0.
			[n \\ p = 0] whileTrue: [times _ times + 1. n _ n // p].
			times > 0 ifTrue: [answer add: p withOccurrences: times]].
		p _ p + 2].

	^ answer! !

!Integer methodsFor: 'mathematical functions' stamp: 'len 11/24/97 20:45'!
factors2
	"Answer a collection with the prime factors of the receiver."

	| n p answer times |

	n _ self abs.
	n <= 1 ifTrue: [^ Bag new].
	answer _ Bag new.
	n even ifTrue: [
		answer add: 2 withOccurrences: (times _ n lowBit - 1).
		n _ n bitShift: times negated].

	p _ 3.
	[p <= (n // p)] whileTrue: [
		p isPrime ifTrue: [
			times _ 0.
			[n \\ p = 0] whileTrue: [times _ times + 1. n _ n // p].
			times > 0 ifTrue: [answer add: p withOccurrences: times]].
		p _ p + 2].
	(p = n or: [n = 1]) ifFalse: [answer add: n].
	^ answer! !

!Integer methodsFor: 'mathematical functions' stamp: 'len 11/24/97 20:46'!
fibonacci
	| fn fn1 fi fi1 n ftemp |
	fn _ 1. fn1 _ 0. fi _ 0. fi1 _ 1. n _ self.
	[n = 0] whileFalse: [
		n odd ifTrue: [
			ftemp _ (fi * fn) + (fi1 * fn1).
			fi _ (fi + fi1) * fn + (fn * fi).
			fi1 _ ftemp].
		(n _ n >> 1) = 0 ifFalse: [
			ftemp _ fn squared.
			fn _ ftemp + (2 * fn * fn1).
			fn1 _ ftemp + fn1 squared]].
	^ Array with: fn with: fn1 with: fi with: fi1! !

!Integer methodsFor: 'mathematical functions' stamp: 'len 8/20/97 02:25'!
jacobi: m
	"Answer the Jacobi symbol of the receiver and the argument."

	| x y z answer |
	m odd ifFalse: [^ self error: 'the argument must by an odd positive integer'].
	(self gcd: m) = 1 ifFalse: [^ 0].
	x _ self \\ m.
	y _ m.
	answer _ 1.
	[x > 1] whileTrue: [
		[x \\ 4 = 0] whileTrue: [x _ x // 4].
		x \\ 2 = 0 ifTrue: [
			x _ x // 2.
			y + 2 \\ 8 > 4 ifTrue: [answer _ answer negated]
		].
		z _ y \\ x.
		y _ x.
		x _ z
	].
	^ answer! !

!Integer methodsFor: 'mathematical functions' stamp: 'len 8/20/97 02:26'!
jacobiOld: n
	"Answer the Jacoby symbol of the receiver and the argument."

	| a minusOne |
"	n odd ifFalse: [^ self error: 'the argument must by an odd positive integer']."
	a _ self \\ n.
	a = 2 ifTrue: [^ (n squared - 1) lowBit > 3 ifTrue: [1] ifFalse: [-1]].
	minusOne _ n - 1.
	a = minusOne ifTrue: [^ minusOne lowBit > 1 ifTrue: [1] ifFalse: [-1]].
	^ (a - 1 * minusOne) lowBit > 2
		ifTrue: [n jacobiOld: a] ifFalse: [(n jacobiOld: a) negated]! !

!Integer methodsFor: 'mathematical functions' stamp: 'len 9/17/97 02:05'!
pollard
	"Answer a non trivial factor of the receiver.
	The Pollard method is used."

	| interval a x y p count |

	interval _ 1 to: self abs.
	a _ interval atRandom.
	x _ interval atRandom.
	y _ x.
	count _ 1.
	[x _ x squared + a \\ self.
	y _ (y squared + a \\ self) squared + a \\ self.
	(p _ y - x gcd: self) = 1
		ifFalse: [^ Array with: p with: count].
	count _ count + 1. true] whileTrue.! !

!Integer methodsFor: 'mathematical functions' stamp: 'len 8/20/97 00:56'!
raisedToInteger: anInteger mod: otherInteger
	"Answer the receiver raised to the power anInteger modulo otherInteger.
	Both anInteger and otherInteger must be positive."

	anInteger = 0 ifTrue: [^ 1].
	anInteger = 1 ifTrue: [^ self \\ otherInteger].
	^ (self squared \\ otherInteger
		raisedToInteger: anInteger // 2 mod: otherInteger) *
	(self raisedToInteger: anInteger \\ 2 mod: otherInteger) \\ otherInteger! !

!Integer methodsFor: 'bit manipulation' stamp: 'len 8/19/97 21:58'!
lowBit
	"Answer the index of the low order bit of this number."

	| index |
	self = 0 ifTrue: [^ 0].
	index _ 1.
	[(self digitAt: index) = 0]
		whileTrue: [index _ index + 1].
	^ (self digitAt: index) lowBit + (8 * (index - 1))! !

!Integer methodsFor: 'converting' stamp: 'len 1/20/98 01:44'!
adaptAlgebraic: anAlgebraicNumber
	"If I am involved in arithmetic with an AlgebraicNumber,
	do not convert the AlgebraicNumber."
	^ anAlgebraicNumber! !

!Integer methodsFor: 'converting' stamp: 'len 1/20/98 01:44'!
adaptToAlgebraic
	"If I am involved in arithmetic with an AlgebraicNumber,
	convert me to an AlgebraicNumber."
	^ self asAlgebraic! !

!Integer methodsFor: 'converting' stamp: 'len 1/20/98 01:44'!
asAlgebraic
	"Answer an AlebraicNumber that represents the same value as does the receiver."
	^ AlgebraicNumber fromRational: self! !

!Integer methodsFor: 'accessing' stamp: 'len 1/20/98 01:45'!
denominator
	"Answer the denominator of the receiver."

	^ 1! !

!Integer methodsFor: 'accessing' stamp: 'len 1/20/98 01:45'!
numerator
	"Answer the numerator of the receiver."

	^ self! !


!Point methodsFor: 'converting' stamp: 'len 11/28/97 02:22'!
asTuple
	"Convert the receiver to a Tuple."

	^ self x, self y! !


!Polynomial commentStamp: '<historical>' prior: 0!
My instances are polynomials in one or many variables.

For an examples try this:
	| x y |
	x _ Polynomial x.
	y _ Polynomial y.
	(x + y) squared - x - y.
!

!Polynomial methodsFor: 'initialization' stamp: 'len 9/5/97 14:28'!
initialize
	self monomials: OrderedCollection new! !

!Polynomial methodsFor: 'accessing-private' stamp: 'len 1/20/98 00:53'!
add: aMonomial
	"Add aMonomial to the monomials of the receiver. Answer aMonomial."

	| mon coef |
	aMonomial isNull ifTrue: [^ aMonomial].
	mon _ self privateMonomialAt: aMonomial literal.
	mon isNil
		ifTrue: [self privateAddMonomial: aMonomial]
		ifFalse: [mon coefficient: (coef _ mon coefficient + aMonomial coefficient).
				coef isNull ifTrue: [self privateRemoveMonomial: mon]].
	^ aMonomial! !

!Polynomial methodsFor: 'accessing-private' stamp: 'len 12/3/97 02:24'!
addAll: aCollection
	"Add all the monomials in the argument to the receiver. Answer the argument."

	aCollection do: [ :each | self add: each].
	^ aCollection! !

!Polynomial methodsFor: 'accessing-private' stamp: 'len 1/27/98 23:33'!
monomials: aCollection
	monomials _ aCollection! !

!Polynomial methodsFor: 'accessing-private' stamp: 'len 1/20/98 01:28'!
privateAddMonomial: aMonomial
	self monomials add: aMonomial! !

!Polynomial methodsFor: 'accessing-private' stamp: 'len 1/20/98 01:28'!
privateMonomialAt: aMonomialLiteral
	^ self monomials detect: [ :each | each literal = aMonomialLiteral] ifNone: []! !

!Polynomial methodsFor: 'accessing-private' stamp: 'len 1/20/98 01:28'!
privateRemoveMonomial: aMonomial
	self monomials remove: aMonomial! !

!Polynomial methodsFor: 'accessing' stamp: 'len 1/27/98 23:33'!
first
	"Answer the first monomial of the receiver."

	^ self isNull
		 ifTrue: [self class monomialClass constant: self nullCoefficient]
		 ifFalse: [self sortedMonomials first]! !

!Polynomial methodsFor: 'accessing' stamp: 'len 1/13/98 00:05'!
head
	"Answer the head monomial of the receiver (a monomial of greatest degree)."

	^ self first! !

!Polynomial methodsFor: 'accessing' stamp: 'len 1/27/98 23:33'!
last
	"Answer the last monomial of the receiver."

	^ self isNull
		 ifTrue: [self class monomialClass constant: self nullCoefficient]
		 ifFalse: [self sortedMonomials last]! !

!Polynomial methodsFor: 'accessing' stamp: 'len 9/1/97 20:36'!
monomials
	"Answer the collection of the receiver's monomials."

	^ monomials! !

!Polynomial methodsFor: 'accessing' stamp: 'len 1/27/98 23:33'!
sortedMonomials
	"Answer the collection of the receiver's monomials, but sorted.
	 Notice that the returning collection can be used even to add
	 more monomials to the polynomials. The monomials are keeped
	 in a collection, refered by the instance variable ""monomials"",
	 and eventually, only when it's needed (when this method is
	 invocated), the collection is sorted."

	(monomials isKindOf: SortedCollection)
		ifFalse: [monomials _ monomials asSortedCollection: [ :a :b | a literal >= b literal]].
	^ monomials! !

!Polynomial methodsFor: 'accessing' stamp: 'len 10/18/97 02:30'!
tail
	"Answer the tail of the receiver."

	^ self - self head! !

!Polynomial methodsFor: 'accessing indeterminates' stamp: 'len 12/3/97 02:21'!
indeterminates
	"Answer the indeterminates of the receiver."

	| answer |
	answer _ Set new.
	self do: [ :each | answer addAll: each indeterminates].
	^ answer! !

!Polynomial methodsFor: 'accessing indeterminates' stamp: 'len 11/22/97 19:12'!
main
	"Answer the main indeterminate of the receiver."

	^ 1! !

!Polynomial methodsFor: 'accessing coefficients' stamp: 'len 1/27/98 05:15'!
coefficientAt: anIntegerOrALiteral 
	"Answer the coefficient of the degree (univariate case) 
	or literal given by the argument."

	^ (anIntegerOrALiteral isInteger
		ifTrue: [self monomials detect: [:each | each degree = anIntegerOrALiteral]
				ifNone: [^ self nullCoefficient]]
		ifFalse: [self monomials detect: [:each | each literal = anIntegerOrALiteral]
				ifNone: [^ self nullCoefficient]]) coefficient! !

!Polynomial methodsFor: 'accessing coefficients' stamp: 'len 12/3/97 02:25'!
coefficientAt: anInteger in: anotherInteger
	"Answer the coefficient of degree anInteger looking at the
	receiver as univariate in the anotherInteger-th indeterminate."

	| answer |

	"The answer will be 0 when the argument were negative
	 or greater than the degree of the receiver."
	(self degree < anInteger or: [anInteger negative])
		ifTrue: [^ self nullCoefficient].

	answer _ self class new.
	self do: [ :each |
		(each degreeIn: anotherInteger) = anInteger
			ifTrue: [answer add: (each copyWithout: anotherInteger)]].
	^ answer isConstant
		ifTrue: [answer leadingCoefficient]
		ifFalse: [answer]! !

!Polynomial methodsFor: 'accessing coefficients' stamp: 'len 11/22/97 21:51'!
coefficients
	"Answer the Array of coefficients of the receiver."

	^ self isNull
		ifTrue: [Array new]
		ifFalse: [(0 to: self degree) collect: [ :each | self coefficientAt: each]]! !

!Polynomial methodsFor: 'accessing coefficients' stamp: 'len 1/13/98 00:03'!
independentCoefficient
	"Answer the coefficient of the constant monomial of the receiver."

	| monomial |
	^ (monomial _ self last) isConstant
		ifTrue: [monomial coefficient]
		ifFalse: [self nullCoefficient]! !

!Polynomial methodsFor: 'accessing coefficients' stamp: 'len 11/22/97 21:50'!
leadingCoefficient
	"Answer the leading coefficient of the receiver."

	^ self isNull ifTrue: [self nullCoefficient] ifFalse: [self head coefficient]! !

!Polynomial methodsFor: 'accessing coefficients' stamp: 'len 12/3/97 02:25'!
leadingCoefficientIn: anInteger
	"Answer the leading coefficient of the receiver as
	univariate polynomial in the anInteger-th indeterminate."

	| deg answer |
	deg _ self degreeIn: anInteger.
	answer _ self class new.
	self do: [ :each |
		(each degreeIn: anInteger) = deg
			ifTrue: [answer add: (each copyWithout: anInteger)]].
	^ answer! !

!Polynomial methodsFor: 'arithmetic-private' stamp: 'len 1/23/98 16:28'!
divideBy: aPolynomial
	"Answer a division algorithm to divide the receiver by aPolynomial."

	^ PolynomialDivisor divide: self by: aPolynomial! !

!Polynomial methodsFor: 'arithmetic-private' stamp: 'len 10/18/97 21:34'!
privateMonomialDivision: anObject
	"Answer the product of the receiver and the argument, monomial by monomial."

	^ self class new monomials: (self monomials collect: [ :each | each / anObject])! !

!Polynomial methodsFor: 'arithmetic-private' stamp: 'len 10/18/97 21:33'!
privateMonomialProduct: anObject
	"Answer the product of the receiver and the argument, monomial by monomial."

	| newMonomials monomial |
	newMonomials _ OrderedCollection new.
	self monomials do: [ :each |
		(monomial _ each * anObject) isNull
			ifFalse: [newMonomials add: monomial]].
	^ self class new monomials: newMonomials! !

!Polynomial methodsFor: 'arithmetic-private' stamp: 'len 1/23/98 16:27'!
pseudoDivideBy: aPolynomial
	"Answer a pseudo-division algorithm to divide the receiver by aPolynomial."

	^ PolynomialPseudoDivisor divide: self by: aPolynomial! !

!Polynomial methodsFor: 'arithmetic-private' stamp: 'len 1/23/98 16:26'!
pseudoDivideBy: aPolynomial in: anInteger
	"Answer a pseudo-division algorithm to divide the receiver
	by aPolynomial with respect to the anInteger-th indeterminate."

	^ PolynomialPseudoDivisor divide: self by: aPolynomial in: anInteger! !

!Polynomial methodsFor: 'arithmetic' stamp: 'len 1/24/98 13:39'!
* anObject
	"Answer the product of the receiver and the argument."

	| answer |
	anObject isPolynomial ifTrue: [
		answer _ self class new.
		anObject do: [ :each |
			answer addAll: (self privateMonomialProduct: each) monomials].
		^ answer].
	(anObject isMonomial or: [anObject isMonomialLiteral])
		ifTrue: [^ self privateMonomialProduct: anObject].
	anObject isRationalFunction ifTrue: [^ self asRationalFunction * anObject].
	^ self mapCoefficients: [ :each | each * anObject]! !

!Polynomial methodsFor: 'arithmetic' stamp: 'len 9/1/97 20:42'!
** anInteger
	"Answer the receiver raised to anInteger."

	^ self raisedToInteger: anInteger! !

!Polynomial methodsFor: 'arithmetic' stamp: 'len 1/24/98 13:40'!
+ anObject
	"Answer the sum of the receiver and the argument."

	anObject isPolynomial
		ifTrue: [^ self copy addAll: (anObject monomials); yourself].
	anObject isMonomial
		ifTrue: [^ self copy add: anObject; yourself].
	anObject isRationalFunction ifTrue: [^ self asRationalFunction + anObject].

	^ self + (self identity * anObject)! !

!Polynomial methodsFor: 'arithmetic' stamp: 'len 10/18/97 02:33'!
- anObject
	"Answer the difference between the receiver and the argument."

	^ self + anObject negated! !

!Polynomial methodsFor: 'arithmetic' stamp: 'len 1/24/98 13:40'!
/ anObject
	"Answer the division of the receiver by the argument."

	(anObject isMonomial or: [anObject isMonomialLiteral])
		ifTrue: [^ self privateMonomialDivision: anObject].
	^ self * anObject reciprocal! !

!Polynomial methodsFor: 'arithmetic' stamp: 'len 1/24/98 13:41'!
// anObject
	"Answer the quotient of the division of the receiver by the argument."

	anObject isPolynomial
		ifTrue: [^ (self divideBy: anObject) quotient].
	^ self mapCoefficients: [ :each | each // anObject]! !

!Polynomial methodsFor: 'arithmetic' stamp: 'len 1/24/98 13:40'!
\\ anObject
	"Answer the remainder of the division of the receiver by the argument."

	anObject isPolynomial
		ifTrue: [^ (self divideBy: anObject) remainder].
	^ self mapCoefficients: [ :each | each \\ anObject]! !

!Polynomial methodsFor: 'arithmetic' stamp: 'len 10/18/97 02:33'!
negated
	"Answer the additive inverse of the receiver."

	^ self mapCoefficients: [ :each | each negated]! !

!Polynomial methodsFor: 'arithmetic' stamp: 'len 1/23/98 16:29'!
pseudoQuo: aPolynomial
	"Answer the quotient of the pseudo-division of the receiver by the argument."

	^ (self pseudoDivideBy: aPolynomial) quotient! !

!Polynomial methodsFor: 'arithmetic' stamp: 'len 1/23/98 16:29'!
pseudoQuo: aPolynomial in: anInteger
	"Answer the quotient of the pseudo-division of the receiver
	by the argument w.r.t to the anInteger-th indeterminate."

	^ (self pseudoDivideBy: aPolynomial in: anInteger) quotient! !

!Polynomial methodsFor: 'arithmetic' stamp: 'len 1/23/98 16:29'!
pseudoRem: aPolynomial
	"Answer the remainder of the pseudo-division of the receiver by the argument."

	^ (self pseudoDivideBy: aPolynomial) remainder! !

!Polynomial methodsFor: 'arithmetic' stamp: 'len 1/23/98 16:29'!
pseudoRem: aPolynomial in: anInteger
	"Answer the remainder of the pseudo-division of the receiver
	by the argument w.r.t to the anInteger-th indeterminate."

	^ (self pseudoDivideBy: aPolynomial in: anInteger) remainder! !

!Polynomial methodsFor: 'arithmetic' stamp: 'len 11/12/97 20:51'!
raisedToInteger: anInteger
	"Answer the receiver raised to the power anInteger."

	anInteger = 0 ifTrue: [^ self identity].
	anInteger = 1 ifTrue: [^ self].
	anInteger > 1
		ifTrue: [^ (self * self raisedToInteger: anInteger // 2)
				* (self raisedToInteger: anInteger \\ 2)].
	^ (self raisedToInteger: anInteger negated) reciprocal! !

!Polynomial methodsFor: 'arithmetic' stamp: 'len 11/23/97 01:43'!
raisedToInteger: anInteger mod: anObject
	"Answer the receiver raised to the power anInteger modulo anObject.
	The argument anInteger must be positive."

	| result y n |

	result _ self identity.
	n _ anInteger abs.
	y _ self \\ anObject.
	[n > 0] whileTrue: [
		n odd ifTrue: [result _ result * y \\ anObject].
		y _ y squared \\ anObject.
		n _ n // 2].

	^ anInteger negative ifTrue: [result negated] ifFalse: [result]! !

!Polynomial methodsFor: 'arithmetic' stamp: 'len 11/22/97 21:40'!
reciprocal
	"Answer the receiprocal of the receiver."

	^ self asRationalFunction reciprocal! !

!Polynomial methodsFor: 'arithmetic' stamp: 'len 9/1/97 20:44'!
squared
	"Answer the square of the receiver."

	^ self * self! !

!Polynomial methodsFor: 'mathematical functions' stamp: 'len 11/22/97 21:41'!
gcd: aPolynomial
	"Answer the greatest common divisor of the receiver and aPolynomial."

	| a b r |

	aPolynomial isNull ifTrue: [^ self].
	a _ self.
	b _ aPolynomial.
	[(r _ a \\ b) isNull] whileFalse: [a _ b. b _ r].
	^ b * b leadingCoefficient reciprocal! !

!Polynomial methodsFor: 'mathematical functions' stamp: 'len 11/22/97 21:41'!
lcm: aPolynomial
	"Answer the least common multiple of the receiver and aPolynomial."

	^ self // (self gcd: aPolynomial) * aPolynomial! !

!Polynomial methodsFor: 'mathematical functions' stamp: 'len 10/21/97 01:18'!
sign
	"Answer the sign of the receiver, i.e.
	the sign if its head coefficient."

	^ self head coefficient sign! !

!Polynomial methodsFor: 'equations' stamp: 'len 11/22/97 19:20'!
eq: anObject
	"Answer the equation 'self = anObject'."

	^ PolynomialEquation polynomial: self - anObject! !

!Polynomial methodsFor: 'equations' stamp: 'len 12/18/97 19:18'!
geq: anObject
	"Answer the inequality 'self >= anObject'."

	^ (self gneq: anObject) | (self eq: anObject)! !

!Polynomial methodsFor: 'equations' stamp: 'len 1/12/98 23:59'!
gneq: anObject
	"Answer the inequality 'self > anObject'."

	^ self negated lneq: anObject negated! !

!Polynomial methodsFor: 'equations' stamp: 'len 12/18/97 19:18'!
leq: anObject
	"Answer the inequality 'self <= anObject'."

	^ (self lneq: anObject) | (self eq: anObject)! !

!Polynomial methodsFor: 'equations' stamp: 'len 12/18/97 19:17'!
lneq: anObject
	"Answer the inequality 'self < anObject'."

	^ PolynomialInequality polynomial: self - anObject! !

!Polynomial methodsFor: 'equations' stamp: 'len 12/18/97 19:18'!
neq: anObject
	"Answer the inequation 'self ~= anObject'."

	^ (self lneq: anObject) | (self gneq: anObject)! !

!Polynomial methodsFor: 'operations' stamp: 'len 11/22/97 19:20'!
affinizedIn: anInteger
	"Answer the affinization of the receiver in the anInteger-th indeterminate."

	^ self class new
		monomials: (self monomials
			collect: [ :each | each copyWithout: anInteger])! !

!Polynomial methodsFor: 'operations' stamp: 'len 12/3/97 02:21'!
content
	"Answer the content of the receiver."

	| answer |
	self isNull ifTrue: [^ self nullCoefficient].
	self do: [ :each | answer _ answer isNil
						ifTrue: [each coefficient]
						ifFalse: [answer gcd: each coefficient]].
	^ answer! !

!Polynomial methodsFor: 'operations' stamp: 'len 1/23/98 03:06'!
degree
	"Answer the total degree of the receiver."

	| answer |
	self isNull ifTrue: [^ Infinity negative].
	answer _ 0.
	self do: [ :each | answer _ answer max: each degree].
	^ answer! !

!Polynomial methodsFor: 'operations' stamp: 'len 12/3/97 02:21'!
degreeIn: anInteger
	"Answer the degree of the receiver in the anInteger-th indeterminate."

	| answer |
	self isNull ifTrue: [^ Infinity negative].
	answer _ 0.
	self do: [ :each | answer _ answer max: (each degreeIn: anInteger)].
	^ answer! !

!Polynomial methodsFor: 'operations' stamp: 'len 12/3/97 02:25'!
derivativeIn: anInteger
	"Answer the derivative of the receiver in the anInteger-th indeterminate."

	| answer |
	answer _ self class new.
	self do: [ :each | answer add: (each derivativeIn: anInteger)].
	^ answer! !

!Polynomial methodsFor: 'operations' stamp: 'len 11/22/97 21:56'!
descendentPower: n
	"Answer the descendent power of the recever raised to the integer argument."

	| mid |
	n = 0 ifTrue: [^ self identity].
	n = 1 ifTrue: [^ self].
	n negative ifTrue: [^ (self descendentPower: n negated) reciprocal].
	mid _ n bitShift: -1.
	^ n even
		ifTrue: [(self - (self identityCoefficient * mid) descendentPower: mid) *
				(self descendentPower: mid)]
		ifFalse: [(self - (self identityCoefficient * mid) descendentPower: mid + 1) *
				(self descendentPower: mid)]! !

!Polynomial methodsFor: 'operations' stamp: 'len 11/22/97 19:20'!
discriminantIn: anInteger
	"Answer the discriminant of the receiver in the anInteger-th indeterminate."

	^ self resultant: (self derivativeIn: anInteger) in: anInteger! !

!Polynomial methodsFor: 'operations' stamp: 'len 12/3/97 02:25'!
evenIn: anInteger
	"Decompose the receiver in the form f(x^2)x + g(x^2) and
	answer g(x), where 'x' is the anInteger-th indeterminate."

	| answer monomial d |
	answer _ self class new.
	self do: [ :each |
		(d _ each degreeIn: anInteger) even ifTrue: [
			monomial _ each copy.
			monomial literal at: anInteger put: d // 2.
			answer add: monomial]].
	^ answer! !

!Polynomial methodsFor: 'operations' stamp: 'len 11/22/97 19:20'!
homogeneousComponentAt: anInteger
	"Answer the receiver's homogeneous component of degree anInteger."

	^ self class new monomials: (self monomials select: [ :each | each degree = anInteger])! !

!Polynomial methodsFor: 'operations' stamp: 'len 11/22/97 19:20'!
homogenizedIn: anInteger
	"Answer the homogenization of the receiver in the anInteger-th indeterminate."

	| degree |
	degree _ self degree.
	^ self class new
		monomials: (self monomials collect: [ :each |
			each complete: degree with: anInteger])! !

!Polynomial methodsFor: 'operations' stamp: 'len 9/5/97 14:12'!
integerContent
	"Answer the integer content of the receiver.
	NOTE: the receiver is supposed a polynomial over
	the rational numbers."

	| num den |
	self isNull ifTrue: [^ self].
	num _ self monomials first coefficient numerator.
	den _ self monomials first coefficient denominator.
	self monomials do: [ :each |
		num _ num gcd: each coefficient numerator.
		den _ den lcm: each coefficient denominator].
	^ (num / den) abs! !

!Polynomial methodsFor: 'operations' stamp: 'len 11/22/97 21:59'!
integerPrimitive
	"Answer the integer primitive polynomial associated to the receiver.
	Remove the integer content and the sign.
	NOTE: the receiver is supposed a polynomial over
	the rational numbers."

	self isNull ifTrue: [^ self].
	^ self / (self integerContent * self sign)! !

!Polynomial methodsFor: 'operations' stamp: 'len 1/13/98 00:03'!
ldegree
	"Answer the lowest degree of the receiver's monomials."

	^ self isNull ifTrue: [Infinity negative] ifFalse: [self last degree]! !

!Polynomial methodsFor: 'operations' stamp: 'len 8/25/97 01:23'!
mapCoefficients: aBlock
	"Answer a new polynomial like the receiver but with changing
	the coefficients applying to them aBlock."

	| newMonomials newCoefficient |

	newMonomials _ OrderedCollection new.
	self monomials do: [ :each |
		newCoefficient _ aBlock value: each coefficient.
		newCoefficient isNull ifFalse: [
			newMonomials add: (each copy coefficient: newCoefficient)]].
	^ self class new monomials: newMonomials! !

!Polynomial methodsFor: 'operations' stamp: 'len 12/3/97 02:22'!
norm1
	"Answer the 1-norm of the receiver."

	| answer |
	answer _ self nullCoefficient.
	self do: [ :each | answer _ answer + each coefficient abs].
	^ answer! !

!Polynomial methodsFor: 'operations' stamp: 'len 12/3/97 02:22'!
norm2
	"Answer the square norm of the receiver."

	| answer |
	answer _ self nullCoefficient.
	self do: [ :each | answer _ answer + each coefficient squared].
	^ answer! !

!Polynomial methodsFor: 'operations' stamp: 'len 12/3/97 02:22'!
normInfinite
	"Answer the infinite-norm of the receiver."

	| answer |
	answer _ self nullCoefficient.
	self do: [ :each | answer _ answer max: each coefficient abs].
	^ answer! !

!Polynomial methodsFor: 'operations' stamp: 'len 12/3/97 02:22'!
normMax
	"Answer the maximun norm of the receiver."

	| answer |
	answer _ self nullCoefficient.
	self do: [ :each | answer _ answer + each coefficient abs].
	^ answer! !

!Polynomial methodsFor: 'operations' stamp: 'len 12/3/97 02:25'!
oddIn: anInteger
	"Decompose the receiver in the form f(x^2)x + g(x^2) and
	answer f(x), where 'x' is the anInteger-th indeterminate."

	| answer monomial d |
	answer _ self class new.
	self do: [ :each |
		(d _ each degreeIn: anInteger) odd ifTrue: [
			monomial _ each copy.
			monomial literal at: anInteger put: d // 2.
			answer add: monomial]].
	^ answer! !

!Polynomial methodsFor: 'operations' stamp: 'len 9/5/97 14:13'!
primitive
	"Answer the primitive part of the receiver."

	| content |
	content _ self content.
	^ self mapCoefficients: [ :each | each / content]! !

!Polynomial methodsFor: 'operations' stamp: 'len 12/14/97 20:01'!
psc: anInteger with: aPolynomial in: anotherInteger
	"Answer the anInteger-th principal subresultant
	coefficient of the receiver with aPolynomial in
	the anotherInteger-th indeterminate."

	| n m matrix tuple |
	m _ self degreeIn: anotherInteger.
	n _ aPolynomial degreeIn: anotherInteger.
	matrix _ Matrix new.
	tuple _ Tuple dimension: m + n - anInteger - anInteger fromBlock: [ :each |
				self coefficientAt: m - each + 1 in: anotherInteger].
	n - anInteger timesRepeat: [matrix addRow: tuple. tuple _ tuple shift: 1].
	tuple _ Tuple dimension: m + n - anInteger - anInteger fromBlock: [ :each |
				aPolynomial coefficientAt: n - each + 1 in: anotherInteger].
	m - anInteger timesRepeat: [matrix addRow: tuple. tuple _ tuple shift: 1].
	^ matrix isEmpty ifTrue: [^ self identity] ifFalse: [matrix determinant]! !

!Polynomial methodsFor: 'operations' stamp: 'len 1/30/98 00:56'!
resultant: aPolynomial in: anInteger
	"Answer the resultant of the receiver with aPolynomial
	in the anInteger-th indeterminate."

	(self degreeIn: anInteger) = 0
		ifTrue: [^ aPolynomial raisedToInteger: self degree].
	(aPolynomial degreeIn: anInteger) = 0 ifTrue: [
		^ (self degree even or: [aPolynomial degree even])
			ifTrue: [(self raisedToInteger: aPolynomial degree)]
			ifFalse: [(self raisedToInteger: aPolynomial degree) negated]].

	^ (self sylvester: aPolynomial in: anInteger) determinant! !

!Polynomial methodsFor: 'operations' stamp: 'len 12/3/97 02:25'!
reversedIn: anInteger
	"Answer the reverse of the receiver as univariate
	polynomial in the anInteger-th indeterminate."

	| answer monomial n |
	n _ self degreeIn: anInteger.
	answer _ self class new.
	self do: [ :each |
		monomial _ each copy.
		monomial literal at: anInteger put: n - (each degreeIn: anInteger).
		answer add: each].
	^ answer! !

!Polynomial methodsFor: 'operations' stamp: 'len 12/3/97 02:25'!
shift: anInteger in: anotherInteger
	"Answer the receiver shifted anInteger places as univariate
	polynomial in the anotherInteger-th indeterminate."

	| answer monomial d |
	answer _ self class new.
	self do: [ :each |
		d _ (each degreeIn: anotherInteger) + anInteger.
		d negative ifFalse: [
			monomial _ each copy.
			monomial literal at: anotherInteger put: d.
			answer add: monomial]].
	^ answer! !

!Polynomial methodsFor: 'operations' stamp: 'len 12/14/97 20:19'!
subresultant: anInteger with: aPolynomial in: anotherInteger
	"Answer the anInteger-th subresultant of the receiver with
	the aPolynomial in the anotherInteger-th indeterminate."

	| lambda mu n m c matrix tuple |
	m _ self degreeIn: anotherInteger.
	n _ aPolynomial degreeIn: anotherInteger.
	lambda _ m min: n.
	mu _ (m max: n) - 1.
	anInteger = lambda
		ifTrue: [self degree + 1 < aPolynomial degree
					ifTrue: [c _ self]
					ifFalse: [aPolynomial degree + 1 < self degree
						ifTrue: [c _ aPolynomial] ifFalse: [^ nil]].
				^ c * ((c leadingCoefficientIn: anotherInteger)
						raisedToInteger: (m - n) abs - 1)].
	(anInteger between: lambda and: mu) ifTrue: [^ self null].
	(anInteger between: 0 and: lambda - 1) ifFalse: [self error: 'index out of range'].
	matrix _ Matrix new.
	tuple _ Tuple dimension: m + n - anInteger - anInteger fromBlock: [ :each |
				self coefficientAt: m - each + 1 in: anotherInteger].
	n - anInteger timesRepeat: [matrix addRow: tuple. tuple _ tuple shift: 1].
	tuple _ Tuple dimension: m + n - anInteger - anInteger fromBlock: [ :each |
				aPolynomial coefficientAt: n - each + 1 in: anotherInteger].
	m - anInteger timesRepeat: [matrix addRow: tuple. tuple _ tuple shift: 1].
	1 to: n - anInteger do: [ :each |
		matrix atRow: each column: m + n - anInteger - anInteger
				put: (self shift: n - anInteger - each in: anotherInteger)].
	1 to: m - anInteger do: [ :each |
		matrix atRow: n - anInteger + each column: m + n - anInteger - anInteger
				put: (aPolynomial shift: m - anInteger - each in: anotherInteger)].
	^ matrix determinant! !

!Polynomial methodsFor: 'operations' stamp: 'len 12/12/97 22:14'!
subresultantChain: aPolynomial in: anInteger
	"Answer the subresultant chain of the receiver with
	aPolynomial in the anInteger-th indeterminate."

	| chain n |
	n _ (self degreeIn: anInteger) > (aPolynomial degreeIn: anInteger)
			ifTrue: [(self degreeIn: anInteger) - 1]
			ifFalse: [aPolynomial degreeIn: anInteger].
	chain _ Array new: n + 2.
	0 to: n - 1 do: [ :each |
		chain
			at: each + 1
			put: (self subresultant: each with: aPolynomial in: anInteger)].
	chain at: n + 1 put: aPolynomial; at: n + 2 put: self.
	^ chain! !

!Polynomial methodsFor: 'operations' stamp: 'len 11/27/97 02:00'!
sylvester: aPolynomial in: anInteger
	"Answer the Sylvester matrix of the receiver with
	the argument in the anInteger-th indeterminate."

	| sumDegree selfDegree |
	selfDegree _ self degreeIn: anInteger.
	sumDegree _ selfDegree + (aPolynomial degreeIn: anInteger).
	^ self class matrixClass
		dimension: sumDegree @ sumDegree
		fromBlock: [ :each |
			each y <= selfDegree
				ifTrue: [aPolynomial coefficientAt: each x - each y in: anInteger]
				ifFalse: [self coefficientAt: each x - each y + selfDegree in: anInteger]]! !

!Polynomial methodsFor: 'operations' stamp: 'len 12/3/97 02:23'!
valueAt: anObject
	"Answer the value of the receiver at the argument."

	| answer |
	(anObject isTuple or: [anObject class == Array])
		ifFalse: [^ self valueAt: anObject in: self main].
	answer _ anObject first null.
	self do: [ :each |
		answer _ answer + (each valueAt: anObject)].
	^ answer! !

!Polynomial methodsFor: 'operations' stamp: 'len 12/13/97 05:23'!
valueAt: anObject in: anInteger
	"Answer the value of the receiver at anObject as univariate
	polynomial in the anInteger-th indeterminate."

	| f answer id deg |
	self isNull ifTrue: [^ anObject null].
	f _ self univariateIn: anInteger.
	id _ anObject identity.
	answer _ anObject null.
	deg _ f degree + 1.
	f sortedMonomials do: [ :each |
		answer _
			(anObject raisedToInteger: deg - (deg _ each degree)) * answer
			+ (id * each coefficient)].
	answer _ (anObject raisedToInteger: deg) * answer.
	^ answer! !

!Polynomial methodsFor: 'operations univariate' stamp: 'len 11/22/97 21:55'!
companion
	"Answer the companion matrix of the receiver."

	^ self class matrixClass companion: self! !

!Polynomial methodsFor: 'operations univariate' stamp: 'len 11/22/97 22:13'!
derivative
	"Answer the derivative of the receiver."

	^ self derivativeIn: self main! !

!Polynomial methodsFor: 'operations univariate' stamp: 'len 11/22/97 22:08'!
discriminant
	"Answer the discriminant of the receiver,
	i.e. the resultant of the receiver with its derivative."

	^ self discriminantIn: self main! !

!Polynomial methodsFor: 'operations univariate' stamp: 'len 11/22/97 22:12'!
even
	"Decompose the receiver in the form f(x^2)x + g(x^2) and answer g(x)."

	^ self evenIn: self main! !

!Polynomial methodsFor: 'operations univariate' stamp: 'len 11/22/97 21:59'!
multiplicityAt: anObject
	"Answer the multiplicity of anObject as zero of the receiver."

	| answer f |
	self isNull ifTrue: [^ Infinity positive].
	answer _ 0.
	f _ self.
	[(f valueAt: anObject) isNull] whileTrue: [
		answer _ answer + 1.
		f _ f derivative].
	^ answer! !

!Polynomial methodsFor: 'operations univariate' stamp: 'len 11/22/97 22:12'!
odd
	"Decompose the receiver in the form f(x^2)x + g(x^2) and answer f(x)."

	^ self oddIn: self main! !

!Polynomial methodsFor: 'operations univariate' stamp: 'len 11/22/97 23:29'!
resultant: aPolynomial
	"Answer the resultant of the receiver with the argument."

	^ self resultant: aPolynomial in: self main! !

!Polynomial methodsFor: 'operations univariate' stamp: 'len 11/22/97 22:15'!
reversed
	"Answer the reverse of the receiver."

	^ self reversedIn: self main! !

!Polynomial methodsFor: 'operations univariate' stamp: 'len 11/22/97 23:24'!
shift: anInteger
	"Answer the receiver shifted anInteger places."

	^ self shift: anInteger in: self main! !

!Polynomial methodsFor: 'operations univariate' stamp: 'len 11/22/97 23:25'!
sylvester: aPolynomial
	"Answer the Sylvester matrix of the receiver with the argument."

	^ self sylvester: aPolynomial in: self main! !

!Polynomial methodsFor: 'operations univariate' stamp: 'len 11/23/97 01:03'!
zeroAddition: aPolynomial
	"Answer a polynomial whose zeros are the addition of
	the receiver zeros with the zeros of the argument."

	| f g x y |
	self degree <= aPolynomial degree
		ifTrue: [f _ self. g _ aPolynomial]
		ifFalse: [g _ self. f _ aPolynomial].
	x _ self class x.
	y _ self class y.
	^ ((g valueAt: x - y) valueAt: f companion in: 2) determinant! !

!Polynomial methodsFor: 'operations univariate' stamp: 'len 11/22/97 23:36'!
zeroNegation
	"Answer a polynomial whose zeros are the receiver zeros negated."

	^ self class new monomials:
		(self monomials collect: [ :each |
			each degree even ifTrue: [each] ifFalse: [each negated]])! !

!Polynomial methodsFor: 'operations univariate' stamp: 'len 11/23/97 01:03'!
zeroProduct: aPolynomial
	"Answer a polynomial whose zeros are the product
	of the receiver zeros by the zeros of the argument."

	| f g |
	self degree <= aPolynomial degree
		ifTrue: [f _ self. g _ aPolynomial]
		ifFalse: [g _ self. f _ aPolynomial].
	^ ((g homogenizedIn: 2) valueAt: f companion in: 2) determinant! !

!Polynomial methodsFor: 'operations univariate' stamp: 'len 11/22/97 23:36'!
zeroReciprocal
	"Answer a polynomial whose zeros are the reciprocals of the receiver's zeros."

	^ self reversed! !

!Polynomial methodsFor: 'enumerating' stamp: 'len 12/3/97 02:23'!
do: aBlock
	"Enumerate the monomials of the receiver."

	self monomials do: aBlock! !

!Polynomial methodsFor: 'comparing' stamp: 'len 12/4/97 00:42'!
= anObject
	"Answer true if the receiver equals anObject."

	^ (self - anObject) isNull! !

!Polynomial methodsFor: 'comparing' stamp: 'len 1/23/98 03:12'!
hash
	"Answer the hash value of the receiver."

	| answer |
	answer _ -918347.
	self monomials do: [ :each | answer _ answer + each hash].
	^ answer! !

!Polynomial methodsFor: 'testing' stamp: 'len 7/30/97 21:39'!
isBinomial
	"Answer true if the receiver is a binomial."

	^ self monomials size = 2! !

!Polynomial methodsFor: 'testing' stamp: 'len 10/18/97 03:01'!
isConstant
	"Answer true if the receiver is constant."

	^ self degree < 1! !

!Polynomial methodsFor: 'testing' stamp: 'len 12/3/97 02:21'!
isHomogeneous
	"Answer true if the receiver is homogeneous."

	| n |
	self isNull ifTrue: [^ true].
	n _ self degree.
	self do: [ :each | each degree = n ifFalse: [^ false]].
	^ true! !

!Polynomial methodsFor: 'testing' stamp: 'len 10/18/97 03:01'!
isLinear
	"Answer true if the receiver is linear."

	^ self degree < 2! !

!Polynomial methodsFor: 'testing' stamp: 'len 11/22/97 21:45'!
isMonic
	"Answer true if the receiver is monic."

	^ self leadingCoefficient = self identityCoefficient! !

!Polynomial methodsFor: 'testing' stamp: 'len 9/1/97 20:49'!
isNull
	"Answer true if the receiver is null."

	^ self monomials isEmpty! !

!Polynomial methodsFor: 'testing' stamp: 'len 9/13/97 03:46'!
isPolynomial
	"Answer true if the receiver is a polynomial."

	^ true! !

!Polynomial methodsFor: 'testing' stamp: 'len 11/22/97 21:45'!
isSquareFree
	"Answer true if the receiver is square free."

	^ (self gcd: self derivative) degree = 0! !

!Polynomial methodsFor: 'testing' stamp: 'len 12/3/97 02:21'!
isUnivariateIn: anInteger
	"Answer true if the receiver is an univariate
	polynomial in the anInteger-th indeterminate."

	self do: [ :each | (each isUnivariateIn: anInteger) ifFalse: [^ false]].
	^ true! !

!Polynomial methodsFor: 'converting' stamp: 'len 8/1/97 18:30'!
@ anObject
	^ Point x: self y: anObject! !

!Polynomial methodsFor: 'converting' stamp: 'len 10/23/97 03:38'!
adaptFraction: aFraction
	^ self identity * aFraction! !

!Polynomial methodsFor: 'converting' stamp: 'len 7/12/97 23:27'!
adaptInteger: anInteger
	^ self identity * anInteger! !

!Polynomial methodsFor: 'converting' stamp: 'len 8/30/97 01:24'!
adaptToFraction
	^ self! !

!Polynomial methodsFor: 'converting' stamp: 'len 7/12/97 23:27'!
adaptToInteger
	^ self! !

!Polynomial methodsFor: 'converting' stamp: 'len 12/1/97 20:41'!
asPolynomial
	^ self! !

!Polynomial methodsFor: 'converting' stamp: 'len 11/22/97 21:43'!
asRationalFunction
	"Answer the rational function representing the receiver."

	^ RationalFunction
		numerator: self
		denominator: self identity! !

!Polynomial methodsFor: 'converting' stamp: 'len 12/3/97 02:25'!
univariateIn: anInteger
	"Answer the receiver as univariate in the anInteger-th indeterminate."

	| answer |
	(self isUnivariateIn: anInteger) ifTrue: [^ self].
	answer _ self class new.
	self do: [ :each | answer add: (each univariateIn: anInteger)].
	^ answer! !

!Polynomial methodsFor: 'copying' stamp: 'len 9/1/97 20:56'!
copy
	"Answer a copy of the receiver."

	^ self class new monomials: (self monomials collect: [ :each | each copy])! !

!Polynomial methodsFor: 'constants' stamp: 'len 10/23/97 03:40'!
identity
	self monomials do: [ :each | ^ self class fromMonomial: each identity].
	^ self class constant: self identityCoefficient! !

!Polynomial methodsFor: 'constants' stamp: 'len 7/28/97 19:25'!
identityCoefficient
	self isNull ifTrue: [^ self class identityCoefficient].
	^ self monomials first coefficient identity! !

!Polynomial methodsFor: 'constants' stamp: 'len 7/28/97 19:23'!
null
	^ self class new! !

!Polynomial methodsFor: 'constants' stamp: 'len 7/28/97 19:25'!
nullCoefficient
	self isNull ifTrue: [^ self class nullCoefficient].
	^ self monomials first coefficient null! !

!Polynomial methodsFor: 'constants' stamp: 'len 11/22/97 21:54'!
x
	"Answer the x polynomial."

	^ self class fromMonomial:
		(self class monomialClass coefficient: self identityCoefficient degree: 1)! !

!Polynomial methodsFor: 'printing-private' stamp: 'len 12/26/97 17:58'!
defaultNames
	"Answer the default names for the indeterminates."

	^ self class defaultNames! !

!Polynomial methodsFor: 'printing' stamp: 'len 12/26/97 17:59'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	self printOn: aStream withNames: self defaultNames! !

!Polynomial methodsFor: 'printing' stamp: 'len 12/21/97 20:51'!
printOn: aStream withNames: aDictionary
	"Print a representation of the receiver on the stream aStream.
	Use aDictionary to name the indeterminates."

	self head printOn: aStream withNames: aDictionary.
	self tail sortedMonomials do: [ :each |
		each coefficient printString first = $-
			ifTrue: [aStream nextPutAll: ' - '.
					each negated printOn: aStream withNames: aDictionary]
			ifFalse: [aStream nextPutAll: ' + '.
					each printOn: aStream withNames: aDictionary]]! !

!Polynomial methodsFor: 'misc misc' stamp: 'len 11/22/97 23:31'!
cauchyRootBound
	| max a0 an |
	max _ 0.
	self monomials do: [ :each | max _ max max: each coefficient abs].
	a0 _ self independentCoefficient abs.
	an _ self leadingCoefficient abs.
	^ Array with: a0 / (a0 + max) with: an + max / an! !

!Polynomial methodsFor: 'misc misc' stamp: 'len 11/22/97 21:47'!
eprs: aPolynomial
	"Answer the Euclidean Polynomial Remainder
	Sequence of the receiver with the argument."

	| answer last untilLast next |
	answer _ OrderedCollection new.
	self degree > aPolynomial degree ifTrue: [^ aPolynomial eprs: self].
	answer add: self.
	untilLast _ self.
	last _ aPolynomial.
	[last isNull] whileFalse: [
		answer add: last.
		next _ untilLast pseudoRem: last.
		untilLast _ last.
		last _ next
	].
	^ answer! !

!Polynomial methodsFor: 'misc misc' stamp: 'len 11/23/97 01:42'!
exactDivideBy: aPolynomial
	"Answer the exact division of the receiver by the argument."
	"Ref: 'Algorithms With Exact Divisions Made Faster', Arnold Schonhage,
	INRIA Research Report Nro. 2381, Algorithms Seminar 1993-1994, p. 51."

	| m u v qj qs shift |

"	(shift _ aPolynomial ldegree) > 0 ifTrue: [
		^ (self shift: shift) exactDivideBy: (aPolynomial shift: shift negated)
	]."
	m _ self degree + 1 // 2.
	u _ m // 2.
	v _ m - u.
	qj _ self jebeleanDivideBy: aPolynomial upTo: u.
	qs _ self schonhageDivideBy: aPolynomial upTo: v.
	^ self class coefficients: qj , qs

"
(Polynomial coefficients: #(4 7 9 10 10 6 3 1))
exactDivideBy:
(Polynomial coefficients: #(4 3 2 1))
"! !

!Polynomial methodsFor: 'misc misc' stamp: 'len 11/22/97 21:46'!
isIrreducibleHeuristic2: anInteger
	"Answer an Integer or nil. If the answer is an Integer, the
	receiver is irreducible iff that integer is prime, and in fact the
	integer will be prime with a very high probability (a probabilistic
	test is used here). If the answer is nil, the heuristic test has failed,
	and nothing can be said about the irreducibility of the receiver."

	"This is a probabilistic test for irreudcibility of rational univariate
	polynomials. It works looking for a prime evaluation of the polynomial.
	If it finds such a prime, then it's returned, and nil otherwise. The
	argument anInteger is the upper bound for the looking for primes."

	"Reference: 'A Heuristic Polynomial Irreducibility Test', Michael
	Monagan, J. Symbolic Comp., (1992) Vol. 13, No. 1, pp 47-57."

	| f g bg bound val try gcd |
	f _ self integerPrimitive.
	g _ f reversed.
	(bg _ g norm1 / g leadingCoefficient abs + 1) <
	(bound _ f norm1 / f leadingCoefficient abs + 1)
		ifTrue: [f _ g. bound _ bg].
	bound to: anInteger - 1 / 2 do: [ :each |
		val _ (f valueAt: each) abs.
		gcd _ val gcd: 355929487585205167172661547995662840887819680000.
		(gcd <= (each - bound) squared and: [(try _ val / gcd) isPrime])
			ifTrue: [^ try].
		val _ (f valueAt: each negated) abs.
		gcd _ val gcd: 355929487585205167172661547995662840887819680000.
		(gcd <= (each - bound) squared and: [(try _ val / gcd) isPrime])
			ifTrue: [^ try]
	].
	^ nil! !

!Polynomial methodsFor: 'misc misc' stamp: 'len 11/22/97 21:46'!
isIrreducibleHeuristic: anInteger
	"Answer an Integer or nil. If the answer is an Integer, the
	receiver is irreducible iff that integer is prime, and in fact the
	integer will be prime with a very high probability (a probabilistic
	test is used here). If the answer is nil, the heuristic test has failed,
	and nothing can be said about the irreducibility of the receiver."

	"This is a probabilistic test for irreudcibility of rational univariate
	polynomials. It works looking for a prime evaluation of the polynomial.
	If it finds such a prime, then it's returned, and nil otherwise. The
	argument anInteger is the upper bound for the looking for primes."

	| f val bound interval |
	f _ self integerPrimitive.
	bound _ f cauchyRootBound first floor abs.
	bound even ifTrue: [bound _ 0 max: bound - 1].
	interval _ f independentCoefficient odd
		ifTrue: [bound to: bound + (anInteger // 2)]
		ifFalse: [bound to: bound + anInteger by: 2].
	interval do: [ :each |
		val _ (f valueAt: each) abs.
		val isPrime ifTrue: [^ val].
		val _ (f valueAt: each negated) abs.
		val isPrime ifTrue: [^ val]
	].
	^ nil! !

!Polynomial methodsFor: 'misc misc' stamp: 'len 11/23/97 01:42'!
jebeleanDivideBy: aPolynomial upTo: k
	| f g cg q |

	f _ self coefficients.
	g _ aPolynomial coefficients.
	cg _ g first reciprocal.
	q _ Array new: k + 1.
	0 to: k do: [ :i |
		q at: i + 1 put: (f at: i + 1) * cg.
		1 to: k - i do: [ :j |
			f at: i + j + 1 put: (f at: i + j + 1) - ((q at: i + 1)*(g at: j + 1))]].
	^ q! !

!Polynomial methodsFor: 'misc misc' stamp: 'len 11/22/97 21:42'!
pgcd: aPolynomial
	"Answer the greatest common divisor of the receiver
	and aPolynomial using a probabilistic algorithm."

	| f g maps samples n |
	f _ self integerPrimitive.
	g _ aPolynomial integerPrimitive.
	n _ f degree max: g degree.
	maps _ OrderedCollection new: n + 1.
	samples _ 1 to: n.
	samples do:
		[ :each | maps add: each -> ((f valueAt: each) gcd: (g valueAt: each))].
	^ self class interpolate: maps! !

!Polynomial methodsFor: 'misc misc' stamp: 'len 11/22/97 21:47'!
pprs: aPolynomial
	"Answer the Primitive Polynomial Remainder
	Sequence of the receiver with the argument."

	| answer last untilLast next |
	answer _ OrderedCollection new.
	self degree > aPolynomial degree ifTrue: [^ aPolynomial pprs: self].
	answer add: self.
	untilLast _ self.
	last _ aPolynomial.
	[last isNull] whileFalse: [
		last _ last / last content.
		answer add: last.
		next _ untilLast pseudoRem: last.
		untilLast _ last.
		last _ next
	].
	^ answer! !

!Polynomial methodsFor: 'misc misc' stamp: 'len 11/22/97 23:30'!
resultant2: aPolynomial
	"Answer the resultant of the receiver with the argument."

	| f g mult |
	self degree <= aPolynomial degree
		ifTrue: [f _ self. g _ aPolynomial]
		ifFalse: [f _ aPolynomial. g _ self].
	f isConstant ifTrue: [^ (f raisedToInteger: g degree)].
	f isMonic
		ifTrue: [mult _ f identityCoefficient]
		ifFalse: [mult _ f leadingCoefficient raisedToInteger: g degree.
				f _ f / f leadingCoefficient].
	^ (g valueAt: f companion) determinant * mult! !

!Polynomial methodsFor: 'misc misc' stamp: 'len 11/22/97 23:30'!
resultant3: aPolynomial
	"Answer the resultant of the receiver with the argument."

	| f g answer negate |
	self degree > aPolynomial degree
		ifTrue: [f _ aPolynomial. g _ self. negate _ true]
		ifFalse: [f _ self. g _ aPolynomial. negate _ false].
	answer _ f isConstant
		ifTrue: [f raisedToInteger: g degree]
		ifFalse: [(f resultant3: g \\ f) *
				(f leadingCoefficient raisedToInteger: (g degree - f degree + 1))].
	^ negate ifTrue: [answer negated] ifFalse: [answer]! !

!Polynomial methodsFor: 'misc misc' stamp: 'len 11/23/97 01:41'!
schonhageDivideBy: aPolynomial upTo: k
	| f g cg m n q |

	f _ self coefficients.
	g _ aPolynomial coefficients.
	m _ self degree + 1.
	n _ aPolynomial degree + 1.
	cg _ g last reciprocal.
	q _ Array new: k.
	m - n to: m - n - k + 1 by: -1 do: [ :i |
		q at: i - m + n + k put: (f at: i + n) * cg.
		n - 2 to: m - k - i by: -1 do: [ :j |
			f at: i + j + 1 put: (f at: i + j + 1) - ((q at: i - m + n + k)*(g at: j + 1))]].
	^ q! !

!Polynomial methodsFor: 'misc misc' stamp: 'len 11/22/97 21:47'!
sprs: aPolynomial
	"Answer the Subresultant Polynomial Remainder
	Sequence of the receiver with the argument."

	self notYetImplemented! !

!Polynomial methodsFor: 'misc misc' stamp: 'len 11/22/97 21:47'!
squareFreeFactorization
	"Answer a square free factorization of the receiver.
	Use Yun's algorithm. Assume the coefficients are in a unique
	factorization domain or in a field of characteristic 0."

	| p q gcd count answer lc |

	answer _ Bag new.
	count _ 1.
	lc _ self leadingCoefficient.
	lc = self identityCoefficient
		ifFalse: [answer add: (self class constant: lc)].
	p _ self / lc.
	q _ p derivative.
	gcd _ p gcd: q.
	gcd degree > 0 ifTrue: [
		p _ p // gcd.
		q _ q // gcd - p derivative.
		[q isNull] whileFalse: [
			gcd _ p gcd: q.
			gcd degree > 0 ifTrue: [answer add: gcd withOccurrences: count].
			count _ count + 1.
			p _ p // gcd.
			q _ q // gcd - p derivative.
		]
	].
	^ answer add: p withOccurrences: count; yourself! !

!Polynomial methodsFor: 'misc misc' stamp: 'len 11/22/97 21:47'!
squareFreeFactorizationOLD
	"Answer a square free factorization of the receiver."

	| f gcd answer |

	answer _ Bag new.
	f _ self.
	[(gcd _ f gcd: f derivative) isConstant] whileFalse: [
		answer add: f // gcd. f _ gcd
	].
	^ answer add: f // gcd; add: gcd; yourself! !


!Polynomial class methodsFor: 'instance creation' stamp: 'len 11/23/97 00:31'!
coefficients: anArray
	"Answer a new instance of the receiver whose coefficients
	are the elements of the argument."

	| monomials |
	monomials _ OrderedCollection new: anArray size.
	1 to: anArray size do: [ :each |
		(anArray at: each) isNull ifFalse: [
			monomials add:
				(self monomialClass
					coefficient: (anArray at: each)
					degree: each - 1)]].
	^ self new monomials: monomials! !

!Polynomial class methodsFor: 'instance creation' stamp: 'len 9/9/97 00:51'!
constant: anObject
	"Answer a new instance the receiver with the constant object anObject."

	^ self fromMonomial: (self monomialClass constant: anObject)! !

!Polynomial class methodsFor: 'instance creation' stamp: 'len 12/3/97 02:25'!
fromMonomial: aMonomial
	"Answer a new instance of the receiver with only one monomial."

	^ self new add: aMonomial; yourself! !

!Polynomial class methodsFor: 'instance creation' stamp: 'len 9/9/97 00:54'!
identity
	"Answer an instance of the receiver representing the '1' polynomial."

	^ self constant: self identityCoefficient! !

!Polynomial class methodsFor: 'instance creation' stamp: 'len 7/11/97 20:51'!
new
	^ super new initialize! !

!Polynomial class methodsFor: 'instance creation' stamp: 'len 9/5/97 14:27'!
null
	"Answer an instance of the receiver representing a null polynomial."

	^ self new! !

!Polynomial class methodsFor: 'instance creation' stamp: 'len 11/22/97 19:30'!
x
	"Answer the 'x' polynomial."

	^ self x: 1! !

!Polynomial class methodsFor: 'instance creation' stamp: 'len 11/22/97 19:30'!
x: anInteger
	"Answer an instance of the receiver representing
	the polynomial with the sole anInteger-th indeterminate
	with degree 1 and coefficient 1."

	^ self x: anInteger to: 1 coefficient: self identityCoefficient! !

!Polynomial class methodsFor: 'instance creation' stamp: 'len 11/22/97 19:30'!
x: anInteger coefficient: anObject
	"Answer an instance of the receiver representing
	the polynomial with the sole anInteger-th indeterminate
	with degree 1 and coefficient anObject."

	^ self x: anInteger to: 1 coefficient: anObject! !

!Polynomial class methodsFor: 'instance creation' stamp: 'len 11/22/97 19:30'!
x: anInteger to: anotherInteger
	"Answer an instance of the receiver representing
	the polynomial with the sole anInteger-th indeterminate
	with degree anotherInteger and coefficient 1."

	^ self x: anInteger to: anotherInteger coefficient: self identityCoefficient! !

!Polynomial class methodsFor: 'instance creation' stamp: 'len 11/22/97 19:30'!
x: anInteger to: anotherInteger coefficient: anObject
	"Answer an instance of the receiver representing
	the polynomial with the sole anInteger-th indeterminate
	raised to anotherInteger and with coefficient anObject."

	^ self fromMonomial:
		(self monomialClass
			x: anInteger
			to: anotherInteger
			coefficient: anObject)! !

!Polynomial class methodsFor: 'instance creation' stamp: 'len 11/22/97 19:30'!
y
	"Answer the 'y' polynomial."

	^ self x: 2! !

!Polynomial class methodsFor: 'instance creation' stamp: 'len 11/22/97 19:30'!
z
	"Answer the 'z' polynomial."

	^ self x: 3! !

!Polynomial class methodsFor: 'related classes' stamp: 'len 8/28/97 02:49'!
matrixClass
	^ Matrix! !

!Polynomial class methodsFor: 'related classes' stamp: 'len 11/22/97 19:58'!
monomialClass
	^ Monomial! !

!Polynomial class methodsFor: 'examples' stamp: 'len 11/22/97 19:35'!
chebyshevOfOrder: n
	"Answer the n-th Chebyshev polynomial."

	| monomials c m k |
	n <= 0 ifTrue: [^ self identity].
	monomials _ OrderedCollection new: n // 2 + 1.
	c _ (1 bitShift: n - 1).
	m _ 4.
	k _ n - 1.
	monomials add:
		(self monomialClass
			degree: n
			coefficient: self identityCoefficient * c).
	n - 1 to: 1 by: -2 do: [ :each |
		c _ ((c * (each + 1) * each) / (k * m)) negated.
		m _ m + 4.
		k _ k - 1.
		c isNull ifFalse: [
			monomials add:
				(self monomialClass
					degree: each - 1
					coefficient: self identityCoefficient * c)]].
	^ self new monomials: monomials! !

!Polynomial class methodsFor: 'examples' stamp: 'len 11/22/97 19:33'!
continuantOfOrder: n
	"Answer the continuant polynomial of order n."
	"Polynomial continuantOfOrder: 3"

	n = 0 ifTrue: [^ self identity].
	n = 1 ifTrue: [^ self x: 1].
	^ (self continuantOfOrder: n - 1) * (self x: n) + (self continuantOfOrder: n - 2)! !

!Polynomial class methodsFor: 'examples' stamp: 'len 11/22/97 19:33'!
determinantOfOrder: n
	"Answer the determinant polynomial of order n."
	"Polynomial determinantOfOrder: 3"

	n = 0 ifTrue: [^ self null].
	^ (self matrixClass dimension: n @ n fromBlock: [ :each |
		self x: n * (each x - 1) + each y]) determinant! !

!Polynomial class methodsFor: 'examples' stamp: 'len 11/22/97 19:35'!
fibonacciOfOrder: n
	"Answer the n-th Fibonacci polynomial."
	"Polynomial fibonacciOfOrder: 3"

	n negative ifTrue: [^ self notYetImplemented].
	n = 0 ifTrue: [^ self null].
	n = 1 ifTrue: [^ self identity].
	^ (self fibonacciOfOrder: n - 1) - (self x * (self fibonacciOfOrder: n - 2))! !

!Polynomial class methodsFor: 'constants' stamp: 'len 1/23/98 16:24'!
defaultNames
	"Answer the default names for the indeterminates."

	^ MonomialLiteral defaultNames! !

!Polynomial class methodsFor: 'constants' stamp: 'len 8/30/97 01:09'!
identityCoefficient
	^ 1! !

!Polynomial class methodsFor: 'constants' stamp: 'len 8/30/97 01:09'!
nullCoefficient
	^ 0! !


!PolynomialDivisor methodsFor: 'initialization' stamp: 'len 1/23/98 15:49'!
divide: aPolynomial by: anotherPolynomial
	self dividend: aPolynomial.
	self divisor: anotherPolynomial.
	self done: false! !

!PolynomialDivisor methodsFor: 'accessing-private' stamp: 'len 8/29/97 00:17'!
done: aBoolean
	done _ aBoolean! !

!PolynomialDivisor methodsFor: 'accessing-private' stamp: 'len 8/29/97 00:18'!
quotient: aPolynomial
	quotient _ aPolynomial! !

!PolynomialDivisor methodsFor: 'accessing-private' stamp: 'len 8/29/97 00:18'!
remainder: aPolynomial
	remainder _ aPolynomial! !

!PolynomialDivisor methodsFor: 'accessing' stamp: 'len 8/29/97 00:21'!
dividend
	"Answer the dividend of the receiver."

	^ dividend! !

!PolynomialDivisor methodsFor: 'accessing' stamp: 'len 1/23/98 15:50'!
dividend: aPolynomial 
	dividend _ aPolynomial.
	self done: false! !

!PolynomialDivisor methodsFor: 'accessing' stamp: 'len 8/29/97 00:21'!
divisor
	"Answer the divisor of the receiver."

	^ divisor! !

!PolynomialDivisor methodsFor: 'accessing' stamp: 'len 1/23/98 15:50'!
divisor: aPolynomial 
	divisor _ aPolynomial.
	self done: false! !

!PolynomialDivisor methodsFor: 'accessing' stamp: 'len 8/29/97 00:22'!
done
	"Answer true if the quotient and the remainder have been computed."

	^ done! !

!PolynomialDivisor methodsFor: 'accessing' stamp: 'len 1/23/98 15:51'!
quotient
	"Answer the quotient of the receiver."
	self divide.
	^ quotient! !

!PolynomialDivisor methodsFor: 'accessing' stamp: 'len 1/23/98 15:51'!
remainder
	"Answer the remainder of the receiver."
	self divide.
	^ remainder! !

!PolynomialDivisor methodsFor: 'operations' stamp: 'len 1/24/98 13:35'!
divide
	"Divide the dividend by the divisor, computing
	the quotient and the remainder polynoials."

	| quo rem lc monomial n m |

	self done ifTrue: [^ self].
	self divisor isNull ifTrue: [^ self error: 'division by zero'].
	self divisor degree = 0
		ifTrue: [^ self quotient: self dividend * self divisor leadingCoefficient reciprocal;
					remainder: self dividend null;
					done: true].
	self dividend degree < self divisor degree
		ifTrue: [^ self quotient: self dividend null; remainder: self dividend; done: true].

	m _ self divisor degree.
	quo _ self dividend null.
	rem _ self dividend.
	lc _ self divisor leadingCoefficient.
	[(n _ rem degree) >= m] whileTrue: [
		monomial _ self dividend class monomialClass
						coefficient: rem leadingCoefficient / lc
						degree: n - m.
		rem _ rem + (self divisor * monomial negated).
		quo _ quo add: monomial; yourself].
	self quotient: quo; remainder: rem; done: true! !

!PolynomialDivisor methodsFor: 'printing' stamp: 'len 1/24/98 12:43'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	aStream
		print: self dividend;
		nextPutAll: ' = (';
		print: self quotient;
		nextPutAll: ')(';
		print: self divisor;
		nextPutAll: ') + ';
		print: self remainder! !


!PolynomialDivisor class methodsFor: 'instance creation' stamp: 'len 1/23/98 16:03'!
divide: aPolynomial by: anotherPolynomial
	"Answer a division algorithm to divide aPolynomial by anotherPolynomial."

	^ self new divide: aPolynomial by: anotherPolynomial! !


!PolynomialEquation commentStamp: '<historical>' prior: 0!
My instances are polynomial equations.

For an example try:
	| x y |
	x _ Polynomial x.
	y _ Polynomial y.
	PolynomialEquation polynomial: x*x + (y*y) - 1.

which is equivalent to:
	| x y |
	x _ Polynomial x.
	y _ Polynomial y.
	x*x + (y*y) eq: 1.
!

!PolynomialEquation methodsFor: 'accessing-private' stamp: 'len 9/5/97 14:15'!
polynomial: aPolynomial
	aPolynomial monomials do: [ :each |
		each coefficient isRational
			ifFalse: [polynomial _ aPolynomial. ^ self]].
	polynomial _ aPolynomial integerPrimitive! !

!PolynomialEquation methodsFor: 'accessing' stamp: 'len 12/21/97 21:06'!
bounded
	"Answer the collection of bounded indeterminates."

	^ Set new! !

!PolynomialEquation methodsFor: 'accessing' stamp: 'len 12/21/97 21:06'!
free
	"Answer the collection of free indeterminates."

	^ self indeterminates! !

!PolynomialEquation methodsFor: 'accessing' stamp: 'len 12/18/97 20:34'!
indeterminates
	"Answer the indeterminates of the receiver."

	^ self polynomial indeterminates! !

!PolynomialEquation methodsFor: 'accessing' stamp: 'len 7/30/97 23:47'!
polynomial
	"Answer the polynomial that defines the receiver."

	^ polynomial! !

!PolynomialEquation methodsFor: 'accessing' stamp: 'len 12/19/97 21:47'!
polynomials
	"Answer the polynomial set of the receiver."

	^ PolynomialSet new add: self polynomial; yourself! !

!PolynomialEquation methodsFor: 'arithmetic' stamp: 'len 12/18/97 19:56'!
& anObject
	"Answer the conjunction of the receiver with the argument."

	^ ConjunctionConnective left: self right: anObject! !

!PolynomialEquation methodsFor: 'arithmetic' stamp: 'len 12/18/97 19:57'!
-> anObject
	"Answer the implication of the argument from the receiver."

	^ ImplicationConnective left: self right: anObject! !

!PolynomialEquation methodsFor: 'arithmetic' stamp: 'len 12/21/97 21:26'!
exists: anInteger
	"Answer the quantification of the reciever by the
	existential quantifier in the anInteger-th indeterminate."

	^ QuantifiedSentence quantifier: (Quantifier exists: anInteger) matrix: self! !

!PolynomialEquation methodsFor: 'arithmetic' stamp: 'len 12/21/97 21:26'!
forAll: anInteger
	"Answer the quantification of the reciever by the
	universal quantifier in the anInteger-th indeterminate."

	^ QuantifiedSentence quantifier: (Quantifier forAll: anInteger) matrix: self! !

!PolynomialEquation methodsFor: 'arithmetic' stamp: 'len 12/18/97 19:58'!
not
	"Answer the negation of the receiver."

	^ (self polynomial lneq: self polynomial null)
		| (self polynomial gneq: self polynomial null)! !

!PolynomialEquation methodsFor: 'arithmetic' stamp: 'len 12/18/97 19:56'!
| anObject
	"Answer the disjunction of the receiver with the argument."

	^ DisjunctionConnective left: self right: anObject! !

!PolynomialEquation methodsFor: 'operations' stamp: 'len 12/26/97 18:46'!
normalized
	"Answer a copy of the receiver with the indeterminates renamed
	such that the same indeterminate does not ocur as free and bound."

	^ self copy! !

!PolynomialEquation methodsFor: 'operations' stamp: 'len 12/31/97 02:26'!
prenex
	"Answer the prenex form of the receiver."

	^ self reduced normalized privatePrenex! !

!PolynomialEquation methodsFor: 'operations' stamp: 'len 12/26/97 18:38'!
reduced
	"Answer a copy of the receiver with the redundant quantifiers removed."

	^ self copy! !

!PolynomialEquation methodsFor: 'operations' stamp: 'len 2/5/98 00:49'!
rename: anInteger to: anotherInteger 
	"Rename the anInteger-th indeterminate of the receiver to anotherInteger."
	| xi |
	xi _ self polynomial class x: anotherInteger.
	self polynomial: (self polynomial valueAt: xi in: anInteger)! !

!PolynomialEquation methodsFor: 'copying' stamp: 'len 12/19/97 02:48'!
copy
	"Answer a copy of the receiver."

	^ self class polynomial: self polynomial copy! !

!PolynomialEquation methodsFor: 'testing' stamp: 'len 12/18/97 20:28'!
isQuantifierFree
	"Answer true if the receiver is quantifier-free."

	^ true! !

!PolynomialEquation methodsFor: 'testing' stamp: 'len 8/22/97 01:25'!
isSolution: anObject
	"Answer true if the argument satisfies the receiver."

	^ (self polynomial valueAt: anObject) isNull! !

!PolynomialEquation methodsFor: 'private' stamp: 'len 12/31/97 02:27'!
privatePrenex
	"Answer the prenex form of the receiver.
	Assume the receiver is reduced and normalized."

	^ QuantifiedSentence matrix: self! !

!PolynomialEquation methodsFor: 'printing' stamp: 'len 7/30/97 23:51'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	aStream print: self polynomial; nextPutAll: ' = 0'! !


!PolynomialEquation class methodsFor: 'instance creation' stamp: 'len 7/30/97 23:45'!
polynomial: aPolynomial
	"Answer an instance of the receiver representing
	the equation 'aPolynomial = 0'."

	^ self new polynomial: aPolynomial! !


!PolynomialFactorizer methodsFor: 'initialization' stamp: 'len 8/27/97 23:07'!
polynomial: aPolynomial
	"Change the polynomial of the receiver."

	self privatePolynomial: aPolynomial.
	self factors: Bag new.
	self done: false! !

!PolynomialFactorizer methodsFor: 'accessing-private' stamp: 'len 8/23/97 21:57'!
done: aBoolean
	done _ aBoolean! !

!PolynomialFactorizer methodsFor: 'accessing-private' stamp: 'len 8/23/97 17:38'!
factors: aCollection
	factors _ aCollection! !

!PolynomialFactorizer methodsFor: 'accessing-private' stamp: 'len 8/23/97 17:46'!
irreducible: anInteger
	irreducible _ anInteger! !

!PolynomialFactorizer methodsFor: 'accessing-private' stamp: 'len 8/23/97 23:04'!
privateFactors
	^ factors! !

!PolynomialFactorizer methodsFor: 'accessing-private' stamp: 'len 8/27/97 00:37'!
privatePolynomial: aPolynomial
	polynomial _ aPolynomial! !

!PolynomialFactorizer methodsFor: 'accessing' stamp: 'len 8/23/97 17:39'!
done
	"Answer true if the polynomial has been factored."

	^ done! !

!PolynomialFactorizer methodsFor: 'accessing' stamp: 'len 11/24/97 22:02'!
factors
	"Answer the factors of the poylnomial."

	self factorize.
	^ factors! !

!PolynomialFactorizer methodsFor: 'accessing' stamp: 'len 8/23/97 17:54'!
irreducible
	"Answer a fraction 'q' representing that the polynomial
	is irreducible with probability of error less than 'q'."

	^ irreducible! !

!PolynomialFactorizer methodsFor: 'accessing' stamp: 'len 8/23/97 17:39'!
polynomial
	"Answer the polynomial of the receiver."

	^ polynomial! !

!PolynomialFactorizer methodsFor: 'operations' stamp: 'len 8/25/97 00:02'!
factorize
	"Factorize the polynomial of the receiver."

	self subclassResponsibility! !

!PolynomialFactorizer methodsFor: 'testing' stamp: 'len 8/23/97 17:53'!
isIrreducible
	"Answer true if the polynomial is irreducible."

	(self irreducible = 0 or: [self irreducible = 1])
		ifFalse: [self computeIrreducibility].
	^ self irreducible = 1! !

!PolynomialFactorizer methodsFor: 'testing' stamp: 'len 9/4/97 22:01'!
isIrreducibleProbabilistic: anInteger
	"Answer true if the polynomial is irreducible with
	probability of error less than '1/2^anInteger'."

	^ self isIrreducible! !

!PolynomialFactorizer methodsFor: 'private' stamp: 'len 9/4/97 22:00'!
computeIrreducibility
	"Compute the irreducibility of the receiver."

	self subclassResponsibility! !

!PolynomialFactorizer methodsFor: 'printing' stamp: 'len 8/23/97 21:56'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	aStream nextPutAll: self class name; nextPutAll: ' on '; print: self polynomial! !


!PolynomialFactorizer class methodsFor: 'instance creation' stamp: 'len 11/6/97 21:12'!
polynomial: aPolynomial
	"Answer a new instance of the receiver to factorize aPolynomial."

	^ self new polynomial: aPolynomial! !


!PolynomialInequality commentStamp: '<historical>' prior: 0!
My instances are polynomial inequalities.

For an example try:
	| x y |
	x _ Polynomial x.
	y _ Polynomial y.
	PolynomialInequality polynomial: x*x + (y*y) - 1.

which is equivalent to:
	| x y |
	x _ Polynomial x.
	y _ Polynomial y.
	x*x + (y*y) lneq: 1.
!

!PolynomialInequality methodsFor: 'accessing-private' stamp: 'len 1/12/98 23:55'!
polynomial: aPolynomial
	aPolynomial monomials do: [ :each |
		each coefficient isRational
			ifFalse: [polynomial _ aPolynomial. ^ self]].
	polynomial _ aPolynomial / aPolynomial integerContent abs! !

!PolynomialInequality methodsFor: 'accessing' stamp: 'len 12/21/97 21:06'!
bounded
	"Answer the collection of bounded indeterminates."

	^ Set new! !

!PolynomialInequality methodsFor: 'accessing' stamp: 'len 12/21/97 21:07'!
free
	"Answer the collection of free indeterminates."

	^ self indeterminates! !

!PolynomialInequality methodsFor: 'accessing' stamp: 'len 12/18/97 20:34'!
indeterminates
	"Answer the indeterminates of the receiver."

	^ self polynomial indeterminates! !

!PolynomialInequality methodsFor: 'accessing' stamp: 'len 12/15/97 23:57'!
polynomial
	"Answer the polynomial that defines the receiver."

	^ polynomial! !

!PolynomialInequality methodsFor: 'accessing' stamp: 'len 12/19/97 21:47'!
polynomials
	"Answer the polynomial set of the receiver."

	^ PolynomialSet new add: self polynomial; yourself! !

!PolynomialInequality methodsFor: 'arithmetic' stamp: 'len 12/18/97 20:07'!
& anObject
	"Answer the conjunction of the receiver with the argument."

	^ ConjunctionConnective left: self right: anObject! !

!PolynomialInequality methodsFor: 'arithmetic' stamp: 'len 12/18/97 20:07'!
-> anObject
	"Answer the implication of the argument from the receiver."

	^ ImplicationConnective left: self right: anObject! !

!PolynomialInequality methodsFor: 'arithmetic' stamp: 'len 12/21/97 21:26'!
exists: anInteger
	"Answer the quantification of the reciever by the
	existential quantifier in the anInteger-th indeterminate."

	^ QuantifiedSentence quantifier: (Quantifier exists: anInteger) matrix: self! !

!PolynomialInequality methodsFor: 'arithmetic' stamp: 'len 12/21/97 21:27'!
forAll: anInteger
	"Answer the quantification of the reciever by the
	universal quantifier in the anInteger-th indeterminate."

	^ QuantifiedSentence quantifier: (Quantifier forAll: anInteger) matrix: self! !

!PolynomialInequality methodsFor: 'arithmetic' stamp: 'len 12/18/97 20:09'!
not
	"Answer the negation of the receiver."

	^ (self polynomial eq: self polynomial null) |
		(self polynomial gneq: self polynomial null)! !

!PolynomialInequality methodsFor: 'arithmetic' stamp: 'len 12/18/97 20:07'!
| anObject
	"Answer the disjunction of the receiver with the argument."

	^ DisjunctionConnective left: self right: anObject! !

!PolynomialInequality methodsFor: 'operations' stamp: 'len 12/26/97 18:46'!
normalized
	"Answer a copy of the receiver with the indeterminates renamed
	such that the same indeterminate does not ocur as free and bound."

	^ self copy! !

!PolynomialInequality methodsFor: 'operations' stamp: 'len 12/31/97 02:26'!
prenex
	"Answer the prenex form of the receiver."

	^ self reduced normalized privatePrenex! !

!PolynomialInequality methodsFor: 'operations' stamp: 'len 12/26/97 18:38'!
reduced
	"Answer a copy of the receiver with the redundant quantifiers removed."

	^ self copy! !

!PolynomialInequality methodsFor: 'operations' stamp: 'len 2/5/98 00:49'!
rename: anInteger to: anotherInteger
	"Rename the anInteger-th indeterminate of the receiver to anotherInteger."
	| xi |
	xi _ self polynomial class x: anotherInteger.
	self polynomial: (self polynomial valueAt: xi in: anInteger)! !

!PolynomialInequality methodsFor: 'copying' stamp: 'len 12/19/97 02:47'!
copy
	"Answer a copy of the receiver."

	^ self class polynomial: self polynomial copy! !

!PolynomialInequality methodsFor: 'testing' stamp: 'len 12/18/97 20:28'!
isQuantifierFree
	"Answer true if the receiver is quantifier-free."

	^ true! !

!PolynomialInequality methodsFor: 'testing' stamp: 'len 12/15/97 23:59'!
isSolution: anObject
	"Answer true if the argument satisfies the receiver."

	^ (self polynomial valueAt: anObject) negative! !

!PolynomialInequality methodsFor: 'private' stamp: 'len 12/31/97 02:27'!
privatePrenex
	"Answer the prenex form of the receiver.
	Assume the receiver is reduced and normalized."

	^ QuantifiedSentence matrix: self! !

!PolynomialInequality methodsFor: 'printing' stamp: 'len 1/12/98 23:54'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	| f ineq coeff |
	self polynomial head coefficient negative
		ifTrue: [f _ self polynomial negated. ineq _ ' > ']
		ifFalse: [f _ self polynomial. ineq _ ' < '].
	(coeff _ f coefficientAt: 0) negative
		ifTrue: [aStream print: f - coeff; nextPutAll: ineq; print: coeff negated]
		ifFalse: [aStream print: f; nextPutAll: ineq; nextPut: $0]! !


!PolynomialInequality class methodsFor: 'instance creation' stamp: 'len 12/16/97 00:00'!
polynomial: aPolynomial
	"Answer an instance of the receiver representing
	the inequation 'aPolynomial < 0'."

	^ self new polynomial: aPolynomial! !


!PolynomialInterpolator methodsFor: 'initialization' stamp: 'len 11/23/97 00:08'!
initialize
	self polynomial: Polynomial null.
	self corrector: Polynomial identity! !

!PolynomialInterpolator methodsFor: 'accessing-private' stamp: 'len 11/17/97 18:20'!
corrector: aPolynomial
	corrector _ aPolynomial! !

!PolynomialInterpolator methodsFor: 'accessing-private' stamp: 'len 11/17/97 18:20'!
polynomial: aPolynomial
	polynomial _ aPolynomial! !

!PolynomialInterpolator methodsFor: 'accessing' stamp: 'len 11/17/97 18:21'!
corrector
	"Answer the correction polynoial."

	^ corrector! !

!PolynomialInterpolator methodsFor: 'accessing' stamp: 'len 11/17/97 18:20'!
polynomial
	"Answer the interpolation polynoial."

	^ polynomial! !

!PolynomialInterpolator methodsFor: 'operations' stamp: 'len 5/28/1998 20:11'!
map: aNumber to: anotherNumber
	"Change the interpolation polynomial to map aNumber to anotherNumber."

	| f q m |
	f _ self polynomial.
	q _ self corrector.
	m _ anotherNumber - (f valueAt: aNumber) / (q valueAt: aNumber).
	f _ q * m + f.
	q _ q * aNumber negated + (q shift: 1).
	self polynomial: f.
	self corrector: q.
	^ anotherNumber! !


!PolynomialInterpolator class methodsFor: 'instance creation' stamp: 'len 11/17/97 18:30'!
new
	^ super new initialize! !


!PolynomialPseudoDivisor methodsFor: 'initialization' stamp: 'len 1/23/98 15:38'!
divide: aPolynomial by: anotherPolynomial in: anInteger
	self dividend: aPolynomial;
		divisor: anotherPolynomial;
		indeterminate: anInteger;
		done: false! !

!PolynomialPseudoDivisor methodsFor: 'accessing-private' stamp: 'len 8/29/97 00:39'!
done: aBoolean
	done _ aBoolean! !

!PolynomialPseudoDivisor methodsFor: 'accessing-private' stamp: 'len 8/29/97 00:39'!
quotient: aPolynomial
	quotient _ aPolynomial! !

!PolynomialPseudoDivisor methodsFor: 'accessing-private' stamp: 'len 8/29/97 00:39'!
remainder: aPolynomial
	remainder _ aPolynomial! !

!PolynomialPseudoDivisor methodsFor: 'accessing' stamp: 'len 1/24/98 13:01'!
delta
	"Answer an integer delta such that the dividend
	multiplied by its leading coeficient raised to the delta
	equals the product of the quotient by the divisor plus
	the remainder (the pseudo-division relation)."

	^ self dividend degree - self divisor degree + 1 max: 0! !

!PolynomialPseudoDivisor methodsFor: 'accessing' stamp: 'len 8/29/97 00:39'!
dividend
	"Answer the dividend of the receiver."

	^ dividend! !

!PolynomialPseudoDivisor methodsFor: 'accessing' stamp: 'len 1/23/98 15:35'!
dividend: aPolynomial
	dividend _ aPolynomial.
	self done: false! !

!PolynomialPseudoDivisor methodsFor: 'accessing' stamp: 'len 8/29/97 00:40'!
divisor
	"Answer the divisor of the receiver."

	^ divisor! !

!PolynomialPseudoDivisor methodsFor: 'accessing' stamp: 'len 1/23/98 15:35'!
divisor: aPolynomial
	divisor _ aPolynomial.
	self done: false! !

!PolynomialPseudoDivisor methodsFor: 'accessing' stamp: 'len 8/29/97 00:40'!
done
	"Answer true if the quotient and the remainder have been computed."

	^ done! !

!PolynomialPseudoDivisor methodsFor: 'accessing' stamp: 'len 1/23/98 15:37'!
indeterminate
	"Answer the indeterminate with respect to is the receiver dividing."

	^ indeterminate! !

!PolynomialPseudoDivisor methodsFor: 'accessing' stamp: 'len 1/23/98 15:36'!
indeterminate: anInteger
	indeterminate _ anInteger.
	self done: false! !

!PolynomialPseudoDivisor methodsFor: 'accessing' stamp: 'len 1/23/98 15:43'!
quotient
	"Answer the quotient of the receiver."

	self divide.
	^ quotient! !

!PolynomialPseudoDivisor methodsFor: 'accessing' stamp: 'len 1/23/98 15:47'!
remainder
	"Answer the remainder of the receiver."
	self divide.
	^ remainder! !

!PolynomialPseudoDivisor methodsFor: 'operations' stamp: 'len 1/24/98 13:35'!
divide
	| m n am bn nextDivisor indet |

	self done ifTrue: [^ self].
	self divisor isNull ifTrue: [self error: 'division by zero'].
	indet _ self indeterminate.
	(m _ self dividend degreeIn: indet) < (n _ self divisor degreeIn: indet)
		ifTrue: [^ self quotient: self dividend null; remainder: self dividend; done: true].

	am _ self dividend leadingCoefficientIn: indet.
	bn _ self divisor leadingCoefficientIn: indet.
	nextDivisor _ self class
					divide: bn * self dividend - (am * self divisor shift: m - n in: indet)
					by: self divisor
					in: indet.
	self quotient: (am * (bn raisedToInteger: m - n) shift: m - n in: indet) + nextDivisor quotient;
		remainder: nextDivisor remainder;
		done: true! !

!PolynomialPseudoDivisor methodsFor: 'printing' stamp: 'len 1/24/98 12:55'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	aStream
		print: (self divisor leadingCoefficient raisedToInteger: self delta);
		nextPut: $(;
		print: self dividend;
		nextPutAll: ') = (';
		print: self quotient;
		nextPutAll: ')(';
		print: self divisor;
		nextPutAll: ') + ';
		print: self remainder! !


!PolynomialPseudoDivisor class methodsFor: 'instance creation' stamp: 'len 1/23/98 16:05'!
divide: aPolynomial by: anotherPolynomial
	"Answer a pseudo-division algorithm to divide aPolynomial by anotherPolynomial."

	^ self divide: aPolynomial by: anotherPolynomial in: aPolynomial main! !

!PolynomialPseudoDivisor class methodsFor: 'instance creation' stamp: 'len 1/23/98 16:05'!
divide: aPolynomial by: anotherPolynomial in: anInteger 
	"Answer a pseudo-division algorithm to divide 
	aPolynomial by anotherPolynomial with respect 
	to the anInteger-th indeterminate."

	^ self new divide: aPolynomial by: anotherPolynomial in: anInteger! !


!PolynomialRootFinder methodsFor: 'initialization' stamp: 'len 9/10/97 20:18'!
polynomial: aPolynomial	
	"Change the polynomial of the receiver."

	self privatePolynomial: aPolynomial.
	self roots: OrderedCollection new.
	self done: false! !

!PolynomialRootFinder methodsFor: 'accessing-private' stamp: 'len 8/28/97 02:18'!
done: aBoolean
	done _ aBoolean! !

!PolynomialRootFinder methodsFor: 'accessing-private' stamp: 'len 8/27/97 00:39'!
privatePolynomial: aPolynomial
	polynomial _ aPolynomial! !

!PolynomialRootFinder methodsFor: 'accessing-private' stamp: 'len 8/26/97 00:36'!
privateRoots
	^ roots! !

!PolynomialRootFinder methodsFor: 'accessing-private' stamp: 'len 8/26/97 00:31'!
roots: aCollection
	roots _ aCollection! !

!PolynomialRootFinder methodsFor: 'accessing' stamp: 'len 8/27/97 00:39'!
done
	"Answer true if the roots of the polynomial have been found."

	^ done! !

!PolynomialRootFinder methodsFor: 'accessing' stamp: 'len 8/26/97 00:33'!
polynomial
	"Answer the polynomial of the receiver."

	^ polynomial! !

!PolynomialRootFinder methodsFor: 'accessing' stamp: 'len 11/24/97 22:03'!
roots
	"Answer a collection with the roots of the receiver."

	self separateRoots.
	^ roots! !

!PolynomialRootFinder methodsFor: 'printing' stamp: 'len 8/26/97 00:37'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	aStream nextPutAll: self class name; nextPutAll: ' on '; print: self polynomial! !


!AlgebraicPolynomialRootFinder methodsFor: 'initialization' stamp: 'len 12/1/97 20:43'!
polynomial: aPolynomial
	"Change the polynomial of the receiver."

	self privatePolynomial:
		(aPolynomial // (aPolynomial gcd: aPolynomial derivative)) integerPrimitive.
	self roots:
		(SortedCollection
			sortBlock: [ :one :other | one leftBound <= other leftBound]).
	self done: false! !

!AlgebraicPolynomialRootFinder methodsFor: 'accessing-private' stamp: 'len 11/18/97 00:44'!
fourier: aCollection
	fourier _ aCollection! !

!AlgebraicPolynomialRootFinder methodsFor: 'accessing-private' stamp: 'len 8/17/97 21:49'!
sturm: aCollection
	sturm _ aCollection! !

!AlgebraicPolynomialRootFinder methodsFor: 'accessing' stamp: 'len 11/18/97 00:38'!
fourier
	"Answer the Budan-Fourier sequence for the polynomial of the receiver."

	fourier isNil ifTrue: [self computeFourier].
	^ fourier! !

!AlgebraicPolynomialRootFinder methodsFor: 'accessing' stamp: 'len 8/23/97 18:10'!
sturm
	"Answer a sturm sequence for the polynomial of the receiver."

	sturm isNil ifTrue: [self computeSturm].
	^ sturm! !

!AlgebraicPolynomialRootFinder methodsFor: 'couting roots' stamp: 'len 11/18/97 02:37'!
lowerBoundNumberOfRootsBetween: leftBound and: rightBound
	"Answer a lower bound for the number of real roots
	in the open interval (leftBound, rightBound)."

	| answer last sign |
	answer _ 0.
	last _ 0.
	(1 to: self polynomial degree * 2) do: [ :each |
		sign _ (self polynomial valueAt: (rightBound - leftBound) / each) sign.
		(last ~= sign and: [sign ~= 0]) ifTrue: [answer _ answer + 1].
		last _ sign].
	^ answer! !

!AlgebraicPolynomialRootFinder methodsFor: 'couting roots' stamp: 'len 11/18/97 02:48'!
moreThanOneRootBetween: leftBound and: rightBound
	"Answer true if there are only one root
	in the interval (leftBound, rightBound]."

	| count upper lower |
	self sturmComputed
		ifFalse: [(upper _ self upperBoundNumberOfRootsBetween: leftBound and: rightBound) < 2
					ifTrue: [^ false].
				(upper even and: [self heuristicDetectOneRootBetween: leftBound and: rightBound])
					ifTrue: [^ true].
				lower _ self lowerBoundNumberOfRootsBetween: leftBound and: rightBound.
				lower > 1 ifTrue: [^ true].
				(upper even and: [lower > 0]) ifTrue: [^ true].
				Transcript show: upper printString, ' - ', lower printString, ' - '].

	count _ self numberOfRootsBetween: leftBound and: rightBound.
	Transcript show: count printString; cr.
	^ count > 1! !

!AlgebraicPolynomialRootFinder methodsFor: 'couting roots' stamp: 'len 11/18/97 00:53'!
numberOfNegativeRoots
	"Answer the number of negative roots."

	| fix |
	fix _ (self polynomial valueAt: 0) = 0 ifTrue: [1] ifFalse: [0].
	^ (self numberOfRootsBetween: self bigBounds first and: 0) - fix! !

!AlgebraicPolynomialRootFinder methodsFor: 'couting roots' stamp: 'len 11/18/97 00:52'!
numberOfPositiveRoots
	"Answer the number of positive roots."

	^ self numberOfRootsBetween: 0 and: self bigBounds last! !

!AlgebraicPolynomialRootFinder methodsFor: 'couting roots' stamp: 'len 9/5/97 01:11'!
numberOfRoots
	"Answer the number of real roots of the receiver."

	| interval |
	interval _ self bigBounds.
	^ self numberOfRootsBetween: interval first and: interval last! !

!AlgebraicPolynomialRootFinder methodsFor: 'couting roots' stamp: 'len 12/13/97 04:40'!
numberOfRootsBetween: leftBound and: rightBound
	"Answer the number of real roots in the left
	open interval (leftBound, rightBound]."

	| leftSignChanges rightSignChanges |

	leftSignChanges _ 0.
	(self sturm collect: [ :each | (each valueAt: leftBound) sign])
		inject: 0 into: [ :lastSign :each |
			(lastSign ~= each and: [each ~= 0])
				ifTrue: [leftSignChanges _ leftSignChanges + 1].
			each].

	rightSignChanges _ 0.
	(self sturm collect: [ :each | (each valueAt: rightBound) sign])
		inject: 0 into: [ :lastSign :each |
			(lastSign ~= each and: [each ~= 0])
				ifTrue: [rightSignChanges _ rightSignChanges + 1].
			each].

	^ leftSignChanges - rightSignChanges! !

!AlgebraicPolynomialRootFinder methodsFor: 'couting roots' stamp: 'len 11/18/97 00:49'!
upperBoundNumberOfRoots
	"Answer an upper bound for the number of real roots of the receiver."

	| interval |
	interval _ self bigBounds.
	^ self upperBoundNumberOfRootsBetween: interval first and: interval last! !

!AlgebraicPolynomialRootFinder methodsFor: 'couting roots' stamp: 'len 11/18/97 00:48'!
upperBoundNumberOfRootsBetween: leftBound and: rightBound
	"Answer an upper bound for the number of real roots
	in the open interval (leftBound, rightBound)."

	| leftSignChanges rightSignChanges |

	leftSignChanges _ 0.
	(self fourier collect: [ :each | (each valueAt: leftBound) sign])
		inject: 0 into: [ :lastSign :each |
			(lastSign ~= each and: [each ~= 0])
				ifTrue: [leftSignChanges _ leftSignChanges + 1].
			each].

	rightSignChanges _ 0.
	(self fourier collect: [ :each | (each valueAt: rightBound) sign])
		inject: 0 into: [ :lastSign :each |
			(lastSign ~= each and: [each ~= 0])
				ifTrue: [rightSignChanges _ rightSignChanges + 1].
			each].

	^ leftSignChanges - rightSignChanges! !

!AlgebraicPolynomialRootFinder methodsFor: 'refining roots' stamp: 'len 8/28/97 02:02'!
error
	"Answer the maximun current error in the
	rational approximation of the roots."

	| error |
	error _ 0.
	self roots do: [ :each | error _ error max: each error].
	^ error asFloat! !

!AlgebraicPolynomialRootFinder methodsFor: 'refining roots' stamp: 'len 8/28/97 02:07'!
refineRoot: anInteger
	"Refine the rational bounds of the anInteger-th root."

	(self roots at: anInteger) refine! !

!AlgebraicPolynomialRootFinder methodsFor: 'refining roots' stamp: 'len 8/28/97 02:12'!
refineRoot: anInteger toError: aNumber
	"Refine the anInteger-th root of the receiver up
	to get an approximation error < aNumber."

	(self roots at: anInteger) refineToError: aNumber! !

!AlgebraicPolynomialRootFinder methodsFor: 'refining roots' stamp: 'len 8/28/97 02:08'!
refineRoots
	"Refine the roots approximation intervals."

	self roots do: [ :each | each refine]! !

!AlgebraicPolynomialRootFinder methodsFor: 'refining roots' stamp: 'len 8/28/97 02:11'!
refineRootsToError: aNumber
	"Refine the roots of the receiver up to get an
	approximation error < aNumber."

	self roots do: [ :each | each refineToError: aNumber]! !

!AlgebraicPolynomialRootFinder methodsFor: 'operations' stamp: 'len 9/5/97 01:11'!
separateRoots
	"Separate the roots in intervals each of them including an isolated root."

	| bounds |
	bounds _ self bigBounds.
	self separateRootsBetween: bounds first and: bounds last! !

!AlgebraicPolynomialRootFinder methodsFor: 'operations' stamp: 'len 8/23/97 18:49'!
separateRootsBetween: leftBound and: rightBound
	"Separate the roots in the real interval given by the arguments."

	self privateSeparateRootsBetween: leftBound and: rightBound.
	self done: true! !

!AlgebraicPolynomialRootFinder methodsFor: 'private' stamp: 'len 11/7/97 06:30'!
bigBounds
	"Compute and answer a first estimation of
	an interval containing all the real roots."

	| bound |
	bound _ self polynomial norm1 / self polynomial leadingCoefficient.
	bound _ bound max: 1.
	^ Array with: bound negated with: bound! !

!AlgebraicPolynomialRootFinder methodsFor: 'private' stamp: 'len 1/27/98 23:58'!
computeFourier
	"Compute the Budan-Fourier sequence for the polynomial of the receiver."

	| f sequence |
	f _ self polynomial.
	sequence _ (OrderedCollection new: f degree + 1) add: f; yourself.
	f degree timesRepeat: [sequence add: (f _ f derivative)].
	self fourier: sequence! !

!AlgebraicPolynomialRootFinder methodsFor: 'private' stamp: 'len 1/27/98 23:59'!
computeSturm
	"Compute a sturmian sequence for the receiver."

	| f g r sequence |
	"Transcript show: 'computing sturm...'; cr."
	f _ self polynomial.
	g _ f derivative.
	sequence _ (OrderedCollection new: f degree + 1) add: f; add: g; yourself.
	[g degree > 0] whileTrue: [
		r _ sequence add: (f \\ g) negated.
		f _ g.
		g _ r].
	self sturm: sequence! !

!AlgebraicPolynomialRootFinder methodsFor: 'private' stamp: 'len 11/18/97 02:46'!
heuristicDetectOneRootBetween: leftBound and: rightBound

	| first |
	first _ self polynomial valueAt: leftBound.
	2 to: 10 do: [ :each |
		first ~= (self polynomial valueAt: (rightBound - leftBound) / each) sign
			ifTrue: [^ true]].
	^ false! !

!AlgebraicPolynomialRootFinder methodsFor: 'private' stamp: 'len 1/30/98 01:04'!
privateSeparateRootsBetween: leftBound and: rightBound
	"Iterate in the process of separate roots."

	| r mid |

	(r _ self numberOfRootsBetween: leftBound and: rightBound) = 0
		ifTrue: [^ self].

	r = 1 ifTrue: [
		self privateRoots add:
			(AlgebraicNumber
				polynomial: self polynomial
				leftBound: leftBound
				rightBound: rightBound).
		^ self].

	mid _ leftBound + rightBound / 2.
	self separateRootsBetween: leftBound and: mid.
	self separateRootsBetween: mid and: rightBound! !

!AlgebraicPolynomialRootFinder methodsFor: 'private' stamp: 'len 11/18/97 02:05'!
sturmComputed
	"Answer true if the Sturm sequence has been computed."

	^ false
	"^ sturm notNil"! !


!PolynomialRootFinder class methodsFor: 'instance creation' stamp: 'len 11/6/97 21:11'!
polynomial: aPolynomial
	"Answer a new instance of the receiver to find the roots of aPolynomial."

	^ self new polynomial: aPolynomial! !


!PolynomialRootFunction commentStamp: '<historical>' prior: 0!
My instances are polynomial root functions. Each of my instances is defined by an integer index and a set of rational multivariate polynomials. For instance, the PolynomialRootFunction with index k and polynomial f of n+1 indeterminates, represent the continious real function going from a connected subset of R^n (a semialgebraic set) to R and whose value at (a1,...,an) is the k-th real root of f(a1,...,an, x) as univariate polynomial in x. A PolynomialRootFunction with two or more defining polynomials is equivalent to the one defined by the product of all the polynomials.

For an example try this:
	| x y z f |
	x _ Polynomial x.
	y _ Polynomial y.
	z _ Polynomial z.
	f _ PolynomialRootFunction polynomial: x squared + y squared + z squared - 8 index: 1.
	(0 to: 2) collect: [ :one |
		(0 to: 2) collect: [ :two | f valueAt: (one, two)]].
!

!PolynomialRootFunction methodsFor: 'accessing-private' stamp: 'len 12/14/97 21:11'!
index: anInteger
	index _ anInteger! !

!PolynomialRootFunction methodsFor: 'accessing-private' stamp: 'len 12/14/97 21:10'!
polynomials: aPolynomialSet
	polynomials _ aPolynomialSet! !

!PolynomialRootFunction methodsFor: 'accessing' stamp: 'len 12/14/97 21:12'!
index
	"Answer the index of the receiver."

	^ index! !

!PolynomialRootFunction methodsFor: 'accessing' stamp: 'len 12/16/97 20:40'!
polynomial
	"Answer the polynomial of the receiver."

	| answer |
	self polynomials do: [ :each |
		answer _ answer isNil ifTrue: [each] ifFalse: [answer * each]].
	^ answer! !

!PolynomialRootFunction methodsFor: 'accessing' stamp: 'len 12/14/97 21:11'!
polynomials
	"Answer the polynomial set of the receiver."

	^ polynomials! !

!PolynomialRootFunction methodsFor: 'operations' stamp: 'len 2/13/98 21:02'!
valueAt: aTuple
	"Answer the value of the receiver at the argument."

	| roots f polys |
	roots _ Set new.
	polys _ Set new.
	self polynomials do: [ :each |
		f _ (each valueAt: (aTuple, Polynomial x))
				mapCoefficients: [ :coeff |
					coeff isAlgebraic ifTrue: [coeff asRational] ifFalse: [coeff]].
		polys do: [ :some | f _ f // (f gcd: some)].
		roots addAll: (AlgebraicPolynomialRootFinder polynomial: f) roots.
		polys add: f].
	^ roots asSortedCollection at: self index! !


!PolynomialRootFunction class methodsFor: 'instance creation' stamp: 'len 12/14/97 21:51'!
polynomial: aPolynomial index: anInteger
	"Answer a new instance of the receiver representing the
	anInteger-th root function for the polynomial aPolynomial."

	^ self polynomials: (PolynomialSet new add: aPolynomial; yourself) index: anInteger! !

!PolynomialRootFunction class methodsFor: 'instance creation' stamp: 'len 12/14/97 21:50'!
polynomials: aPolynomialSet index: anInteger
	"Answer a new instance of the receiver representing the
	anInteger-th root function for the polynomials in aPolynomialSet."

	^ self new polynomials: aPolynomialSet; index: anInteger! !


!PolynomialSet commentStamp: '<historical>' prior: 0!
My instances are ordered sets of polynomials.

For an example try this:
	PolynomialSet new
		add: (Polynomial continuantOfOrder: 2);
		add: (Polynomial continuantOfOrder: 3);
		yourself.
!

!PolynomialSet methodsFor: 'initialization' stamp: 'len 10/18/97 23:42'!
initialize
	self contents: OrderedCollection new! !

!PolynomialSet methodsFor: 'accessing-private' stamp: 'len 10/18/97 19:13'!
contents
	^ contents! !

!PolynomialSet methodsFor: 'accessing-private' stamp: 'len 10/18/97 19:13'!
contents: aCollection
	contents _ aCollection! !

!PolynomialSet methodsFor: 'accessing' stamp: 'len 2/13/98 21:03'!
add: aPolynomial
	"Add the argument to the receiver. Answer the argument."

	(aPolynomial isNull or: [self includes: aPolynomial])
		ifFalse: [self contents add: aPolynomial].
	^ aPolynomial! !

!PolynomialSet methodsFor: 'accessing' stamp: 'len 10/18/97 20:01'!
addAll: aCollection
	"Add the elements in the argument to the receiver. Answer the argument."

	aCollection do: [ :each | self add: each].
	^ aCollection! !

!PolynomialSet methodsFor: 'accessing' stamp: 'len 10/18/97 23:43'!
at: anInteger
	"Answer the anInteger-th element of the receiver."

	^ self contents at: anInteger! !

!PolynomialSet methodsFor: 'accessing' stamp: 'len 10/23/97 21:25'!
first
	"Answer the first polynomial of the receiver."

	^ self at: 1! !

!PolynomialSet methodsFor: 'accessing' stamp: 'len 10/23/97 22:20'!
indeterminates
	"Answer the indeterminates of the receiver."

	| answer |
	answer _ Set new.
	self do: [ :each | answer addAll: each indeterminates].
	^ answer! !

!PolynomialSet methodsFor: 'accessing' stamp: 'len 10/20/97 00:15'!
indexOf: aPolynomial
	"Answer the index of the argument in the receiver."

	| answer |
	answer _ 1.
	self do: [ :each |
		each = aPolynomial ifTrue: [^ answer].
		answer _ answer + 1].
	self errorNotFound! !

!PolynomialSet methodsFor: 'accessing' stamp: 'len 10/18/97 23:06'!
size
	"Answer the size of the receiver."

	^ self contents size! !

!PolynomialSet methodsFor: 'enumerating' stamp: 'len 10/18/97 19:43'!
collect: aBlock
	"Answer a copy of the receiver with the elements mapped by aBlock."

	| answer |
	answer _ self class new.
	self do: [ :each | answer add: (aBlock value: each)].
	^ answer! !

!PolynomialSet methodsFor: 'enumerating' stamp: 'len 2/7/98 19:15'!
detect: aBlock ifNone: exceptionBlock 
	"Evaluate aBlock with each of the receiver's elements as the argument. 
	Answer the first element for which aBlock evaluates to true. If none 
	evaluate to true, then evaluate the argument, exceptionBlock."

	self do: [:each | (aBlock value: each) ifTrue: [^each]].
	^exceptionBlock value! !

!PolynomialSet methodsFor: 'enumerating' stamp: 'len 10/18/97 19:16'!
do: aBlock
	"Enumerate the elements of the receiver."

	self contents do: aBlock! !

!PolynomialSet methodsFor: 'enumerating' stamp: 'len 10/18/97 20:12'!
select: aBlock
	"Answer the subset of the receiver satistying aBlock."

	| answer |
	answer _ self class new.
	self do: [ :each | (aBlock value: each) ifTrue: [answer add: each]].
	^ answer! !

!PolynomialSet methodsFor: 'converting' stamp: 'len 1/30/98 01:22'!
asTuple
	"Convert the receiver to a Tuple."

	| answer |
	answer _ Tuple dimension: self size.
	1 to: self size do: [ :each |
		answer at: each put: (self at: each)].
	^ answer! !

!PolynomialSet methodsFor: 'testing' stamp: 'len 10/18/97 23:59'!
includes: aPolynomial
	"Answer true if the receiver includes the argument."

	self do: [ :each | each = aPolynomial ifTrue: [^ true]].
	^ false! !

!PolynomialSet methodsFor: 'testing' stamp: 'len 10/22/97 00:32'!
isEmpty
	"Answer true if all the receiver is empty."

	self do: [ :each | ^ false].
	^ true! !

!PolynomialSet methodsFor: 'testing' stamp: 'len 10/22/97 00:31'!
isNull
	"Answer true if all the elements of the receiver are null."

	self do: [ :each | each isNull ifFalse: [^ false]].
	^ true! !

!PolynomialSet methodsFor: 'copying' stamp: 'len 1/30/98 01:23'!
copy
	"Answer a copy of the receiver."

	^ self class basicNew contents: self contents copy ! !

!PolynomialSet methodsFor: 'printing' stamp: 'len 10/18/97 21:11'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	| first |
	aStream nextPut: ${.
	first _ true.
	self do: [ :each |
		first ifFalse: [aStream nextPutAll: ', '].
		aStream print: each.
		first _ false].
	aStream nextPut: $}! !


!PolynomialSet class methodsFor: 'instance creation' stamp: 'len 10/18/97 19:14'!
new
	^ super new initialize! !


!PositionableStream methodsFor: 'accessing' stamp: 'len 11/24/97 20:44'!
nextLine
	"Answer the next line of the receiver. (line delimiters are lf, cr or crlf)."

	| answer char cr lf |
	self atEnd ifTrue: [^ nil].
	cr _ Character cr.
	lf _ Character linefeed.
	answer _ WriteStream with: ''.
	[self atEnd] whileFalse: [
		char _ self next.
		(char = lf or: [char = cr])
			ifTrue: [(char = cr and: [self peek = lf]) ifTrue: [self next].
					^ answer contents].
		answer nextPut: char].
	^ answer contents! !


!QuantifiedSentence commentStamp: '<historical>' prior: 0!
My instances are Tarski sentences represented by a list of quantifiers (prefix) and by the sentence subject of the quantification (matrix).

For an example try this:
	| x y |
	x _ Polynomial x.
	y _ Polynomial y.
	(QuantifiedSentence matrix: (y squared gneq: x))
		add: (ExistentialQuantifier indeterminate: 1);
		add: (UniversalQuantifier indeterminate: 2);
		yourself.

Tarski sentences can be tested for truth (just sending the message #truth). The algorithm uses the mechinery of Cylindrical Algebraic Decomposition (CAD) of R^n and Semialgebraic Sets. and has a very bad time complexity, but it still is useful in small examples.
!

!QuantifiedSentence methodsFor: 'initialization' stamp: 'len 2/7/98 15:26'!
initialize
	self prefix: OrderedCollection new! !

!QuantifiedSentence methodsFor: 'accessing-private' stamp: 'len 12/19/97 21:30'!
matrix: anObject
	matrix _ anObject! !

!QuantifiedSentence methodsFor: 'accessing-private' stamp: 'len 12/19/97 21:30'!
prefix: aCollection
	prefix _ aCollection! !

!QuantifiedSentence methodsFor: 'accessing' stamp: 'len 2/6/98 12:33'!
add: aQuantifier
	"Add the quantifier aQuantifier to the receiver. Answer aQuantifier."

	^ self prefix add: aQuantifier! !

!QuantifiedSentence methodsFor: 'accessing' stamp: 'len 12/31/97 02:46'!
bounded
	"Answer the collection of bounded indeterminates."

	| answer |
	answer _ self matrix bounded.
	self prefix do: [ :each | answer add: each indeterminate].
	^ answer! !

!QuantifiedSentence methodsFor: 'accessing' stamp: 'len 12/31/97 02:45'!
free
	"Answer the collection of free indeterminates."

	| answer |
	answer _ self indeterminates.
	self bounded do: [ :each | answer remove: each ifAbsent: []].
	^ answer! !

!QuantifiedSentence methodsFor: 'accessing' stamp: 'len 12/19/97 22:00'!
indeterminates
	"Answer the indeterminates set of the receiver."

	| answer |
	answer _ self matrix indeterminates.
	self prefix do: [ :each | answer add: each indeterminate].
	^ answer! !

!QuantifiedSentence methodsFor: 'accessing' stamp: 'len 12/21/97 21:03'!
matrix
	"Answer the matrix of the receiver: the sentence being quantified."

	^ matrix! !

!QuantifiedSentence methodsFor: 'accessing' stamp: 'len 12/19/97 21:46'!
polynomials
	"Answer the polynomial set of the receiver."

	^ self matrix polynomials! !

!QuantifiedSentence methodsFor: 'accessing' stamp: 'len 12/21/97 21:02'!
prefix
	"Answer the prefix of the receiver: a collection with quantifiers."

	^ prefix! !

!QuantifiedSentence methodsFor: 'accessing' stamp: 'len 2/7/98 19:16'!
truth
	"Answer the truth value of the receiver, true or false."

	| prenex cad |
	prenex _ self prenex resorted.
	cad _ SemialgebraicSet cad: prenex polynomials.
	^ prenex truthRestrictedTo: cad! !

!QuantifiedSentence methodsFor: 'arithmetic' stamp: 'len 12/21/97 21:09'!
& anObject
	"Answer the conjunction of the receiver with the argument."

	^ ConjunctionConnective left: self right: anObject! !

!QuantifiedSentence methodsFor: 'arithmetic' stamp: 'len 12/21/97 21:09'!
-> anObject
	"Answer the implication of the argument from the receiver."

	^ ImplicationConnective left: self right: anObject! !

!QuantifiedSentence methodsFor: 'arithmetic' stamp: 'len 12/21/97 21:24'!
exists: anInteger
	"Answer the quantification of the reciever by the
	existential quantifier in the anInteger-th indeterminate."

	^ self copy add: (Quantifier exists: anInteger); yourself! !

!QuantifiedSentence methodsFor: 'arithmetic' stamp: 'len 2/6/98 12:32'!
forAll: anInteger
	"Answer the quantification of the reciever by the
	universal quantifier in the anInteger-th indeterminate."

	^ self copy add: (Quantifier forAll: anInteger); yourself! !

!QuantifiedSentence methodsFor: 'arithmetic' stamp: 'len 12/21/97 21:10'!
not
	"Answer the negation of the receiver."

	^ self class prefix: (self prefix collect: [ :each | each not]) matrix: self matrix not! !

!QuantifiedSentence methodsFor: 'arithmetic' stamp: 'len 12/21/97 21:09'!
| anObject
	"Answer the disjunction of the receiver with the argument."

	^ DisjunctionConnective left: self right: anObject! !

!QuantifiedSentence methodsFor: 'operations' stamp: 'len 12/26/97 18:47'!
normalized
	"Answer a copy of the receiver with the indeterminates renamed
	such that the same indeterminate does not ocur as free and bound."

	^ self class prefix: self prefix matrix: self matrix normalized! !

!QuantifiedSentence methodsFor: 'operations' stamp: 'len 12/31/97 02:26'!
prenex
	"Answer the prenex form of the receiver."

	^ self reduced normalized privatePrenex! !

!QuantifiedSentence methodsFor: 'operations' stamp: 'len 12/31/97 02:52'!
reduced
	"Answer a copy of the receiver with the redundant quantifiers removed."

	| indets quantifiers reducedMatrix |
	reducedMatrix _ self matrix reduced.
	indets _ reducedMatrix indeterminates.
	quantifiers _ self prefix select: [ :each | indets includes: each indeterminate].
	^ quantifiers isEmpty
		ifTrue: [reducedMatrix]
		ifFalse: [self class prefix: quantifiers matrix: reducedMatrix]! !

!QuantifiedSentence methodsFor: 'operations' stamp: 'len 12/26/97 18:52'!
rename: anInteger to: anotherInteger
	"Rename the anInteger-th indeterminate of the receiver to anotherInteger."

	self prefix do: [ :each | each rename: anInteger to: anotherInteger].
	self matrix rename: anInteger to: anotherInteger! !

!QuantifiedSentence methodsFor: 'operations' stamp: 'len 2/7/98 19:04'!
resorted
	"Answer a copy of the receiver with the indeterminates resorted and renamed."

	| answer last |
	answer _ self copy.
	last _ 0.
	self prefix do: [ :each | last _ each indeterminate max: last].
	last _ last + 1.
	1 to: self prefix size do: [ :each |
		answer rename: (self prefix at: each) indeterminate to: last + each].
	1 to: self prefix size do: [ :each |
		answer rename: last + each to: each].
	^ answer! !

!QuantifiedSentence methodsFor: 'testing' stamp: 'len 12/21/97 20:42'!
isQuantifierFree
	"Answer true if the receiver is a quantifier-free sentence."

	^ self prefix isEmpty and: [self matrix isQuantifierFree]! !

!QuantifiedSentence methodsFor: 'copying' stamp: 'len 2/14/98 13:31'!
copy
	"Answer a copy of the receiver."

	^ self class
		prefix: (self prefix collect: [ :each | each copy])
		matrix: self matrix copy! !

!QuantifiedSentence methodsFor: 'private' stamp: 'len 12/21/97 20:58'!
defaultNames
	"Answer the default names for the indeterminates."

	^ MonomialLiteral defaultNames! !

!QuantifiedSentence methodsFor: 'private' stamp: 'len 12/31/97 02:25'!
privatePrenex
	"Answer the prenex form of the receiver.
	Assume the receiver is reduced and normalized."

	| mp newPrefix newMatrix |
	mp _ self matrix privatePrenex.
	newPrefix _ self prefix copy addAll: mp prefix; yourself.
	newMatrix _ mp matrix.
	^ self class prefix: newPrefix matrix: newMatrix! !

!QuantifiedSentence methodsFor: 'private' stamp: 'len 2/7/98 18:52'!
truthRestrictedTo: aSemialgebraicSet
	"Answer the truth value of the receiver, true or false,
	when restricted to aSemialgebraicSet. Assume that the
	receiver is in prenex form."

	| sentence quantifier |
	aSemialgebraicSet isEmpty
		ifTrue: [self prefix do: [ :each | each isExistential ifTrue: [^ false]].
				^ true].
	self isQuantifierFree
		ifTrue: [aSemialgebraicSet do: [ :each |
					(self matrix isSolution: each sample) ifFalse: [^ false]].
				^ true].
	sentence _ self class prefix: (self prefix copy removeFirst; yourself) matrix: self matrix.
	quantifier _ self prefix first.
	^ quantifier isExistential
		ifTrue: [(aSemialgebraicSet projectionAt: quantifier indeterminate)
					do: [ :each |
						(sentence truthRestrictedTo: (aSemialgebraicSet cylinderAt: each))
							ifTrue: [^ true]].
				false]
		ifFalse: [(aSemialgebraicSet projectionAt: quantifier indeterminate)
					do: [ :each |
						(sentence truthRestrictedTo: (aSemialgebraicSet cylinderAt: each))
							ifFalse: [^ false]].
				true]! !

!QuantifiedSentence methodsFor: 'printing' stamp: 'len 12/21/97 21:18'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	self prefix do: [ :each | each printOn: aStream].
	aStream nextPut: $[; print: self matrix; nextPut: $]! !


!QuantifiedSentence class methodsFor: 'instance creation' stamp: 'len 2/5/98 20:29'!
matrix: anObject
	"Answer a new instance of the receiver with no
	quantifiers and with the matrix given by the argument."

	^ self new matrix: anObject! !

!QuantifiedSentence class methodsFor: 'instance creation' stamp: 'len 12/19/97 21:32'!
new
	^ super new initialize! !

!QuantifiedSentence class methodsFor: 'instance creation' stamp: 'len 2/5/98 20:32'!
prefix: aCollection matrix: anObject
	"Answer a new instance of the receiver with
	the prefix and matrix given by the arguments."

	| answer |
	answer _ self matrix: anObject.
	answer prefix addAll: aCollection.
	^ answer! !

!QuantifiedSentence class methodsFor: 'instance creation' stamp: 'len 2/5/98 20:32'!
quantifier: aQuantifier matrix: anObject
	"Answer a new instance of the receiver with
	the quantifier and matrix given by the arguments."

	^ self prefix: (Array with: aQuantifier) matrix: anObject! !


!Quantifier commentStamp: '<historical>' prior: 0!
I am an abstract superclass for real quantifiers that are employed in the building of Tarski sentences. My concrete subclases are UniversalQuantifier and ExistentialQuantifier.
!

!Quantifier methodsFor: 'accessing-private' stamp: 'len 12/18/97 20:18'!
indeterminate: anInteger
	indeterminate _ anInteger! !

!Quantifier methodsFor: 'accessing' stamp: 'len 12/18/97 20:35'!
indeterminate
	"Answer the quantified indeterminate of the reiceiver."

	^ indeterminate! !

!Quantifier methodsFor: 'operations' stamp: 'len 12/26/97 18:53'!
rename: anInteger to: anotherInteger
	"Rename the anInteger-th indeterminate of the receiver to anotherInteger."

	self indeterminate = anInteger ifTrue: [self indeterminate: anotherInteger]! !

!Quantifier methodsFor: 'copying' stamp: 'len 2/14/98 13:30'!
copy
	"Answer a copy of the receiver."

	^ self class indeterminate: self indeterminate! !

!Quantifier methodsFor: 'testing' stamp: 'len 2/5/98 21:26'!
isExistential
	"Answer true if the receiver is an existential quantifier."
	^ false! !

!Quantifier methodsFor: 'testing' stamp: 'len 2/5/98 21:27'!
isUniversal
	"Answer true if the receiver is an universal quantifier."
	^ false! !

!Quantifier methodsFor: 'printing' stamp: 'len 12/21/97 20:57'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	self printOn: aStream withNames: MonomialLiteral defaultNames! !

!Quantifier methodsFor: 'printing' stamp: 'len 12/31/97 03:02'!
printOn: aStream withNames: aDictionary
	"Print a representation of the receiver on the stream aStream
	using the indeterminate names from aDictionary."

	self subclassResponsibility! !


!ExistentialQuantifier commentStamp: '<historical>' prior: 0!
My instances are existential quantifiers in one indeterminate.

For an example try:
	ExistentialQuantifier indeterminate: 3.
!

!ExistentialQuantifier methodsFor: 'arithmetic' stamp: 'len 12/21/97 21:13'!
not
	"Answer the negation of the receiver."

	^ UniversalQuantifier indeterminate: self indeterminate! !

!ExistentialQuantifier methodsFor: 'testing' stamp: 'len 2/5/98 21:28'!
isExistential
	"Answer true if the receiver is an existential quantifier."
	^ true! !

!ExistentialQuantifier methodsFor: 'printing' stamp: 'len 12/19/97 21:58'!
printOn: aStream withNames: aDictionary
	"Print a representation of the receiver on the stream aStream
	using the indeterminate names from aDictionary."

	| name |
	name _ aDictionary
				at: self indeterminate
				ifAbsent: ['{x', self indeterminate printString, '}'].
	aStream nextPutAll: '(exists ', name, ')'! !


!Quantifier class methodsFor: 'instance creation' stamp: 'len 12/19/97 21:50'!
exists: anInteger
	"Answer the existential quantifier in the anInteger-th indeterminate."

	^ ExistentialQuantifier indeterminate: anInteger! !

!Quantifier class methodsFor: 'instance creation' stamp: 'len 12/19/97 21:50'!
forAll: anInteger
	"Answer the universal quantifier in the anInteger-th indeterminate."

	^ UniversalQuantifier indeterminate: anInteger! !

!Quantifier class methodsFor: 'instance creation' stamp: 'len 12/19/97 21:35'!
indeterminate: anInteger
	"Answer a new instance of the receiver representing
	the quantifier in the anInteger-th indeterminate."

	^ self new indeterminate: anInteger! !


!RationalFunction commentStamp: '<historical>' prior: 0!
My instances are rational functions in one or many variables.
Each of my instances has a numerator and a denominator, which are keeped 'reduced' in the univariate case (see RationalFunction>>reduced).
RationalFunctions are created by sending to a Polynomial the message #/ with argument anotherPolynomial.

This is an univariate example:
	Polynomial x + 1 / Polynomial x squared.

And this one is an example with many variables:
	Polynomial x + Polynomial y / Polynomial z squared.
!

!RationalFunction methodsFor: 'accessing'!
denominator
	"Answer the denominator."
	^ denominator! !

!RationalFunction methodsFor: 'accessing' stamp: 'len 4/1/98 23:42'!
indeterminates
	"Answer the indeterminates of the receiver."

	^ Set new
		addAll: self numerator indeterminates;
		addAll: self denominator indeterminates;
		yourself! !

!RationalFunction methodsFor: 'accessing'!
numerator
	"Answer the numerator."
	^ numerator! !

!RationalFunction methodsFor: 'arithmetic' stamp: 'len 4/1/98 23:41'!
* anObject
	"Answer the multiplication of the receiver and the argument."

	| g1 g2 newDenominator newNumerator |
	anObject isRationalFunction
		ifFalse: [^ self numerator * anObject / self denominator].
	(self isUnivariate and: [anObject isUnivariate])
		ifTrue: [g1 _ self numerator gcd: anObject denominator.
				g2 _ self denominator gcd: anObject numerator.
				newNumerator _ self numerator // g1 * (anObject numerator // g2).
				newDenominator _ self denominator // g2 * (anObject denominator // g1).
				^ (newDenominator = newDenominator identity or: [newNumerator isNull])
					ifTrue: [newNumerator]
					ifFalse: [self class numerator: newNumerator denominator: newDenominator]].
	^ self class
		numerator: self numerator * anObject numerator
		denominator: self denominator * anObject denominator! !

!RationalFunction methodsFor: 'arithmetic' stamp: 'len 4/1/98 23:59'!
+ anObject
	"Answer the sum of the receiver and the argument."
	| crossProduct rden1 rden2 denGcd crossGcd newDen |

	anObject isRationalFunction
		ifFalse: [^ self numerator + (self denominator * anObject) / self denominator].
	(self isUnivariate and: [anObject isUnivariate])
		ifTrue: [denGcd _ self denominator gcd: anObject denominator.
				rden1  _ self denominator // denGcd.
				rden2 _ anObject denominator // denGcd.
				crossProduct _ self numerator * rden2 + (anObject numerator * rden1).
				crossGcd _ crossProduct gcd: denGcd.
				((newDen _ denGcd // crossGcd * rden1 * rden2) = 1 or: [crossProduct isNull])
					ifTrue: [^ crossProduct // crossGcd].
				^ self class
					numerator: crossProduct // crossGcd
					denominator: newDen].
	^ (self class
		numerator: self numerator * anObject denominator
					+ (self denominator * anObject numerator)
		denominator: self denominator * anObject denominator) reduced! !

!RationalFunction methodsFor: 'arithmetic' stamp: 'len 8/18/97 19:15'!
- anObject
	"Answer the difference of the receiver and the argument."

	^ self + anObject negated! !

!RationalFunction methodsFor: 'arithmetic' stamp: 'len 8/18/97 19:16'!
/ anObject
	"Answer the division of the receiver by the argument."

	^ self * anObject reciprocal! !

!RationalFunction methodsFor: 'arithmetic'!
negated 
	"Answer the additive inverse of the receiver."

	^ self class
		numerator: numerator negated
		denominator: denominator! !

!RationalFunction methodsFor: 'arithmetic' stamp: 'len 10/18/97 02:55'!
reciprocal 
	"Answer the multiplicative inverse of the receiver."

	| mult |
	mult _ self numerator leadingCoefficient reciprocal.
	self numerator isConstant ifTrue: [^ denominator * mult].
	^ self class numerator: denominator * mult denominator: numerator * mult! !

!RationalFunction methodsFor: 'mathematical functions' stamp: 'len 9/1/97 00:45'!
raisedToInteger: anInteger 
	"Answer the receiver raised to the power anInteger
	where the argument must be a kind of Integer."

	^ self class
		numerator: (self numerator raisedToInteger: anInteger)
		denominator: (self denominator raisedToInteger: anInteger)! !

!RationalFunction methodsFor: 'mathematical functions' stamp: 'len 9/1/97 00:45'!
squared
	"Answer the square of the receiver."

	^ self class
		numerator: self numerator squared
		denominator: self denominator squared! !

!RationalFunction methodsFor: 'operations' stamp: 'len 9/4/97 00:24'!
degree
	"Answer the degree of the receiver."

	^ self numerator degree - self denominator degree! !

!RationalFunction methodsFor: 'operations' stamp: 'len 4/2/98 00:00'!
degreeIn: anInteger
	"Answer the degree of the receiver in the anInteger-th indeterminate."

	^ (self numerator degreeIn: anInteger) - (self denominator degreeIn: anInteger)! !

!RationalFunction methodsFor: 'operations' stamp: 'len 9/3/97 23:49'!
derivative
	"Answer the derivative of the receiver."

	| num gcd |
	num _
		self denominator * self numerator derivative
		- (self numerator * self denominator derivative).
	gcd _ self denominator gcd: num.
	^ self class numerator: num // gcd denominator: (self denominator // gcd) squared * gcd! !

!RationalFunction methodsFor: 'operations' stamp: 'len 9/3/97 23:35'!
derivativeOfOrder: anInteger
	"Answer the anInteger-th derivative of the receiver."

	| answer |
	answer _ self.
	anInteger timesRepeat: [answer _ answer derivative].
	^ answer! !

!RationalFunction methodsFor: 'operations' stamp: 'len 9/4/97 00:24'!
valueAt: anObject
	"Answer the result of evaluating the receiver at the argument."

	^ (self numerator valueAt: anObject) / (self denominator valueAt: anObject)! !

!RationalFunction methodsFor: 'comparing' stamp: 'len 4/1/98 23:49'!
= anObject
	"Answer true if the receiver equals the argument."

	^ anObject isRationalFunction
		ifTrue: [self numerator * anObject denominator = (self denominator * anObject numerator)]
		ifFalse: [self denominator * anObject = self numerator]! !

!RationalFunction methodsFor: 'comparing' stamp: 'len 4/1/98 23:49'!
hash
	"Answer the hash value for the receiver."

	^ 0! !

!RationalFunction methodsFor: 'converting' stamp: 'len 8/30/97 01:15'!
adaptFraction: aFraction
	"If I am involved in arithmetic with a Fraction, convert the Fraction."
	^ self class
		numerator: (self numerator adaptFraction: aFraction)
		denominator: self denominator identity! !

!RationalFunction methodsFor: 'converting' stamp: 'len 8/30/97 01:15'!
adaptInteger: anInteger
	"If I am involved in arithmetic with an Integer, convert the Integer."
	^ self class
		numerator: (self numerator adaptInteger: anInteger)
		denominator: self denominator identity! !

!RationalFunction methodsFor: 'converting'!
adaptToFraction
	"If I am involved in arithmetic with a Fraction, do not convert me."
	^self! !

!RationalFunction methodsFor: 'converting'!
adaptToInteger
	"If I am involved in arithmetic with an Integer, do not convert me."
	^self! !

!RationalFunction methodsFor: 'testing' stamp: 'len 9/4/97 00:27'!
isNull
	"Answer true if the receiver is null."

	^ self numerator isNull! !

!RationalFunction methodsFor: 'testing'!
isRationalFunction
	"Answer true if the receiver is a rational function."
	^ true! !

!RationalFunction methodsFor: 'testing' stamp: 'len 4/1/98 23:52'!
isUnivariate
	"Answer true if the receiver is an univariate rational function."
	| nindets dindets |
	nindets _ self numerator indeterminates.
	dindets _ self denominator indeterminates.
	(nindets isEmpty or: [nindets size = 1 and: [nindets includes: 1]])
		ifFalse: [^ false].
	(dindets isEmpty or: [dindets size = 1 and: [dindets includes: 1]])
		ifFalse: [^ false].
	^ true! !

!RationalFunction methodsFor: 'constants' stamp: 'len 7/29/97 23:41'!
identity
	^ self numerator identity! !

!RationalFunction methodsFor: 'constants' stamp: 'len 7/29/97 23:40'!
identityCoefficient
	^ self numerator identityCoefficient! !

!RationalFunction methodsFor: 'constants' stamp: 'len 7/29/97 23:41'!
null
	^ self numerator null! !

!RationalFunction methodsFor: 'constants' stamp: 'len 7/29/97 23:40'!
nullCoefficient
	^ self numerator nullCoefficient! !

!RationalFunction methodsFor: 'private' stamp: 'len 4/1/98 23:55'!
reduced
	"Reduce the receiver dividing the numerator and the denominator
	by them GCD and making the denominator monic."
	| gcd mult num den |
	(num _ self numerator) isNull ifTrue: [^ num].
	den _ self denominator.
	self isUnivariate
		ifTrue: [gcd _ num gcd: den.
				num _ num // gcd.
				den _ den // gcd].
	mult _ den asPolynomial leadingCoefficient reciprocal.
	self numerator: num * mult.
	self denominator: den * mult! !

!RationalFunction methodsFor: 'printing' stamp: 'len 8/23/97 02:03'!
printOn: aStream
	"Print a representation of the reseiver on the stream aStream."

	| string |
	aStream print: self numerator; nextPutAll: ' / '.
	string _ self denominator printString.
	((string includes: $+) or: [string includes: $-])
		ifTrue: [aStream nextPut: $(; print: self denominator; nextPut: $)]
		ifFalse: [aStream print: self denominator]! !

!RationalFunction methodsFor: 'printing' stamp: 'len 9/1/97 00:49'!
printOn: aStream withName: aString
	"Print a representation of the receiver on the stream aStream.
	Use the aString to name the indeterminate."

	| string |
	self numerator printOn: aStream withName: aString.
	aStream nextPutAll: ' / '.
	string _ self denominator printString.
	((string includes: $+) or: [string includes: $-])
		ifTrue: [aStream nextPut: $(.
				self denominator printOn: aStream withName: aString.
				aStream nextPut: $)]
		ifFalse: [self denominator printOn: aStream withName: aString]! !

!RationalFunction methodsFor: 'printing' stamp: 'len 4/1/98 23:57'!
printOn: aStream withNames: aDictionary
	"Print a representation of the receiver on the stream aStream.
	Use aDictionary to name the indeterminates."

	| string |
	self numerator printOn: aStream withNames: aDictionary.
	aStream nextPutAll: ' / '.
	string _ self denominator printString.
	((string includes: $+) or: [string includes: $-])
		ifTrue: [aStream nextPut: $(.
				self denominator printOn: aStream withNames: aDictionary.
				aStream nextPut: $)]
		ifFalse: [self denominator printOn: aStream withNames: aDictionary]! !

!RationalFunction methodsFor: 'accessing-private' stamp: 'len 4/1/98 23:53'!
denominator: aPolynomial
	denominator _ aPolynomial! !

!RationalFunction methodsFor: 'accessing-private' stamp: 'len 4/1/98 23:53'!
numerator: aPolynomial
	numerator _ aPolynomial! !


!RationalFunction class methodsFor: 'instance creation' stamp: 'len 4/1/98 23:58'!
numerator: aPolynomial denominator: anotherPolynomial
	"Answer a new instance of the receiver representing a
	rational function with the given numerator and denominator."

	^ self new numerator: aPolynomial; denominator: anotherPolynomial! !


!RationalPolynomialRootFinder methodsFor: 'operations' stamp: 'len 5/28/1998 20:08'!
separateRoots
	"Separate the roots of the polynomial of the receiver."

	| f tau result |
	result _ OrderedCollection new.
	f _ self polynomial integerPrimitive.
	f last degree ~= 0 ifTrue: [result add: 0. f _ f shift: f last degree negated].

	f last coefficient divisorsDo: [ :each |
		f head coefficient divisorsDo: [ :one |
			tau _ each / one.
			(f valueAt: tau) isNull ifTrue: [result add: tau].
			tau _ tau negated.
			(f valueAt: tau) isNull ifTrue: [result add: tau]]].
	self roots: result.
	self done: true! !


!RealInterval commentStamp: '<historical>' prior: 0!
My instances are real intervals in R^n. Each of my instances is represented as the cartesian product of one dimensional intervals (instances of RealLineInterval).

For an example try this:
	RealInterval new
		add: (RealLineInterval closed: -1 closed: 1);
		add: (RealLineInterval open: 3 open: 4);
		add: (RealLineInterval closed: 0 open: Infinity positive);
		yourself.
!

!RealInterval methodsFor: 'initialization' stamp: 'len 12/13/97 02:50'!
initialize
	self contents: (OrderedCollection new: 3)! !

!RealInterval methodsFor: 'accessing-private' stamp: 'len 12/13/97 02:50'!
contents
	^ contents! !

!RealInterval methodsFor: 'accessing-private' stamp: 'len 12/13/97 02:49'!
contents: aCollection
	contents _ aCollection! !

!RealInterval methodsFor: 'accessing' stamp: 'len 12/13/97 02:53'!
add: anInterval
	"Add the argument to the receiver. Answer the argument."

	^ self contents add: anInterval! !

!RealInterval methodsFor: 'accessing' stamp: 'len 12/13/97 15:21'!
addAll: aCollection
	"Add the elements in the argument to the receiver. Answer the argument."

	aCollection do: [ :each | self add: each].
	^ aCollection! !

!RealInterval methodsFor: 'accessing' stamp: 'len 12/13/97 02:51'!
at: anInteger
	"Answer the anInteger-th component of the receiver."

	^ self contents at: anInteger! !

!RealInterval methodsFor: 'accessing' stamp: 'len 12/21/97 21:39'!
cartesian: anInterval
	"Answer the cartesian product of the receiver by the argument."

	^ self copy addAll: anInterval; yourself! !

!RealInterval methodsFor: 'accessing' stamp: 'len 12/19/97 22:09'!
dimension
	"Answer the dimension of the receiver."

	| answer |
	self do: [ :each | answer _ answer isNil
						ifTrue: [each dimension]
						ifFalse: [answer + each dimension]].
	^ answer! !

!RealInterval methodsFor: 'accessing' stamp: 'len 12/13/97 02:58'!
first
	"Answer the first component of the receiver."

	^ self at: 1! !

!RealInterval methodsFor: 'accessing' stamp: 'len 12/13/97 02:58'!
last
	"Answer the last component of the receiver."

	^ self at: self size! !

!RealInterval methodsFor: 'accessing' stamp: 'len 12/14/97 20:07'!
measure
	"Answer the measure of the receiver."

	| answer |
	self do: [ :each |
		answer _ answer isNil
			ifTrue: [each measure] ifFalse: [answer * each measure]].
	^ answer! !

!RealInterval methodsFor: 'accessing' stamp: 'len 12/19/97 22:07'!
sample
	"Answer a sampel point in the receiver."

	^ Tuple dimension: self size
			fromBlock: [ :each | (self at: each) sample]! !

!RealInterval methodsFor: 'accessing' stamp: 'len 12/13/97 02:51'!
size
	"Answer the size of the receiver."

	^ self contents size! !

!RealInterval methodsFor: 'enumerating' stamp: 'len 12/13/97 02:52'!
do: aBlock
	"Enumerate the components of the receiver."

	self contents do: aBlock! !

!RealInterval methodsFor: 'comparing' stamp: 'len 12/19/97 22:06'!
= anObject
	"Answer true if the receiver equals the argument."

	self size = anObject size ifFalse: [^ false].
	1 to: self size do: [ :each | (self at: each) = (anObject at: each) ifFalse: [^ false]].
	^ true! !

!RealInterval methodsFor: 'comparing' stamp: 'len 12/19/97 22:06'!
hash
	"Answer the hash value of the receiver."

	^ self size = 0
		ifTrue: [self size hash]
		ifFalse: [self size hash + self first hash + self last hash]! !

!RealInterval methodsFor: 'testing' stamp: 'len 12/19/97 22:06'!
includes: anObject
	"Answer true if the receiver includes the argument."

	1 to: self size do: [ :each |
		((self at: each) includes: (anObject at: each)) ifFalse: [^ false]].
	^ true! !

!RealInterval methodsFor: 'testing' stamp: 'len 12/13/97 03:30'!
isBounded
	"Answer true if the receiver is bounded."

	self do: [ :each | each isBounded ifFalse: [^ false]].
	^ true! !

!RealInterval methodsFor: 'testing' stamp: 'len 12/13/97 02:54'!
isClosed
	"Answer true if the receiver is closed."

	self do: [ :each | each isClosed ifFalse: [^ false]].
	^ true! !

!RealInterval methodsFor: 'testing' stamp: 'len 12/13/97 02:54'!
isOpen
	"Answer true if the receiver is open."

	self do: [ :each | each isOpen ifFalse: [^ false]].
	^ true! !

!RealInterval methodsFor: 'testing' stamp: 'len 12/13/97 03:00'!
isRealInterval
	"Answer true if the receiver is a real interval."

	^ true! !

!RealInterval methodsFor: 'printing' stamp: 'len 12/13/97 02:49'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	| first |
	first _ true.
	self do: [ :each |
		first ifFalse: [aStream nextPut: $x].
		each printOn: aStream.
		first _ false]! !


!RealInterval class methodsFor: 'instance creation' stamp: 'len 12/13/97 02:52'!
new
	^ super new initialize! !


!RealLineInterval commentStamp: '<historical>' prior: 0!
My instances are real intervals in the real line. Each of my instances can have finite or infinite and open or closed bounds.

For some examples try this:
	RealLineInterval open: 1 closed: 2.
	RealLineInterval open: 0 open: Infinity positive.
	RealLineInterval closed: -1 closed: 1.
	RealLineInterval open: Infinity negative open: Infinity positive.
!

!RealLineInterval methodsFor: 'initialization' stamp: 'len 12/13/97 03:18'!
setLeftBound: leftBound rightBound: rightBound leftOpen: leftOpenBool rightOpen: rightOpenBool
	left _ leftBound.
	right _ rightBound.
	"If the interval is left-closed or right-closed and two points are
	the same, then the interval is a single point... so it's closed."
	((leftOpenBool & rightOpenBool) not and: [left = right])
		ifTrue: [leftOpen _ false.
				rightOpen _ false]
		ifFalse: [leftOpen _ leftOpenBool.
				rightOpen _ rightOpenBool]! !

!RealLineInterval methodsFor: 'accessing-private' stamp: 'len 12/13/97 03:18'!
left: aNumber
	left _ aNumber! !

!RealLineInterval methodsFor: 'accessing-private' stamp: 'len 12/13/97 02:30'!
leftOpen: aBoolean
	leftOpen _ aBoolean! !

!RealLineInterval methodsFor: 'accessing-private' stamp: 'len 12/13/97 03:21'!
right: aNumber
	right _ aNumber! !

!RealLineInterval methodsFor: 'accessing-private' stamp: 'len 12/13/97 02:32'!
rightOpen: aBoolean
	rightOpen _ aBoolean! !

!RealLineInterval methodsFor: 'accessing' stamp: 'len 12/13/97 15:19'!
cartesian: anInterval
	"Answer the cartesian product of the receiver by the argument."

	| answer |
	answer _ RealInterval new add: self; yourself.
	anInterval do: [ :each | answer add: each].
	^ answer! !

!RealLineInterval methodsFor: 'accessing' stamp: 'len 12/19/97 22:10'!
dimension
	"Answer the dimension of the receiver."

	self isEmpty ifTrue: [^ Infinity negative].
	self left = self right ifTrue: [^ 0].
	^ 1! !

!RealLineInterval methodsFor: 'accessing' stamp: 'len 12/13/97 03:22'!
inf
	"Answer the infimun of the receiver."

	^ self left! !

!RealLineInterval methodsFor: 'accessing' stamp: 'len 12/13/97 03:21'!
left
	"Answer the left bound of the receiver."

	^ left! !

!RealLineInterval methodsFor: 'accessing' stamp: 'len 12/13/97 03:23'!
length
	"Answer the length of the receiver."

	^ self right - self left! !

!RealLineInterval methodsFor: 'accessing' stamp: 'len 12/13/97 03:24'!
max
	"Answer the maximum of the receiver."

	self isRightOpen ifTrue: [^ self error: 'there''s not maximum'].
	^ self right! !

!RealLineInterval methodsFor: 'accessing' stamp: 'len 12/14/97 20:05'!
measure
	"Answer the measure of the receiver."

	^ self right - self left! !

!RealLineInterval methodsFor: 'accessing' stamp: 'len 12/13/97 03:23'!
min
	"Answer the minimum of the receiver."

	self isLeftOpen ifTrue: [^ self error: 'there''s not minimun'].
	^ self left! !

!RealLineInterval methodsFor: 'accessing' stamp: 'len 12/13/97 03:21'!
right
	"Answer the right bound of the receiver."

	^ right! !

!RealLineInterval methodsFor: 'accessing' stamp: 'len 12/15/97 20:56'!
sample
	"Answer a sample point in the receiver."

	self isEmpty ifTrue: [^ self error: 'empty interval'].
	self isLeftClosed ifTrue: [^ Tuple with: self left].
	self isRightClosed ifTrue: [^ Tuple with: self right].
	(self isLeftBounded and: [self isRightBounded])
		ifTrue: [^ Tuple with: self left + self right / 2].
	self isLeftBounded ifTrue: [^ Tuple with: self left + 1].
	self isRightBounded ifTrue: [^ Tuple with: self right - 1].
	^ Tuple with: 0! !

!RealLineInterval methodsFor: 'accessing' stamp: 'len 12/13/97 03:24'!
sup
	"Answer the supremum of the receiver."

	^ self right! !

!RealLineInterval methodsFor: 'arithmetic' stamp: 'len 12/13/97 03:19'!
* anInterval
	"Answer the product of the receiver by the argument."

	| l1l2 l1r2 r1l2 r1r2 |
	l1l2 _ self left * anInterval left.
	l1r2 _ self left * anInterval right.
	r1l2 _ self right * anInterval left.
	r1r2 _ self right * anInterval right.
	^ self copy
		left: ((l1l2 min: l1r2) min: (r1l2 min: r1r2));
		right: ((l1l2 max: l1r2) max: (r1l2 max: r1r2))! !

!RealLineInterval methodsFor: 'arithmetic' stamp: 'len 12/13/97 03:20'!
+ anInterval
	"Answer the sum of the receiver and the argument."

	^ self copy
		left: self left + anInterval left;
		right: self right + anInterval right! !

!RealLineInterval methodsFor: 'arithmetic' stamp: 'len 12/13/97 03:36'!
- anInterval
	"Answer the difference of the receiver and the argument."

	^ self + anInterval negated! !

!RealLineInterval methodsFor: 'arithmetic' stamp: 'len 12/13/97 02:14'!
/ anInterval
	"Answer the quotient of the receiver by the argument."

	^ self * anInterval reciprocal! !

!RealLineInterval methodsFor: 'arithmetic' stamp: 'len 12/13/97 03:20'!
negated
	"Answer the additive inverse of the receiver."

	^ self copy
		right: self left negated;
		left: self right negated;
		leftOpen: self isRightOpen;
		rightOpen: self isLeftOpen! !

!RealLineInterval methodsFor: 'arithmetic' stamp: 'len 12/13/97 03:20'!
reciprocal
	"Answer the multiplicative inverse of the receiver."

	self sign = 0 ifTrue: [^ self error: 'division by zero'].
	^ self copy
		left: self right reciprocal;
		right: self left reciprocal! !

!RealLineInterval methodsFor: 'comparing' stamp: 'len 2/6/98 13:08'!
= anInterval
	"Answer true if the receiver equals the argument."

	^ self left = anInterval left and: [
		self right = anInterval right and: [
			self isLeftOpen = anInterval isLeftOpen and: [
				self isRightOpen = anInterval isRightOpen]]]! !

!RealLineInterval methodsFor: 'comparing' stamp: 'len 2/6/98 12:43'!
hash
	"Answer the hash value for the receiver."

	^ "self left hash + self right hash +" self isLeftOpen hash + self isRightOpen hash! !

!RealLineInterval methodsFor: 'converting' stamp: 'len 12/13/97 02:31'!
close
	"Answer a closed inverval with the same bounds that the receiver."

	self isClosed ifFalse: [^ self copy leftOpen: false; rightOpen: false]! !

!RealLineInterval methodsFor: 'converting' stamp: 'len 12/13/97 02:40'!
closeLeft
	"Answer a closed left interval with the same bounds that the receiver."

	self isLeftClosed ifFalse: [^ self copy leftOpen: false]! !

!RealLineInterval methodsFor: 'converting' stamp: 'len 12/13/97 02:35'!
closeRight
	"Answer a closed right interval with the same bounds that the receiver."

	self isRightClosed ifFalse: [^ self copy rightOpen: false]! !

!RealLineInterval methodsFor: 'converting' stamp: 'len 12/13/97 02:32'!
open
	"Answer an open inverval with the same bounds that the receiver."

	self isOpen ifFalse: [^ self copy leftOpen: true; rightOpen: true]! !

!RealLineInterval methodsFor: 'converting' stamp: 'len 12/13/97 02:38'!
openLeft
	"Answer an open left interval with the same bounds that the receiver."

	self isLeftOpen ifFalse: [^ self copy leftOpen: true]! !

!RealLineInterval methodsFor: 'converting' stamp: 'len 12/13/97 02:39'!
openRight
	"Answer an open right interval with the same bounds that the receiver."

	self isRightOpen ifFalse: [^ self copy rightOpen: true]! !

!RealLineInterval methodsFor: 'testing' stamp: 'len 1/17/98 13:57'!
includes: anObject
	"Answer true if the receiver includes the argument."

	anObject isRealInterval ifTrue: [self notYetImplemented].
	anObject isTuple ifTrue: [^ anObject dimension = 1 and: [self includes: anObject first]].
	(self left > anObject or: [self right < anObject])
		ifTrue: [^ false].
	(self left < anObject and: [self right > anObject])
		ifTrue: [^ true].
	((self isLeftClosed and: [anObject = self left])
	or: [self isRightClosed and: [anObject = self right]])
		ifTrue: [^ true].
	^ false! !

!RealLineInterval methodsFor: 'testing' stamp: 'len 12/13/97 03:29'!
isBounded
	"Answer true if the receiver is bounded."

	^ self isLeftBounded and: [self isRightBounded]! !

!RealLineInterval methodsFor: 'testing' stamp: 'len 12/13/97 02:36'!
isClosed
	"Answer true if the receiver is closed."

	^ self isLeftClosed and: [self isRightClosed]! !

!RealLineInterval methodsFor: 'testing' stamp: 'len 12/13/97 03:23'!
isEmpty
	"Answer true if the receiver is empty."

	^ self isLeftBounded
		ifTrue: [self right < self left]
		ifFalse: [self left > self right]! !

!RealLineInterval methodsFor: 'testing' stamp: 'len 12/13/97 02:14'!
isHalfOpen
	"Answer true if the receiver is hald-open."

	^ self isClosed not and: [self isOpen not]! !

!RealLineInterval methodsFor: 'testing' stamp: 'len 12/13/97 02:23'!
isLeftBounded
	"Answer true if the receiver is left bounded."

	^ self left isInfinity not! !

!RealLineInterval methodsFor: 'testing' stamp: 'len 12/13/97 02:33'!
isLeftClosed
	"Answer true if the receiver is left closed."

	^ self isLeftOpen not! !

!RealLineInterval methodsFor: 'testing' stamp: 'len 12/13/97 02:36'!
isLeftOpen
	"Answer true if the receiver is left open."

	^ leftOpen! !

!RealLineInterval methodsFor: 'testing' stamp: 'len 12/13/97 02:15'!
isNull
	"Answer true if the receiver is null."

	^ self includes: 0! !

!RealLineInterval methodsFor: 'testing' stamp: 'len 12/13/97 02:38'!
isOpen
	"Answer true if the receiver is open."

	^ self isLeftOpen and: [self isRightOpen]! !

!RealLineInterval methodsFor: 'testing' stamp: 'len 12/13/97 02:15'!
isRealInterval
	"Answer true if the receiver is a real interval."

	^ true! !

!RealLineInterval methodsFor: 'testing' stamp: 'len 12/13/97 02:24'!
isRightBounded
	"Answer true if the receiver is right bounded."

	^ self right isInfinity not! !

!RealLineInterval methodsFor: 'testing' stamp: 'len 12/13/97 02:35'!
isRightClosed
	"Answer true if the receiver is right closed."

	^ self isRightOpen not! !

!RealLineInterval methodsFor: 'testing' stamp: 'len 12/13/97 02:37'!
isRightOpen
	"Answer true if the receiver is open right."

	^ rightOpen! !

!RealLineInterval methodsFor: 'testing' stamp: 'len 2/9/98 23:32'!
overlaps: anInterval
	"Answer true if the receiver overlaps the argument."

	^ (self intersect: anInterval) isEmpty not! !

!RealLineInterval methodsFor: 'testing' stamp: 'len 12/13/97 03:23'!
sign
	"Answer 1 if the receiver is greater than 0, -1 if less than 0, else 0."

	self left > 0 ifTrue: [^ 1].
	self right < 0 ifTrue: [^ -1].
	^ 0! !

!RealLineInterval methodsFor: 'constants' stamp: 'len 12/13/97 03:20'!
identity
	"Answer the identity element for the receiver."

	^ self copy left: 1; right: 1! !

!RealLineInterval methodsFor: 'constants' stamp: 'len 12/13/97 03:20'!
null
	"Answer the null element for the receiver."

	^ self copy left: 0; right: 0! !

!RealLineInterval methodsFor: 'printing' stamp: 'len 12/13/97 03:23'!
printOn: aStream
	"Print a representation of the receiver in the stream aStream."

	aStream
		nextPut: (self isLeftOpen ifTrue: [ $( ] ifFalse: [ $[ ]);
		print: self left;
		nextPutAll: ', ';
		print: self right;
		nextPut: (self isRightOpen ifTrue: [ $) ] ifFalse: [ $] ])! !


!RealLineInterval class methodsFor: 'instance creation' stamp: 'len 12/13/97 02:29'!
closed: left closed: right
	"Answer a new [left, right] interval."

	^ self new setLeftBound: left rightBound: right leftOpen: false rightOpen: false! !

!RealLineInterval class methodsFor: 'instance creation' stamp: 'len 12/13/97 02:30'!
closed: left open: right
	"Answer a new [left, right) interval."

	^ self new setLeftBound: left rightBound: right leftOpen: false rightOpen: true! !

!RealLineInterval class methodsFor: 'instance creation' stamp: 'len 12/13/97 02:30'!
open: left closed: right
	"Answer a new (left, right] interval."

	^ self new setLeftBound: left rightBound: right leftOpen: true rightOpen: false! !

!RealLineInterval class methodsFor: 'instance creation' stamp: 'len 12/13/97 02:30'!
open: left open: right
	"Answer a new (left, right) interval."

	^ self new setLeftBound: left rightBound: right leftOpen: true rightOpen: true! !


!SemialgebraicCell commentStamp: '<historical>' prior: 0!
My instances are components of a Cell Complex of R^n, where n>1. For the case n=1 SemialgebraicLineCell is used. (See the comments in the class SemialgebraicSet and CylindricalAlgebraicDecomposition).
Each SemialgebraicCell in R^n is represented as the extension of a SemialgebraicCell or SemialgebraicLineCell in R^{n-1}.
!

!SemialgebraicCell methodsFor: 'accessing-private' stamp: 'len 12/14/97 21:33'!
left
	^ left! !

!SemialgebraicCell methodsFor: 'accessing-private' stamp: 'len 12/14/97 21:33'!
left: anObject
	left _ anObject! !

!SemialgebraicCell methodsFor: 'accessing-private' stamp: 'len 12/14/97 20:59'!
projection: aCell
	projection _ aCell! !

!SemialgebraicCell methodsFor: 'accessing-private' stamp: 'len 12/14/97 21:33'!
right
	^ right! !

!SemialgebraicCell methodsFor: 'accessing-private' stamp: 'len 12/14/97 21:33'!
right: anObject
	right _ anObject! !

!SemialgebraicCell methodsFor: 'accessing' stamp: 'len 1/17/98 14:26'!
boundary
	"Answer the boundary of the receiver."

"	| answer |
	answer _ SemialgebraicSet new.
	self projection boundary do: [ :each |
		answer
			add: (self class projection: each between: self left and: self left);
			add: (self class projection: each between: self left and: self right);
			add: (self class projection: each between: self right and: self right)].
	answer
		add: (self class projection: self projection between: self left and: self left);
		add: (self class projection: self projection between: self right and: self right).
	^ answer"
	self notYetImplemented! !

!SemialgebraicCell methodsFor: 'accessing' stamp: 'len 1/17/98 14:22'!
boundsAt: aTuple
	"Answer the bounds of the last component of the receiver
	when the first components are aTuple."

	| lbound rbound |
	lbound _ (self left isInfinity or: [self left isNumber])
		ifTrue: [self left]
		ifFalse: [self left valueAt: aTuple].
	rbound _ (self right isInfinity or: [self right isNumber])
		ifTrue: [self right]
		ifFalse: [self right valueAt: aTuple].
	^ SemialgebraicLineCell between: lbound and: rbound! !

!SemialgebraicCell methodsFor: 'accessing' stamp: 'len 1/8/98 20:28'!
closure
	"Answer the closure of the receiver."

	^ self boundary copy add: self; yourself! !

!SemialgebraicCell methodsFor: 'accessing' stamp: 'len 12/19/97 22:05'!
dimension
	"Answer the dimension of the receiver."

	^ self left = self right
		ifTrue: [self projection dimension] ifFalse: [self projection dimension + 1]! !

!SemialgebraicCell methodsFor: 'accessing' stamp: 'len 1/16/98 21:58'!
interior
	"Answer the interior of the receiver."

	^ self closure copyWithoutAll: self boundary! !

!SemialgebraicCell methodsFor: 'accessing' stamp: 'len 1/17/98 13:49'!
polynomials
	"Answer the polynomials defining the receiver."

	| answer |
	answer _ self projection polynomials.
	self left isInfinity ifFalse: [answer addAll: self left polynomials].
	self right isInfinity ifFalse: [answer addAll: self right polynomials].
	^ answer! !

!SemialgebraicCell methodsFor: 'accessing' stamp: 'len 12/14/97 21:01'!
projection
	"Answer the projection of the receiver (all but the last component)."

	^ projection! !

!SemialgebraicCell methodsFor: 'accessing' stamp: 'len 2/6/98 12:50'!
projectionAt: anInteger
	"Answer the first anInteger components of the receiver."

	| projections cell |
	projections _ OrderedCollection with: self.
	cell _ self.
	[(cell _ cell projection) notNil] whileTrue: [projections addFirst: cell].
	^ projections at: anInteger! !

!SemialgebraicCell methodsFor: 'accessing' stamp: 'len 1/17/98 14:23'!
sample
	"Answer a sample point in the receiver."

	| alpha |
	^ (alpha _ self projection sample), (self boundsAt: alpha) sample! !

!SemialgebraicCell methodsFor: 'accessing' stamp: 'len 2/13/98 21:09'!
sentence
	"Answer a quantifier-free defining sentence for the receiver."

	"| answer sample sign sentence |
	sample _ self sample.
	self polynomials do: [ :each |
		sentence _
			(sign _ (each valueAt: sample) sign) = 0
				ifTrue: [each eq: 0]
				ifFalse: [sign = -1 ifTrue: [each lneq: 0] ifFalse: [each gneq: 0]].
		answer _ answer isNil ifTrue: [sentence] ifFalse: [answer & sentence]].
	^ answer"
	self notYetImplemented! !

!SemialgebraicCell methodsFor: 'comparing' stamp: 'len 1/12/98 23:16'!
= anObject
	"Answer true if the receiver equals the argument."

	^ self class == anObject class
		and: [self projection = anObject projection
			and: [self left = anObject left and: [self right = anObject right]]]! !

!SemialgebraicCell methodsFor: 'comparing' stamp: 'len 1/12/98 23:17'!
hash
	"Answer the hash value for the receiver."

	^ self projection hash + self left hash + self right hash! !

!SemialgebraicCell methodsFor: 'testing' stamp: 'len 1/17/98 14:23'!
includes: aTuple
	"Answer true if the receiver includes the argument."

	| pi |
	pi _ aTuple copyFrom: 1 to: aTuple size - 1.
	^ (self projection includes: pi) and: [(self boundsAt: pi) includes: aTuple last]! !

!SemialgebraicCell methodsFor: 'testing' stamp: 'len 12/14/97 22:06'!
isBounded
	"Answer true if the receiver is bounded."

	^ self projection isBounded and: [(self left isInfinity or: [self right isInfinity]) not]! !

!SemialgebraicCell methodsFor: 'testing' stamp: 'len 2/6/98 13:33'!
isCylindricalOver: aCell
	"Answer true if the receiver is cylindrical over aCell."

	^ self = aCell or: [self projection isCylindricalOver: aCell]! !

!SemialgebraicCell methodsFor: 'printing' stamp: 'len 2/6/98 13:04'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	"aStream nextPut: ${; print: self sentence; nextPut: $}"
	aStream print: self sample! !


!SemialgebraicCell class methodsFor: 'instance creation' stamp: 'len 12/14/97 21:45'!
projection: aCell between: leftBound and: rightBound
	"Answer a new instance of the receiver representing the cell
	whose projection is aCell and whose last component is bounded
	by the given bounds."

	^ self new projection: aCell; left: leftBound; right: rightBound! !


!SemialgebraicLineCell commentStamp: '<historical>' prior: 0!
My instances are components of a Cell Complex of R^1. See the comment in the class SemialgebraicCell.
!

!SemialgebraicLineCell methodsFor: 'accessing' stamp: 'len 1/8/98 20:35'!
boundary
	"Answer the boundary of the receiver."

	^ SemialgebraicSet new
		add: (self class between: self left and: self left);
		add: (self class between: self right and: self right);
		yourself! !

!SemialgebraicLineCell methodsFor: 'accessing' stamp: 'len 1/8/98 20:29'!
closure
	"Answer the closure of the receiver."

	^ self boundary copy add: self; yourself! !

!SemialgebraicLineCell methodsFor: 'accessing' stamp: 'len 1/16/98 21:58'!
interior
	"Answer the interior of the receiver."

	^ self closure copyWithoutAll: self boundary! !

!SemialgebraicLineCell methodsFor: 'accessing' stamp: 'len 1/17/98 13:49'!
polynomials
	"Answer the polynomials defining the receiver."

	| answer |
	answer _ Set new.
	self left isInfinity ifFalse: [answer add: self left polynomial].
	self right isInfinity ifFalse: [answer add: self right polynomial].
	^ answer! !

!SemialgebraicLineCell methodsFor: 'accessing' stamp: 'len 2/6/98 12:38'!
projection
	"Answer the projection of the receiver."
	^ nil! !

!SemialgebraicLineCell methodsFor: 'accessing' stamp: 'len 12/19/97 02:29'!
sample
	"Answer a sample point in the receiver."

	self isEmpty ifTrue: [^ self error: 'empty interval'].
	self left = self right ifTrue: [^ Tuple with: self left].
	(self isLeftBounded and: [self isRightBounded])
		ifTrue: [[self left rightBound <= self right leftBound]
					whileFalse: [self left refine. self right refine].
				^ Tuple with: self left rightBound + self right leftBound / 2].
	self isLeftBounded ifTrue: [^ Tuple with: self left rightBound + 1].
	self isRightBounded ifTrue: [^ Tuple with: self right leftBound - 1].
	^ Tuple with: 0! !

!SemialgebraicLineCell methodsFor: 'accessing' stamp: 'len 1/12/98 23:33'!
sentence
	"Answer a quantifier-free defining sentence for the receiver."

	| answer sample sign sentence |
	sample _ self sample.
	self polynomials do: [ :each |
		sentence _
			(sign _ (each valueAt: sample) sign) = 0
				ifTrue: [each eq: 0]
				ifFalse: [sign = -1 ifTrue: [each lneq: 0] ifFalse: [each gneq: 0]].
		answer _ answer isNil ifTrue: [sentence] ifFalse: [answer & sentence]].
	^ answer! !

!SemialgebraicLineCell methodsFor: 'testing' stamp: 'len 2/6/98 13:33'!
isCylindricalOver: aCell
	"Answer true if the receiver is cylindrical over aCell."

	^ self = aCell! !

!SemialgebraicLineCell methodsFor: 'printing' stamp: 'len 2/6/98 13:03'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	"aStream nextPut: ${; print: self sentence; nextPut: $}"
	aStream print: self sample! !


!SemialgebraicLineCell class methodsFor: 'instance creation' stamp: 'len 12/20/97 02:35'!
between: leftBound and: rightBound
	"Answer a new instance of the receiver representing the
	univariate cell which is bounded by the given bounds."

	(leftBound = rightBound or: [leftBound isInfinity and: [rightBound isInfinity]])
		ifTrue: [^ self closed: leftBound closed: rightBound].
	leftBound isInfinity
		ifTrue: [^ self closed: leftBound open: rightBound].
	rightBound isInfinity
		ifTrue: [^ self open: leftBound closed: rightBound].
	^ self open: leftBound open: rightBound! !


!SemialgebraicSet commentStamp: '<historical>' prior: 0!
My instances are semialgebraic sets, i.e. subsets of R^n expressables as finite union and intersection of sets of the form:
	{(x1,...,xn) | sign(f(x1,...,xn)) = s}
where f is a polynomial in R[x1,...,xn] and s is 1, -1 or 0.

Semialgebraic sets are closed under union, intersection, complementation and projection. Furthermore, the boundary and closure of a semialgebraic set is again a semialgebraic set. Semialgebraic sets are the natural generalization of algebraic sets (zeros of polynomials) in such a way to make them be closed under projection.

The implementation is based on the Cylindrical Algebraic Decomposition process. Each SemialgebraicSet is made of an union of SemialgebraicCells (or SemialgebraicLineCells in R^1). For more details on the implementation of semialgebraic sets, take a look at the comment of the class CylindricalAlgebraicDecomposition.

Some examples of semialgebraic sets are:
	open unitary circle in R^2:
		SemialgebraicSet circle.
	unitary circunference in R^2:
		SemialgebraicSet circunference.
!

!SemialgebraicSet methodsFor: 'initialization' stamp: 'len 1/9/98 21:34'!
initialize
	self cells: Set new! !

!SemialgebraicSet methodsFor: 'accessing-private' stamp: 'len 12/14/97 21:46'!
cells: aCollection
	cells _ aCollection! !

!SemialgebraicSet methodsFor: 'accessing' stamp: 'len 1/9/98 21:34'!
add: aCell
	"Add the argument to the cells of the receiver. Answer the argument."

	^ self cells add: aCell! !

!SemialgebraicSet methodsFor: 'accessing' stamp: 'len 12/14/97 21:48'!
addAll: aCollection
	"Add the elements in the argument to the cells of the receiver. Answer the argument."

	aCollection do: [ :each | self add: each].
	^ aCollection! !

!SemialgebraicSet methodsFor: 'accessing' stamp: 'len 1/10/98 00:22'!
boundary
	"Answer the boundary of the receiver."

	self notYetImplemented! !

!SemialgebraicSet methodsFor: 'accessing' stamp: 'len 12/14/97 21:47'!
cells
	"Answer the cells of the receiver."

	^ cells! !

!SemialgebraicSet methodsFor: 'accessing' stamp: 'len 1/8/98 20:33'!
closure
	"Answer the closure of the receiver."

	| answer |
	answer _ self class new.
	self do: [ :each | answer addAll: each closure].
	^ answer! !

!SemialgebraicSet methodsFor: 'accessing' stamp: 'len 2/5/98 20:45'!
cylinderAt: aCell
	"Answer the subset of the receiver cylindrical over aCell."

	^ self select: [ :each | each isCylindricalOver: aCell]! !

!SemialgebraicSet methodsFor: 'accessing' stamp: 'len 1/9/98 21:31'!
graph
	"Answer the connectivity graph of the cell complex of the receiver."

	| answer |
	answer _ ConnectivityGraph new addAll: self; yourself.
	self do: [ :each |
		each boundary do: [ :some |
			(self cells includes: some) ifTrue: [answer addEdgeFrom: each to: some]]].
	^ answer! !

!SemialgebraicSet methodsFor: 'accessing' stamp: 'len 1/16/98 21:58'!
interior
	"Answer the interior of the receiver."

	^ self closure copyWithoutAll: self boundary! !

!SemialgebraicSet methodsFor: 'accessing' stamp: 'len 2/5/98 20:44'!
projectionAt: anInteger
	"Answer the first anInteger components of the receiver."

	^ self collect: [ :each | each projectionAt: anInteger]! !

!SemialgebraicSet methodsFor: 'accessing' stamp: 'len 2/6/98 13:37'!
sentence
	"Answer a quantifier-free defining sentence for the receiver."

	| answer |
	self do: [ :each |
		answer _ answer isNil
			ifTrue: [each sentence]
			ifFalse: [answer | each sentence]].
	^ answer isNil ifTrue: [Polynomial x squared lneq: 0] ifFalse: [answer]! !

!SemialgebraicSet methodsFor: 'enumerating' stamp: 'len 2/6/98 12:37'!
collect: aBlock 
	"Evaluate aBlock with each of the receiver's elements as the argument. 
	Collect the resulting values into a collection like the receiver. Answer 
	the new collection."

	| newCollection |
	newCollection _ self species new.
	self do: [:each | newCollection add: (aBlock value: each)].
	^newCollection! !

!SemialgebraicSet methodsFor: 'enumerating' stamp: 'len 1/10/98 00:24'!
detect: aBlock ifNone: exceptionBlock 
	"Evaluate aBlock with each of the receiver's elements as the argument. 
	Answer the first element for which aBlock evaluates to true. If none 
	evaluate to true, then evaluate the argument, exceptionBlock."

	self do: [:each | (aBlock value: each) ifTrue: [^ each]].
	^ exceptionBlock value! !

!SemialgebraicSet methodsFor: 'enumerating' stamp: 'len 12/14/97 21:47'!
do: aBlock
	"Enumerate the cells of the receiver."

	self cells do: aBlock! !

!SemialgebraicSet methodsFor: 'enumerating' stamp: 'len 1/16/98 22:08'!
select: aBlock 
	"Evaluate aBlock with each of the receiver's elements as the argument. 
	Collect into a new collection like the receiver, only those elements for 
	which aBlock evaluates to true. Answer the new collection."

	| newCollection |
	newCollection _ self species new.
	self do: [:each | (aBlock value: each) ifTrue: [newCollection add: each]].
	^newCollection! !

!SemialgebraicSet methodsFor: 'comparing' stamp: 'len 1/17/98 12:40'!
= aSemialgebraicSet
	"Answer true if the receiver equals the argument."

	self do: [ :each | (aSemialgebraicSet cells includes: each) ifFalse: [^ false]].
	aSemialgebraicSet do: [ :each | (self cells includes: each) ifFalse: [^ false]].
	^ true! !

!SemialgebraicSet methodsFor: 'comparing' stamp: 'len 1/8/98 20:41'!
hash
	"Answer the hash value of the receiver."

	| answer |
	answer _ 1985123.
	self do: [ :each | answer _ answer + each hash].
	^ answer! !

!SemialgebraicSet methodsFor: 'copying' stamp: 'len 1/16/98 21:59'!
copy
	"Answer a copy of the receiver."

	^ self class basicNew cells: self cells copy! !

!SemialgebraicSet methodsFor: 'copying' stamp: 'len 1/16/98 22:02'!
copyWithoutAll: aCollection
	"Answer a copy of the receiver without all the cells in aCollection."

	^ self select: [ :each | (aCollection includes: each) not]! !

!SemialgebraicSet methodsFor: 'testing' stamp: 'len 1/9/98 21:57'!
connects: aTuple with: anotherTuple
	"Answer true if there exists a path in the receiver
	connecting aTuple with anotherTuple."

	| first last |
	first _ self detect: [ :one | one includes: aTuple] ifNone: [^ false].
	last _ self detect: [ :one | one includes: anotherTuple] ifNone: [^ false].
	^ self graph connects: first with: last! !

!SemialgebraicSet methodsFor: 'testing' stamp: 'len 1/16/98 22:06'!
includes: anObject
	"Answer true if the receiver includes the argument."

	anObject isTuple
		ifTrue: [self do: [ :each | (each includes: anObject) ifTrue: [^ true]].
				^ false].
	anObject do: [ :each | (self cells includes: each) ifTrue: [^ true]].
	^ false! !

!SemialgebraicSet methodsFor: 'testing' stamp: 'len 2/6/98 12:35'!
isEmpty
	"Answer true if the receiver is empty."

	^ self cells isEmpty! !

!SemialgebraicSet methodsFor: 'printing' stamp: 'len 2/6/98 13:33'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	| first |
	"aStream nextPut: ${; print: self sentence; nextPut: $}"
	first _ true.
	self do: [ :each |
		first ifFalse: [aStream nextPutAll: ', '].
		aStream print: each.
		first _ false].
	first ifTrue: [aStream nextPutAll: '{}']! !


!SemialgebraicSet class methodsFor: 'instance creation' stamp: 'len 2/7/98 19:15'!
cad: aPolynomialSet
	"Answer the CAD (Cylindrical Algebraic Decomposition) of R^n,
	by the polynomials in aPolynomialSet, where n is the last
	indeterminate (effectively present) of the polynomials."

	| n |
	n _ aPolynomialSet indeterminates asSortedCollection
		findLast: [ :one |
			(aPolynomialSet detect: [ :any | (any degreeIn: one) > 0] ifNone: []) notNil].
	^ self cad: aPolynomialSet dimension: n! !

!SemialgebraicSet class methodsFor: 'instance creation' stamp: 'len 1/17/98 13:32'!
cad: aPolynomialSet dimension: anInteger
	"Answer the CAD (Cylindrical Algebraic Decomposition) of R^n,
	where n is anInteger, by the polynomials in aPolynomialSet."

	^ self new
		addAll: (CylindricalAlgebraicDecomposition
					polynomials: aPolynomialSet
					dimension: anInteger);
		yourself! !

!SemialgebraicSet class methodsFor: 'instance creation' stamp: 'len 12/14/97 22:47'!
new
	^ super new initialize! !

!SemialgebraicSet class methodsFor: 'examples' stamp: 'len 2/6/98 22:01'!
ball
	"Answer the open unitary ball in R^3."
	"SemialgebraicSet ball."
	| x y z |
	x _ Polynomial x.
	y _ Polynomial y.
	z _ Polynomial z.
	^ (self cad: (PolynomialSet new
					add: x squared + y squared + z squared - 1;
					yourself))
		select: [ :each | each sample norm2 < 1]! !

!SemialgebraicSet class methodsFor: 'examples' stamp: 'len 2/6/98 22:01'!
circle
	"Answer the open unitary circle in R^2."
	"SemialgebraicSet circle."
	| x y |
	x _ Polynomial x.
	y _ Polynomial y.
	^ (self cad: (PolynomialSet new
					add: x squared + y squared - 1;
					yourself))
		select: [ :each | each sample norm2 < 1]! !

!SemialgebraicSet class methodsFor: 'examples' stamp: 'len 2/6/98 22:02'!
circunference
	"Answer the open unitary circunference in R^2."
	"SemialgebraicSet circunference."
	| x y |
	x _ Polynomial x.
	y _ Polynomial y.
	^ (self cad: (PolynomialSet new
					add: x squared + y squared - 1;
					yourself))
		select: [ :each | each sample norm2 = 1]! !

!SemialgebraicSet class methodsFor: 'examples' stamp: 'len 2/6/98 22:02'!
sphere
	"Answer the open unitary sphere in R^3."
	"SemialgebraicSet sphere."
	| x y z |
	x _ Polynomial x.
	y _ Polynomial y.
	z _ Polynomial z.
	^ (self cad: (PolynomialSet new
					add: x squared + y squared + z squared - 1;
					yourself))
		select: [ :each | each sample norm2 = 1]! !


!SequenceableCollection methodsFor: 'comparing' stamp: 'len 6/1/1998 03:48'!
hash
	self size = 0 ifTrue: [^ 17171].
	^ self first hash + self last hash! !


!Set methodsFor: 'comparing' stamp: 'len 6/1/1998 03:48'!
hash
	^ self inject: self size into: [ :hashValue :each | hashValue + each hash]! !


!Dictionary methodsFor: 'enumerating'!
collect: aBlock 
	"Evaluate aBlock with each of my values as the argument.  Collect the
	resulting values into a collection that is like me. Answer with the new
	collection."
	| newCollection |
	newCollection _ Bag new: self size.
	self do: [:each | newCollection add: (aBlock value: each)].
	^ newCollection! !


!SmallInteger methodsFor: 'bit manipulation' stamp: 'len 8/19/97 21:56'!
lowBit
	"Answer the index of the low order bit of this number."

	| n answer |
	n _ self.
	n = 0 ifTrue: [^ 0].
	answer _ 1.
	[(n bitAnd: 16rF) = 0]
		whileTrue: [
			answer _ answer + 4.
			n _ n bitShift: -4].
	[(n bitAnd: 1) = 0]
		whileTrue: [
			answer _ answer + 1.
			n _ n bitShift: -1].
	^ answer! !


!String methodsFor: 'converting' stamp: 'len 11/24/97 20:44'!
asArrayOfSubstrings
	"Answer an array with all the substrings of the receiver separated by
	separator characters (space, cr, tab, linefeed, formfeed, etc)."

	| substrings start end |
	substrings _ OrderedCollection new.
	start _ 1.
	[start <= self size] whileTrue: [
		(self at: start) isSeparator ifFalse: [
			end _ start + 1.
			[end <= self size and: [(self at: end) isSeparator not]]
				whileTrue: [end _ end + 1].
			substrings add: (self copyFrom: start to: end - 1).
			start _ end - 1].
		start _ start + 1].
	^ substrings asArray! !


!Tuple commentStamp: '<historical>' prior: 0!
My instances are tuples of any given finite dimension.

For some examples try:
	Tuple fromArray: #(1 -2 3).
	Tuple with: 1 with: -2 with: 3.

All the objects understand the message #, that is used to create tuples.
For instance, writing (1, -2, 3) is equivalent to the preceding examples.

Tuples understand addition, multiplication by an scalar and the cannonical (real) inner product.

For an example try:
	| a b |
	a _ (1, 2, -1).
	b _ (5, -3, 0).
	a + b.
	a - b.
	a * 3.
	a * b.

Furthermore, you can create 2-dim tuples pointing with the mouse a position in the screen. Try: Tuple fromUser.
!

!Tuple methodsFor: 'initialization' stamp: 'len 10/22/97 03:10'!
initialize: anInteger
	self contents: (Array new: anInteger)! !

!Tuple methodsFor: 'accessing-private' stamp: 'len 10/5/97 21:57'!
contents
	^ contents
! !

!Tuple methodsFor: 'accessing-private'!
contents: anArray
	contents _ anArray
! !

!Tuple methodsFor: 'accessing' stamp: 'len 9/1/97 23:11'!
at: anInteger
	"Answer the element of the receiver at the index anInteger."

	^ self contents at: anInteger! !

!Tuple methodsFor: 'accessing' stamp: 'len 10/22/97 03:04'!
at: anInteger put: anObject
	"Put anObject at the index anInteger in the receiver. Answer anObject."

	^ self contents at: anInteger put: anObject! !

!Tuple methodsFor: 'accessing' stamp: 'len 9/1/97 23:08'!
dimension
	"Answer the dimension of the receiver."

	^ self contents size
! !

!Tuple methodsFor: 'accessing' stamp: 'len 12/13/97 04:52'!
first
	"Answer the first entry of the receiver."

	^ self at: 1! !

!Tuple methodsFor: 'accessing' stamp: 'len 1/17/98 13:58'!
last
	"Answer the last entry of the receiver."

	^ self at: self size! !

!Tuple methodsFor: 'accessing' stamp: 'len 10/5/97 21:51'!
size
	"Answer the size of the receiver."

	^ self dimension! !

!Tuple methodsFor: 'accessing' stamp: 'len 10/16/97 20:11'!
x
	"Answer the x coordinate."

	^ self at: 1! !

!Tuple methodsFor: 'accessing' stamp: 'len 10/16/97 20:11'!
y
	"Answer the y coordinate."

	^ self at: 2! !

!Tuple methodsFor: 'accessing' stamp: 'len 10/16/97 20:11'!
z
	"Answer the z coordinate."

	^ self at: 3! !

!Tuple methodsFor: 'arithmetic' stamp: 'len 12/3/97 03:43'!
* anObject
	"Answer the product of the receiver by the argument."

	anObject isTuple ifTrue: [^ self halt].

	"If the argument is not a tuple, I assume it is a constant."
	^ self collect: [ :each | each * anObject]! !

!Tuple methodsFor: 'arithmetic' stamp: 'len 9/1/97 23:31'!
+ aVector
	"Answer the sum of the receiver and the argument."

	aVector dimension = self dimension
		ifFalse: [^ self errorDimensionNotMatch].

	^ self class
		dimension: self dimension
		fromBlock: [ :each | (self at: each) + (aVector at: each)]! !

!Tuple methodsFor: 'arithmetic' stamp: 'len 7/18/97 01:52'!
- anObject
	"Answer the difference of the receiver and the argument."

	^ self + anObject negated! !

!Tuple methodsFor: 'arithmetic' stamp: 'len 8/13/97 02:01'!
/ anObject
	"Answer the division of the receiver by the argument."

	^ self * anObject reciprocal! !

!Tuple methodsFor: 'arithmetic' stamp: 'len 2/18/98 18:57'!
conjugated
	"Answer the complex conjugation of the receiver."

	^ self collect: [ :each | each conjugated]! !

!Tuple methodsFor: 'arithmetic' stamp: 'len 2/18/98 18:57'!
inner: aTuple
	"Answer the inner product of the receiver by the argument."

	^ self scalar: aTuple conjugated! !

!Tuple methodsFor: 'arithmetic' stamp: 'len 10/5/97 21:52'!
negated
	"Answer the additive inverse of the receiver."

	^ self collect: [ :each | each negated]! !

!Tuple methodsFor: 'arithmetic' stamp: 'len 2/18/98 18:54'!
scalar: aTuple
	"Answer the scalar product of the receiver by the argument."

	| answer |
	answer _ (self at: 1) * (aTuple at: 1).
	2 to: self dimension do: [ :each |
		answer _ (self at: each) * (aTuple at: each) + answer].
	^ answer! !

!Tuple methodsFor: 'enumerating' stamp: 'len 10/5/97 21:53'!
collect: aBlock
	"Answer a copy of the receiver with the coefficients mapped by aBlock."

	^ self class
		dimension: self dimension
		fromBlock: [ :each | aBlock value: (self at: each)]! !

!Tuple methodsFor: 'enumerating' stamp: 'len 10/22/97 03:24'!
do: aBlock
	"Enumerate the entries of the receiver."

	self contents do: aBlock! !

!Tuple methodsFor: 'enumerating' stamp: 'len 4/29/98 00:11'!
indicesDo: aBlock
	"Enumerate the indices of the receiver."
	1 to: self size do: aBlock! !

!Tuple methodsFor: 'operations' stamp: 'len 11/28/97 02:10'!
distance2To: anObject
	"Answer the distance squared to the argument."

	^ anObject isTuple ifTrue: [(self - anObject) norm2] ifFalse: [anObject distance2To: self]! !

!Tuple methodsFor: 'operations' stamp: 'len 11/28/97 02:10'!
distanceTo: anObject
	"Answer the distance to the argument."

	^ anObject isTuple ifTrue: [(self - anObject) norm] ifFalse: [anObject distanceTo: self]! !

!Tuple methodsFor: 'operations' stamp: 'len 1/25/98 01:31'!
euclid
	"Answer a Tuple of coefficients such that the linear combination 
	of those coefficients with the elements of the receiver equals 
	the greatest common divisor of the receiver."

	| a null id s t sPrev tPrev b q r temp answer |
	self dimension = 0 ifTrue: [^ self].
	a _ self at: 1.
	null _ self nullCoefficient.
	id _ self identityCoefficient.
	answer _ self class with: id.
	2 to: self dimension do: [ :each | 
		b _ self at: each.
		s _ id.
		t _ null.
		sPrev _ null.
		tPrev _ id.
		[b isNull]
			whileFalse:
				[q _ a // b.
				r _ a \\ b.
				temp _ s - (q * sPrev).
				s _ sPrev.
				sPrev _ temp.
				temp _ t - (q * tPrev).
				t _ tPrev.
				tPrev _ temp.
				a _ b.
				b _ r].
		answer _ answer * s , t].
	^ answer! !

!Tuple methodsFor: 'operations' stamp: 'len 1/25/98 01:32'!
gcd
	"Answer the gcd of the entries of the receiver."

	| answer |
	self dimension = 0 ifTrue: [^ self identityCoefficient].
	self do: [ :each | answer _ answer isNil ifTrue: [each] ifFalse: [answer gcd: each]].
	^ answer! !

!Tuple methodsFor: 'operations' stamp: 'len 10/5/97 21:53'!
mapCoefficients: aBlock
	"Answer a copy of the receiver with the coefficients mapped by aBlock."

	^ self collect: aBlock! !

!Tuple methodsFor: 'operations' stamp: 'len 7/18/97 01:59'!
norm
	"Answer the euclidean norm of the receiver."

	^ self norm2 sqrt! !

!Tuple methodsFor: 'operations' stamp: 'len 12/3/97 03:21'!
norm2
	"Answer the square norm of the receiver."

	^ self inner: self! !

!Tuple methodsFor: 'operations' stamp: 'len 12/12/97 20:52'!
shift: anInteger
	"Answer the receiver shifted anInteger places."

	| n null |
	null _ self nullCoefficient.
	n _ self dimension.
	^ self class dimension: n fromBlock: [ :each |
		(each - anInteger between: 1 and: n)
			ifTrue: [self at: each - anInteger] ifFalse: [null]]! !

!Tuple methodsFor: 'operations' stamp: 'len 10/5/97 21:53'!
valueAt: anObject
	"Answer the result of evaluating the receiver at the argument."

	^ self collect: [ :each | each valueAt: anObject]! !

!Tuple methodsFor: 'comparing' stamp: 'len 10/5/97 21:57'!
= anObject
	"Answer true if the receiver equals the argument."

	^ self class == anObject class and: [self contents = anObject contents]! !

!Tuple methodsFor: 'comparing' stamp: 'len 8/13/97 21:44'!
hash
	"Answer the hash value of the receiver."

	^ self contents hash! !

!Tuple methodsFor: 'testing' stamp: 'len 10/5/97 21:54'!
isNull
	"Answer true if the reciver is null."

	self do: [ :each | each isNull ifFalse: [^false]].
	^ true! !

!Tuple methodsFor: 'testing' stamp: 'len 11/28/97 02:08'!
isTuple
	"Answer true if the receiver is a Tuple."

	^ true! !

!Tuple methodsFor: 'converting' stamp: 'len 11/20/97 01:51'!
, anObject
	"Answer a new Vector appeding anObject to the receiver."

	^ anObject class == self class
		ifTrue: [self class fromArray: self asArray, anObject asArray]
		ifFalse: [self class fromArray: (self asArray copyWith: anObject)]! !

!Tuple methodsFor: 'converting' stamp: 'len 10/5/97 21:56'!
asArray
	"Answer an Array with the contents of the receiver."

	^ self contents! !

!Tuple methodsFor: 'converting' stamp: 'len 8/23/97 15:40'!
asColumnMatrix
	"Convert the receiver to a column matrix."

	^ self asRowMatrix transposed! !

!Tuple methodsFor: 'converting' stamp: 'len 10/16/97 00:38'!
asPoint
	"Answer the Point with the same coordinates than the receiver.
	Raise an error if the receiver is not of dimension 2."

	self dimension = 2 ifFalse: [^ self error: 'not dimension 2'].
	^ (self at: 1) @ (self at: 2)! !

!Tuple methodsFor: 'converting' stamp: 'len 8/23/97 15:40'!
asRowMatrix
	"Convert the receiver to a row matrix."

	^ Matrix new addRow: self; yourself! !

!Tuple methodsFor: 'copying' stamp: 'len 11/27/97 01:32'!
copy
	"Answer a copy of the receiver."

	^ self class new contents: self contents copy! !

!Tuple methodsFor: 'copying' stamp: 'len 10/5/97 21:55'!
copyFrom: anInteger to: anotherInteger
	"Answer a copy of the receiver from anInteger to anotherInteger."

	^ self class fromArray: (self asArray copyFrom: anInteger to: anotherInteger)! !

!Tuple methodsFor: 'constants' stamp: 'len 8/22/97 20:06'!
e: anInteger
	"Answer the anInteger-th canonical vector with the dimencion of the receiver."

	^ self e: anInteger dimension: self dimension! !

!Tuple methodsFor: 'constants' stamp: 'len 8/21/97 00:12'!
e: anInteger dimension: anotherInteger
	"Answer the anInteger-th canonical vector of
	dimencion anotherInteger."

	| null |
	null _ self nullCoefficient.
	^ self class dimension: anotherInteger fromBlock: [ :each |
		each = anInteger ifTrue: [self identityCoefficient] ifFalse: [null]]! !

!Tuple methodsFor: 'constants' stamp: 'len 10/5/97 21:57'!
identityCoefficient
	"Answer the identity coefficient for the receiver."

	self do: [ :each | each notNil ifTrue: [^ each identity]].
	^ self class identityCoefficient! !

!Tuple methodsFor: 'constants' stamp: 'len 8/22/97 20:35'!
null
	"Answer the null vector with the dimension of the receiver."

	^ self null: self dimension! !

!Tuple methodsFor: 'constants' stamp: 'len 9/1/97 23:32'!
null: anInteger
	"Answer the null vector of dimension anInteger."

	| null |
	null _ self nullCoefficient.
	^ self class dimension: anInteger fromBlock: [ :each | null]! !

!Tuple methodsFor: 'constants' stamp: 'len 10/5/97 21:57'!
nullCoefficient
	"Answer the null coefficient for the receiver."

	self do: [ :each | each notNil ifTrue: [^ each null]].
	^ self class nullCoefficient! !

!Tuple methodsFor: 'private' stamp: 'len 8/13/97 21:47'!
errorDimensionNotMatch
	self error: 'dimension not match'! !

!Tuple methodsFor: 'printing' stamp: 'len 10/5/97 22:18'!
printOn: aStream
	"Print a representation of the receiver on the stream aStream."

	| first |
	first _ true.
	aStream nextPut: $(.
	self do: [ :each |
		first ifFalse: [aStream nextPut: $,; space].
		aStream print: each.
		first _ false].
	aStream nextPut: $)! !


!Tuple class methodsFor: 'instance creation' stamp: 'len 10/22/97 03:09'!
dimension: anInteger
	^ self new initialize: anInteger! !

!Tuple class methodsFor: 'instance creation' stamp: 'len 2/19/98 01:33'!
dimension: anInteger e: anotherInteger scalars: anAlgebraicAmbient
	"Answer the anotherInteger-th canonic tuple of dimencion
	anInteger and with scalars of anAlgebraicAmbient."

	| null |
	null _ anAlgebraicAmbient null.
	^ self dimension: anInteger fromBlock: [ :each |
		each = anotherInteger
			ifTrue: [anAlgebraicAmbient identity] ifFalse: [null]]! !

!Tuple class methodsFor: 'instance creation' stamp: 'len 5/28/1998 19:54'!
dimension: anInteger fromBlock: aBlock
	^ self fromArray: ((1 to: anInteger) collect: aBlock)! !

!Tuple class methodsFor: 'instance creation' stamp: 'len 2/21/98 23:09'!
fromArray: anArray
	^ self new contents: anArray! !

!Tuple class methodsFor: 'instance creation' stamp: 'len 10/16/97 20:10'!
fromPoint: aPoint
	"Answer a new instance of the receiver representing the 2-dim vector
	with the same coordinates that the argument has."

	^ self with: aPoint x with: aPoint y! !

!Tuple class methodsFor: 'instance creation' stamp: 'len 9/1/97 23:32'!
null: anInteger
	"Answer the null vector of dimension anInteger."

	| null |
	null _ self nullCoefficient.
	^ self dimension: anInteger fromBlock: [ :each | null]! !

!Tuple class methodsFor: 'instance creation' stamp: 'len 7/18/97 01:37'!
with: anElement
	^ self fromArray: (Array with: anElement)! !

!Tuple class methodsFor: 'instance creation' stamp: 'len 7/18/97 01:37'!
with: anElement with: otherElement
	^ self fromArray: (Array with: anElement with: otherElement)! !

!Tuple class methodsFor: 'instance creation' stamp: 'len 7/18/97 01:38'!
with: anElement with: otherElement with: thirthElement
	^ self fromArray: (Array with: anElement with: otherElement with: thirthElement)! !

!Tuple class methodsFor: 'instance creation' stamp: 'len 11/7/97 01:38'!
x: x y: y
	"Answer a new instance of the receiver with the given coordinates."

	^ self with: x with: y! !

!Tuple class methodsFor: 'instance creation' stamp: 'len 11/7/97 01:38'!
x: x y: y z: z
	"Answer a new instance of the receiver with the given coordinates."

	^ self with: x with: y with: z! !

!Tuple class methodsFor: 'constants' stamp: 'len 8/30/97 01:05'!
identityCoefficient
	^ 1! !

!Tuple class methodsFor: 'constants' stamp: 'len 8/30/97 01:05'!
nullCoefficient
	^ 0! !

!Tuple class methodsFor: 'examples' stamp: 'len 11/28/97 02:13'!
fromUser
	"Let the user select a 2-dim Tuple from the screen with the mouse."

	| dot point answer |
	dot _ Form dotOfSize: 4.
	Cursor crossHair showWhile: [Sensor waitButton. point _ Sensor waitNoButton].
	dot displayOn: Display at: point clippingBox: Display boundingBox
		rule: Form oldPaint fillColor: Color black.
	answer _ self fromPoint: point.
	answer printString asParagraph form
		displayOn: Display at: point clippingBox: Display boundingBox
		rule: Form oldPaint fillColor: Color black.
	^ answer! !


!UniversalQuantifier commentStamp: '<historical>' prior: 0!
My instances are universal quantifiers in one indeterminate.

For an example try:
	UniversalQuantifier indeterminate: 3.
!

!UniversalQuantifier methodsFor: 'arithmetic' stamp: 'len 12/21/97 21:13'!
not
	"Answer the negation of the receiver."

	^ ExistentialQuantifier indeterminate: self indeterminate! !

!UniversalQuantifier methodsFor: 'testing' stamp: 'len 2/5/98 21:27'!
isUniversal
	"Answer true if the receiver is an universal quantifier."
	^ true! !

!UniversalQuantifier methodsFor: 'printing' stamp: 'len 12/19/97 21:59'!
printOn: aStream withNames: aDictionary
	"Print a representation of the receiver on the stream aStream
	using the indeterminate names from aDictionary."

	| name |
	name _ aDictionary
				at: self indeterminate
				ifAbsent: ['{x', self indeterminate printString, '}'].
	aStream nextPutAll: '(for all ', name, ')'! !


Number removeSelector: #ambient!
AlgebraicNumber removeSelector: #minimal!