Computer Algebra Kit (c) 1993,00 by Comp.Alg.Objects.  All Rights Reserved.

CAObject

Inherits from: Object

Maturity Index: Relatively mature

Class Description

CAObject is the root class of the Computer Algebra Kit.  It implements functionality that is inherited by all Computer Algebra Kit objects and defines a number of methods that inheriting classes are expected to override, thus establishing interface conventions that must be followed by all classes.

Arithmetic

Classes like Polynomial or Matrix work over arbitrary coefficient domains.   The interface to basic arithmetical operations that is declared by CAObject, is designed to support this important feature.

Arithmetical operations such as multiply: or add: are defined only on instances of the same class, or more precisely on objects for which sameClass: returns YES.  The algebraic properties of a set (class) of objects is tested by sending messages to an element of the set (for example inOrderedSet), and control the algorithms being used.  Nullary operators, like obtaining the unity element of a set, are made unary : the unity element of a set is obtained by sending one to an arbitrary element of the set.

For example, for two Integer objects, sameClass: simply returns YES, but for two IntegerModp objects, sameClass: returns YES if and only if the moduli are equal.  This means that you can sum, using add:, any pair of Integer instances, but that you cannot add an object mod p to an object mod q.  Also, you cannot add a Integer instance to a IntegerModp instance using the add: method.

Method types

Class Methods	- cakitRevision
	- str:
	- int:
	- copy
	- deepCopy

Class of an Object	- sameClass:
	- differentClass:
	- isKindOfSequence

Coercion	- str
	- str:
	- intValue
	- intValue:
	- asModp:
	- isFloatingPoint
	- asNumerical
	- floatValue
	- floatValue:
	- asTotalFraction
	- asScalar
	- asSymbol

Equality	- isEqual:
	- notEqual:

Comparing	- inOrderedSet
	- compare:
	- sign
	- isLess:
	- isGreater:
	- isLessEqual:
	- isGreaterEqual:
	- absValue

Addition	- inAdditiveSemiGroup
	- inAdditiveMonoid
	- inAdditiveGroup
	- isZero
	- notZero
	- isOpposite:
	- notOpposite:
	- zero
	- negate
	- add:
	- subtract:
	- increment
	- decrement
	- multiplyIntValue:
	- double
	- quadruple
	- divideIntValue:
	- half
	- quarter

Multiplication	- commutes
	- commutesWith:
	- inSemiGroup
	- inMonoid
	- inGroup
	- one
	- minusOne
	- isOne
	- notOne
	- isMinusOne
	- notMinusOne
	- square
	- multiply:
	- power:
	- inverse
	- isUnit
	- notUnit
	- divide:

Division with Remainder	- remainder:quotient:
	- remainder:
	- quotient:

Greatest Common Divisor	- inEuclideanDomain
	- isCoprime:
	- notCoprime:
	- isGcd::
	- isLcm::
	- gcd:
	- bezout:gcd:
	- lcm:

Modular Arithmetic	- modulo:
	- multiply:modulo:
	- squareModulo:
	- power:modulo:
	- genpower:modulo:
	- inverseModulo:

Random	- random

Characteristic	- characteristic
	- isCharacteristicZero
	- notCharacteristicZero
	- isCharacteristicTwo
	- notCharacteristicTwo
	- frobenius
	- frobeniusInverse
	- dimensionOverPrimeField

Addition and Multiplication	- inRing
	- inIntegralDomain
	- inField
	- inFieldOfFractions

Scalar Multiplication	- scalarZero
	- scalarContent
	- divideScalarContent
	- multiplyScalar:
	- divideScalar:
	- addScalar:
	- subtractScalar:

Printing	- printsLeadingSign
	- printsSum
	- printsProduct
	- printOn:

Methods

cakitRevision
+ (STR)cakitRevision

This method returns the value of the revision string __cakit_revision__ (declared in the header file cakit/cakit.h), as it was when the Computer Algebra Kit was built.  The string in the header file that you're using should match the string returned by this method.

str:
+str:(STR)aString

Creates an object given a string description.  No default implementation.

int:
+int:(int)intValue

Creates an object given an int value.  No default.

copy
-copy

Creates a copy of the object by sending copy to super.  Sets the reference count of the new object to one.

Subclasses must implement their own versions of copy to copy additional memory consumed by the copied object.

- copy
{
    self = [super copy];
    pointer = malloc(nBytes);
    return self;
}

Note that the message to super precedes the code added in the method.  This ensures that copying proceeds in the order of inheritance.

See also: deepCopy

deepCopy
-deepCopy

Creates a deep copy of the object by sending copy to super.  Sets the reference count of the new object to one.

Subclasses must implement their own versions of deepCopy to make a full independent copy of the object.

- deepCopy
{
    self = [super deepCopy];
    companionObject = [companionObject deepCopy];
    return self;
}

See also: copy

sameClass:
- (BOOL)sameClass:a

Whether the objects belong to the same class; the default implementation checks whether the isa pointers of the objects are the same.  Some classes override sameClass: to impose extra requirements; for example, for integers mod p :

return [super sameClass:a] && [self modulus] == [a modulus];

differentClass:
- (BOOL)differentClass:a

Whether sameClass: returns NO.  Don't override this method.  Implement your own version of sameClass: instead (incorporating a call to super's implementation of sameClass:).

isKindOfSequence
- (BOOL)isKindOfSequence

Equivalent to :

[self isKindOf:(id)[CASequence class]]

str
- (STR)str

Returns a string containing a symbolic representation for the object.  Suited for small expressions only since output is unbuffered.  Works by allocating a small buffer and then invoking printOn: on that buffer to do the actual printing.

You don't have to free the string (it is deallocated when you free or change the object), which makes it easy to use the method as follows :

fprintf(stderr,"Value of this %s is %s\n",[anObject name],[anObject str]);

str:
-str:(STR)aString

Returns a new object, instance of the same class, created from aString or returns nil if it's not possible to evaluate aString in the set.  Note that it's not necessarily true that the string value of the new object is literally equal to aString.  There is no default implementation for this method.

intValue
- (int)intValue

Returns, if it makes sense, the value of the object as C integer.  There is no default implementation for this method.

intValue:
-intValue:(int)i

Returns a new object of the same class with intValue equal to i or returns nil.

asModp:
-asModp:(unsigned short)p

Returns an object that is the value modulo the small prime number p for the object that receives the message.  For example, an integer object returns a IntegerModp object in response to this method; a matrix returns a matrix with modular values and so on.

isFloatingPoint
- (BOOL)isFloatingPoint

Returns YES if the object is some kind of floating-point arithmetic.  The default implementation returns NO.  No attempt has been made to integrate floating-point arithmetic into the Computer Algebra Kit's framework of algebraic structures; floating-point numbers are always treated as a special case.

asNumerical
-asNumerical

Returns an object that is the numerical value for the object that receives the message.  For example, an integer object returns a floating-point object as numerical value; a matrix returns a matrix with numerical values and so on.

floatValue
- (float)floatValue

Returns, if it makes sense, the value of the object as C floating-point number.  There is no default implementation for this method.

floatValue:
-floatValue:(float)f

Returns a new object of the same class with floatValue equal to f or returns nil.

asTotalFraction
-asTotalFraction

Returns a new fraction with the numerator set to a new reference to the original object, and with the denominator set to one.  For example, an integer object returns a rational number.

asScalar
-asScalar

Returns a new scalar object or nil if the object cannot be coerced into a scalar object; there is no default implementation of the method.  Polynomial overrides this method to return a scalar object if the polynomial contains just a single scalar and no symbols, or nil otherwise.

asSymbol
-asSymbol

Returns a new symbol object or nil if the object cannot be coerced into a symbol object; there is no default implementation provided.  Polynomial overrides this method to return a symbol object if the polynomial consists of a single symbol raised to the exponent one, or nil otherwise.

Note: Symbol itself does not implement this method.

isEqual:
- (BOOL)isEqual:a

Should test whether the objects are equal.  Returns, by default, YES if the two objects are the same (ie. pointer equal)

notEqual:
- (BOOL)notEqual:a

Whether isEqual: returns NO.

inOrderedSet
- (BOOL)inOrderedSet

Whether the object is an element of a (totally) ordered set.  Elements can be compared with compare: if this method returns YES.  There is no default implementation for this method.

compare:
- (int)compare:b

This method should return -1, 0, or +1 if self is less than, equal to, or greater than b.  There is no default implementation for this method.

sign
- (int)sign

Returns the sign of the object : plus one if positive (greater than zero), zero if zero and minus one if negative (less than zero).  There is no default implementation for this method.

isLess:
- (BOOL)isLess:a

Tests whether the object is less than (but not equal to) a.  Defined, by default, in terms of compare:.

isGreater:
- (BOOL)isGreater:a

Tests whether the object is greater than (but not equal to) a.  Defined, by default, in terms of compare:.

isLessEqual:
- (BOOL)isLessEqual:a

Tests whether the object is less than or equal to a.  Defined, by default, in terms of compare:.

isGreaterEqual:
- (BOOL)isGreaterEqual:a

Tests whether the object is greater than or equal to a.  Defined, by default, in terms of compare:.

absValue
-absValue

Returns the absolute value of the object (a new object).  If the object is negative, invokes negate.  Otherwise returns self.

inAdditiveSemiGroup
- (BOOL)inAdditiveSemiGroup

Should return YES if the object is an element of an additive semigroup ie., a set equiped with a (commutative) additive operation, but not necessarily with a unique zero element.  Objects that return YES should be prepared to receive negate, add:, subtract:, zero and isZero messages, but a zero element for some object a is not necessarily the zero object for another object b of the same class.   For example, the vectors (of variable dimension) have zero elements of different dimension.  There is no default implementation for this method.

inAdditiveMonoid
- (BOOL)inAdditiveMonoid

Should return YES if the object is an element of an additive monoid ie., an additive semigroup with a unique zero element : if an object returns YES to this method, and if isZero returns YES, then it is the zero object for all objects of the same class.  However, not every element in the set necessarily has an additive inverse : for example, the set of positive integers contains elements with no additive inverse.  There is no default implementation for this method.

inAdditiveGroup
- (BOOL)inAdditiveGroup

Should return YES if the object is an element of an additive group ie., an additive monoid with an additive inverse for each element.  There is no default implementation for this method.

isZero
- (BOOL)isZero

Returns YES if the object is equal to zero.  There is no default implementation for this method.

If the object is an element of an additive monoid, the method should test whether the object is the unique zero element.  Otherwise, isZero should return YES if the object is the zero element for itself.  Matrices of variable dimension, for example,  have zero elements of different dimension.

notZero
- (BOOL)notZero

Whether isZero returns NO.

isOpposite:
- (BOOL)isOpposite:b

Should return YES if the objects are additive inverses.  Zero is the only object that is its own additive inverse, unless the characteristic is equal to two.

notOpposite:
- (BOOL)notOpposite:b

Whether isOpposite returns NO.

zero
-zero

Returns a new reference to the zero element.

If the object is an element of an additive monoid, the zero element is unique.  Otherwise, zero should return an element c such that self + c = 0.  Matrices of variable dimension, for example,  have zero elements of different dimension.

There is no default implementation for this method.

negate
-negate

Returns the opposite of the object (a new object).  There is no default implementation.

add:
-add:b

Returns the sum self + b.  If the object is pointer equal to the argument, this method should be equivalent to double.  Adding zero returns a new object that is equal to the non-zero object.

subtract:
-subtract:b

Returns a new object, equal to self - b.  If the object is pointer equal to the argument, this method is equivalent to zero.

increment
-increment

Adds one to the object.  Returns a new object.

decrement
-decrement

Subtracts one from the object.  Returns a new object.

multiplyIntValue:
-multiplyIntValue:(int)b

Returns a new object equal to the product self b.  The default implementation creates an object through -intValue: and then invokes multiply:.

See also: zero, double, quadruple

double
-double

Multiplies the object by two.  Returns a new object.  There is no default implementation for this method.

quadruple
-quadruple

Multiplies the object by four.  Returns a new object.

There is no default implementation for this method.

divideIntValue:
-divideIntValue:(int)b

Returns a new object, the exact quotient of the object on division by b.  Returns nil if the division is not exact or if b is equal to zero. 

half
-half

Divides the object by two.  Returns a new object, or nil if the object is not a multiple of two.

quarter
-quarter

Divides the object by four.  Returns a new object, or nil if the object is not a multiple of four.

commutes
- (BOOL)commutes

Should return YES if multiplication is commutative for all elements of the set that the object belongs to.  There is no default implemenation for this method.

commutesWith:
- (BOOL)commutesWith:b

Should return YES if multiplication is commutative for the two objects.  There is no default implemenation for this method.

inSemiGroup
- (BOOL)inSemiGroup

Should return YES if the object is an element of a (multiplicative) semigroup, ie. a set equiped with a (possibly non-commutative) multiplicative operation.  However, the set doesn't necessarily have a unique unity element.  For example, matrices of free dimension don't.  There is no default implemenation for this method.

inMonoid
- (BOOL)inMonoid

Should return YES if self is an element of a (multiplicative, possibly non-commutative) monoid, ie. a semigroup with a unique unity element.  However, not every element in the set necessarily has a multiplicative inverse.  There is no default implemenation for this method.

inGroup
- (BOOL)inGroup

Should return YES if self is an element of a (multiplicative, possibly non-commutative) group, ie. a monoid with a multiplicative inverse for each element.  There is no default implemenation for this method.

one
-one

Returns a new reference to the multiplicative unity.

If the object is an element of a multiplicative monoid the unity element is unique.  Otherwise, one returns the (right) multiplicative unity element for the object itself, ie. an element c such that self c = 1.  Matrices of variable dimension, for example,  have unity elements of different dimension.

There is no default implementation for this method.

minusOne
-minusOne

Returns a new reference to the opposite of the multiplicative unity.  Negates by default the object returned by one.

isOne
- (BOOL)isOne

Should return YES if the object is equal to one.  There is no default implementation for this method.

If the object is an element of an multiplicative monoid, the method should test whether the object is the unique unity element.  Otherwise, isOne should return YES if the object is the (right) multiplicative unity element for itself.  Matrices of variable dimension, for example,  have unity elements of different dimension.

notOne
- (BOOL)notOne

Whether isOne returns NO.

isMinusOne
- (BOOL)isMinusOne

Should return YES if the object is equal to minus one i.e., the additive inverse of the multiplicative unity.  There is no default implementation for this method.

notMinusOne
- (BOOL)notMinusOne

Whether isMinusOne returns NO.

square
-square

Returns the square of the object ie., a new object equal to the object multiplied by itself.

multiply:
-multiply:b

Returns a new object equal to the product self b.

Note that when multiplication is not commutative, [a multiply:b] is not the same thing as [b multiply:a].  Non-commutative multiplication is currently hardly supported.  In general, we have used throughout the Computer Algebra Kit right multiplication.  Left multiplication will be explicitely indicated.

power:
-power:(int)n

Returns the object raised to the n-th power ie., a new object obtained by multiplying the object n times by itself.

If n is zero, the method invokes one, except if the object itself is zero.  In that case the method returns nil.  If n is negative, the method raises the inverse of the object to the -n-th power, or if the object is not invertible, it returns nil.

The default implementation of this method consists of the binary exponentation algorithm (invoking square).  The method may be overridden in those cases where the binary exponentation algorithm performs worse than, for example, a repeated multiplication strategy (for sufficiently sparse polynomials e.g.).

inverse
-inverse

Returns the multiplicative inverse (a new object).  If there is no inverse, the method returns nil.

isUnit
- (BOOL)isUnit

Tests whether the object has a multiplicative inverse.  The default implementation tests whether inverse returns nil or not.

notUnit
- (BOOL)notUnit

Whether isUnit returns NO.

divide:
-divide:b

Returns the exact quotient on division ie., returns a new object equal to the object multiplied (to the right) by the inverse of b.  If the division fails or if the division is not exact (when there is a remainder), this method returns nil.

Note: Use quotient: to determine the quotient of a division with remainder.

remainder:quotient:
-remainder:bquotient:(id *)q

Divides self by b; returns the remainder R, and by reference, the quotient Q, such that a = Q b + R.  The quotient should not be computed when a NULL pointer is passed for q.  There is no default implementation for this method.

See also: divide, quotient, remainder

remainder:
-remainder:b

Returns a new object, the remainder on division of self by b.  The default implementation invokes remainder:quotient: with a NULL quotient argument.

Note: For ordered domains (such as the integers), this method should return a signed remainder, while modulo: returns an unsigned remainder.

See also: modulo

quotient:
-quotient:b

Returns a new object, the quotient on division of by b.  There may be a remainder on division, which can be obtained through remainder:.  The default implementation invokes remainder:quotient:, and throws away the remainder.

See also: divide

inEuclideanDomain
- (BOOL)inEuclideanDomain

Returns YES if self is an element of a euclidean domain.  There is no default implementation.

isCoprime:
- (BOOL)isCoprime:b

Tests whether the greatest common divisor of self and b is a unit.  Computes the gcd (by invoking -gcd:) and then invokes isUnit.

notCoprime:
- (BOOL)notCoprime:b

Whether isCoprime returns NO.

isGcd::
- (BOOL)isGcd:a:b

Whether self is the greatest common divisor of a and b.  The default implementation computes the gcd by sending -gcd: and compares to self.

isLcm::
- (BOOL)isLcm:a:b

Whether self is the least common multiple of a and b.  The default implementation computes the gcd by sending -lcm: and compares to self.

gcd:
-gcd:b

Returns a new object, the greatest common divisor of self and b.  In the case of an additive semigroup, the following should hold : gcd(0,b) = b and gcd(a,0) = a.  There is no default implementation for this method.

bezout:gcd:
-bezout:bgcd:(id *)gcd

Returns a new object, the bezout coefficient of the object, and if a non NULL pointer is passed for gcd, by reference, the gcd of object and b.  The bezout coefficient is the element u such that u self + v b == gcd.

There is no default implementation for this method.

lcm:
-lcm:b

Returns the least common multiple of the objects.  The default implementation multiplies the the objects and divides by their gcd.  In the case of an additive semi-group, lcm(a,0) = a and lcm(0,b) = b and lcm(0,0) = 0.

modulo:
-modulo:m

Returns a new object, the representant of the object modulo m.  For ordered domains (such as the integers), the representant is kept positive (in the range [0,m[).  For domains such as polynomials over a finite field, modulo: is equivalent to remainder:.

The default implementation invokes remainder:.  Adds back m, if self is ordered and the remainder is negative.

multiply:modulo:
-multiply:bmodulo:m

Returns a new object, the product self b modulo m.  The default implementation first calls multiply: and then modulo:.

squareModulo:
-squareModulo:m

Returns a new object, the square of self modulo m.  The default implementation first calls square and then modulo:.

power:modulo:
-power:(int)nmodulo:m

Returns a new object, equal to self raised to the n-th power modulo m.  The default implementation uses the modular binary exponentation algorithm. 

If self and n are equal to zero, returns nil.

See also: genpower:modulo:

genpower:modulo:
-genpower:nmodulo:m

Returns a new object, equal to self raised to the n-th power modulo m (where n is an instance of the BigInt class).  The default implementation uses the modular binary exponentation algorithm. 

If self and n are equal to zero, returns nil.

inverseModulo:
-inverseModulo:m

Returns a new object, the inverse of self modulo m.  Generates an error message by default.

random
-random

Returns a new random object.  For example, for the integers, random returns 0 or 1.  For the integers mod p, random returns an integer mod p (possibly zero).

There is no default implementation.

characteristic
- (int)characteristic

Returns the characteristic of (the set of) the object, ie. the number n such that n a is zero for each element a.  Domains of characteristic larger than INT_MAX are currently not supported.  There is no default implementation of the method.

isCharacteristicZero
- (BOOL)isCharacteristicZero

Whether characteristic returns zero.

notCharacteristicZero
- (BOOL)notCharacteristicZero

Whether characteristic returns not zero.

isCharacteristicTwo
- (BOOL)isCharacteristicTwo

Whether characteristic returns two.

notCharacteristicTwo
- (BOOL)notCharacteristicTwo

Whether characteristic returns not two.

frobenius
-frobenius

Returns a new object, the image of self under the frobenius map, ie. exponentation by the characteristic of self.  There is no default implementation.

frobeniusInverse
-frobeniusInverse

Returns a new object, the inverse image of self under the frobenius map, ie. the n-th root of self where n is the characteristic of self.  There is no default implementation.

dimensionOverPrimeField
- (int)dimensionOverPrimeField

This method should return the dimension of a finite field over its prime field.  For example, the dimension of GaloisField(9) over GaloisField(3) is 2.

inRing
- (BOOL)inRing

The object is in a ring if it's in an additive group and a multiplicative monoid.

inIntegralDomain
- (BOOL)inIntegralDomain

Should return YES if the object is an element of a ring without zero divisors.  There is no default implementation of this method.  Examples of integral domains in the Computer Algebra Kit include, the integers, the Gaussian (complex) integers and polynomial rings.

inField
- (BOOL)inField

Whether the object is element of an additive group and a multiplicative group.  Examples of fields in the Computer Algebra Kit include, the integers mod p, Galois fields, and various fields of fractions such as the rational numbers or rational functions.

inFieldOfFractions
- (BOOL)inFieldOfFractions

Whether the object is element of a field of fractions.  Returns NO by default; overridden by Fraction and used by some linear algebra algorithms to reduce computations over a field of fractions to computations over an integral domain.

scalarZero
-scalarZero

Returns a reference to the zero scalar object.

See also: zero

scalarContent
-scalarContent

Returns a new scalar object, the (scalar) content of the objects, ie. the gcd of its scalars.

There is no default implementation of this method.

divideScalarContent
-divideScalarContent

If the scalar content is zero, this method simply returns a copy of self.  Otherwise, it divides by the content (sending divideScalar:), ie. it computes the primitive part of self.

multiplyScalar:
-multiplyScalar:s

Returns a new object, equal to self multiplied (to the right) by the scalar s.

divideScalar:
-divideScalar:s

Returns a new object, equal to self divided by the scalar s.  The division is exact; if it isn't, the method returns nil.

addScalar:
-addScalar:s

Adds the scalar s to the object.  Should return a new object.

subtractScalar:
-subtractScalar:s

Subtracts the scalar s from the object.  Should return a new object.

printsLeadingSign
- (BOOL)printsLeadingSign

Should return YES if the printing methods for this object print a leading minus sign.  This can be used in other implementations to avoid printing a plus sign followed by a minus sign.  The default implementation returns NO.

printsSum
- (BOOL)printsSum

Should return YES if the printing methods for this object print multiple terms separated by a plus or minus sign.  This can be used in other implementations to place the expression between parentheses if necessary.  The default implementation returns NO.

printsProduct
- (BOOL)printsProduct

Should return YES if the printing methods for this object print multiple factors separated by a space or multiplication sign.  This can be used in other implementations to place the expression between parentheses if necessary.  The default implementation returns NO.

printOn:
-printOn:(IOD)aFile

Should print a textual representation of the object to aFile.  Methods such as str, printForDebugger:, printOn: etc. work by invoking this method.