login  home  contents  what's new  discussion  bug reports help  links  subscribe  changes  refresh  edit

Symbolic Integers

A simple form of symbolic computation using just Variable and Integer.

fricas
a:Union(Variable a,Integer)
Type: Void
fricas
b:Union(Variable b,Integer)
Type: Void
fricas
c:=a*3-b*2
 (1)
Type: Polynomial(Integer)
fricas
p:UP(x,Integer):=x*2-7
 (2)
Type: UnivariatePolynomial(x,Integer)
fricas
pc := p c
 (3)
Type: Fraction(Polynomial(Integer))
fricas
f(x)==x^3-x^2+1
Type: Void
fricas
fb := f b
fricas
Compiling function f with type Variable(b) -> Polynomial(Integer)
 (4)
Type: Polynomial(Integer)
fricas
a:=1
 (5)
Type: Union(Integer,...)
fricas
b:=-3
 (6)
Type: Union(Integer,...)
fricas
c
 (7)
Type: Polynomial(Integer)
fricas
eval(pc,['a=a,'b=b])
 (8)
Type: Fraction(Polynomial(Integer))
fricas
eval(c,['a=a,'b=b])
 (9)
Type: Polynomial(Integer)
fricas
eval(fb,['a=a,'b=b])
 (10)
Type: Polynomial(Integer)
fricas
a:=3.14  -- not permitted!
Cannot convert right-hand side of assignment 3.14
to an object of the type Union(Variable(a),Integer) of the left-hand side. a:='b -- not permitted!
Cannot convert right-hand side of assignment b
to an object of the type Union(Variable(a),Integer) of the left-hand side.

For more complex cases it is necessary to define a new domain of "indeterminants". These are symbols and unevaluated expressions that can be evaluated at a later time. This domain is modeled after InputForm which provides all of the basic functionality.

)abbrev domain INDET Indeterminant
++ Description:
++   This domain provides basic support for symbols and unevaluated expressions
++   Based on InputForm
-- Author: Bill Page
Indeterminant():
Join(SExpressionCategory(String,Symbol,Integer,DoubleFloat,OutputForm),
ConvertibleTo SExpression) with
eval: % -> Any
++ eval(f) evaluates f with current values of symbols
"+"      : (%, %) -> %
++ \spad{a + b}
"-"      : (%, %) -> %
++ \spad{a - b}
"-"      : % -> %
"*"      : (%, %) -> %
++ \spad{a * b}
"/"      : (%, %) -> %
++ \spad{a / b}
"^"     : (%, NonNegativeInteger) -> %
++ \spad{a ** b}
"^"     : (%, Integer) -> %
++ \spad{a ** b}
coerce : Integer -> %
Rep := SExpression
eval x == interpret(x pretend InputForm)
coerce(x:Integer):% == convert(x) coerce(x:%):OutputForm == expr x
convert(x:%):SExpression == x pretend SExpression convert(x:DoubleFloat):% == convert(x)$Rep s1 + s2 == convert [convert("+"::Symbol), s1, s2]$List(%)
s1 - s2 == convert [convert("-"::Symbol), s1, s2]$List(%) _-(s1) == convert [convert("-"::Symbol), s1]$List(%)
s1 * s2 == convert [convert("*"::Symbol), s1, s2]$List(%) s1:% ^ n:Integer == convert [convert("^"::Symbol), s1, convert n]$List(%)
s1:% ^ n:NonNegativeInteger == s1 ^ (n::Integer)
s1 / s2 == convert [convert("/"::Symbol), s1, s2]$List(%) spad Compiling FriCAS source code from file /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/2122500948687555929-25px002.spad using old system compiler. INDET abbreviates domain Indeterminant ------------------------------------------------------------------------ initializing NRLIB INDET for Indeterminant compiling into NRLIB INDET compiling exported eval :$ -> Any
Time: 0.04 SEC.
compiling exported coerce : Integer -> $Time: 0 SEC. compiling exported coerce :$ -> OutputForm Time: 0 SEC.
compiling exported convert : $-> SExpression INDET;convert;$Se;4 is replaced by x Time: 0 SEC.
compiling exported convert : DoubleFloat -> $Time: 0 SEC. compiling exported + : ($,$) ->$ Time: 0 SEC.
compiling exported - : ($,$) -> $Time: 0 SEC. compiling exported - :$ -> $Time: 0 SEC. compiling exported * : ($,$) ->$ Time: 0 SEC.
compiling exported ^ : ($,Integer) ->$ Time: 0.01 SEC.
compiling exported ^ : ($,NonNegativeInteger) ->$ Time: 0 SEC.
compiling exported / : ($,$) -> $Time: 0 SEC. (time taken in buildFunctor: 0) ;;; *** |Indeterminant| REDEFINED ;;; *** |Indeterminant| REDEFINED Time: 0 SEC. Cumulative Statistics for Constructor Indeterminant Time: 0.05 seconds finalizing NRLIB INDET Processing Indeterminant for Browser database: --------constructor--------- --------(eval ((Any) %))--------- --------(+ (% % %))--------- --------(- (% % %))--------- --------(- (% %))--------- --------(* (% % %))--------- --------(/ (% % %))--------- --------(^ (% % (NonNegativeInteger)))--------- --------(^ (% % (Integer)))--------- --->-->Indeterminant((coerce (% (Integer)))): Not documented!!!! ; compiling file "/var/aw/var/LatexWiki/INDET.NRLIB/INDET.lsp" (written 31 JUL 2013 04:40:23 PM): ; /var/aw/var/LatexWiki/INDET.NRLIB/INDET.fasl written ; compilation finished in 0:00:00.026 ------------------------------------------------------------------------ Indeterminant is now explicitly exposed in frame initial Indeterminant will be automatically loaded when needed from /var/aw/var/LatexWiki/INDET.NRLIB/INDET Symbolic Matrices fricas )clear all All user variables and function definitions have been cleared. fricas m:Union(Indeterminant,Matrix Integer) Type: Void fricas n:Union(Indeterminant,Matrix Integer) Type: Void fricas a:Union(Indeterminant,Integer) Type: Void fricas b:Union(Indeterminant,Integer) Type: Void fricas ab:=(3*a+b)*(a-2*b)  (11) Type: Indeterminant fricas a:=1$Integer  -- because 0 and 1 can be symbolic!
 (12)
Type: Union(Integer,...)
fricas
eval ab
 (13)
Type: Indeterminant
fricas
b:=0$Integer  (14) Type: Union(Integer,...) fricas a:=-10  (15) Type: Union(Integer,...) fricas eval ab  (16) Type: PositiveInteger? fricas mn1:= m*n-n*m  (17) Type: Indeterminant fricas mn2:=(m+n)*(m-n-1)  (18) Type: Indeterminant fricas m:=matrix [[1,2],[3,4]]  (19) Type: Union(Matrix(Integer),...) fricas n:=matrix [[-1,-2],[-3,4]]  (20) Type: Union(Matrix(Integer),...) fricas eval mn1  (21) Type: Matrix(Integer) fricas eval mn2  (22) Type: Matrix(Integer) Questions --yixin.cao, Mon, 07 Jul 2008 10:36:24 -0700 reply In the Union(Variable a,Integer) way, fricas )clear all All user variables and function definitions have been cleared. fricas d: Union(Variable d, Float) Type: Void fricas d*2  (23) Type: Polynomial(Integer) will be problematic, and the assignment between symbolic integers is not allowed. fricas a: Union(Variable a, Integer) Type: Void fricas b: Union(Variable b, Integer) Type: Void fricas b:=a a is declared as being in Union(Variable(a),Integer) but has not been given a value. Re: will be problematic --Bill Page, Mon, 07 Jul 2008 13:48:14 -0700 reply I agree that the type Union(Variable d,Integer) alone is not sufficient for symbolic computation. But although it might look strange, in fact a result of Polynomial Integer for 2*d is not really a problem. Remember that the use of Integer in Polynomial Integer does not mean that evaluation of the polynomial yields an Integer - it means only that the domain of the coefficients of the polynomial are integers (i.e. that 2 is an integer), it says nothing about 'd': fricas p:=2*d  (24) Type: Polynomial(Integer) fricas eval(p,d=3.14)  (25) Type: Polynomial(Float) But there is still a problem since I can write: fricas a:Union(Variable a,Integer) Type: Void fricas a:=3.14 Cannot convert right-hand side of assignment 3.14 to an object of the type Union(Variable(a),Integer) of the left-hand side. p:=2*a  (26) Type: Polynomial(Integer) fricas eval(p,a=3.14)  (27) Type: Polynomial(Float) and Axiom does not complain about the eval request because as far as Polynomial Integer is concerned d is just a Symbol. In the case of the example Indeterminant domain, evaluation of symbolic expressions is always delayed so an appropriate eval operation could be defined that properly respects the type. Re: assignment between symbolic integers --Bill Page, Mon, 07 Jul 2008 14:00:37 -0700 reply I am not sure what b:=a should mean. Does it mean that Variable(b) is to be assigned the Symbol a? If so then I think the type should admit this possibility. E.g. fricas c:Union(Variable(c),Symbol) Type: Void fricas c:=a  (28) Type: Union(Symbol,...) the fundamental problem is that, when you define d as Float, the computation of (2 * d) should NOT be polynomial float (nor polynomial integer showed here), but Float, or Symbolic Float and even Expression Float if you want. PS: In the light of polynomial, (2d) is a non-zero polynomial, so that it's always safe to write (1/(2d)), but it's actually non-safe to do it in the domain of float(or integer). b:=a is meaningless, of course. But there are many scenarios fricas )clear all All user variables and function definitions have been cleared. fricas i:=10  (29) Type: PositiveInteger? fricas a: Union(Variable a, Integer) Type: Void fricas b: Union(Variable b, Integer) Type: Void fricas b:= (i>0=>1; a)  (30) Type: Union(Integer,...) which is meaningful. Re: Expression Float --Bill Page, Mon, 07 Jul 2008 17:02:43 -0700 reply Be careful, Expression Float may not be what you think it is. In Axiom Expression R is a domain constructor which extends rational functions with coefficients in R (Fraction Polynomial R) by adding a set of common operators, e.g. sin, sqrt, etc. Again the appearance of Float here does not say anything specific about the result of evaluating the expression or even the values that can be associated with it's generators. I do not know why one might prefer Expression Float over Polynomial Float or even Polynomial Integer. We wish to place a restriction on the possible values that certain symbols can take. Such symbols and expressions formed from them certainly cannot live in a numeric domain such as Float. Except in certain circumstances (mentioned previously) I think a domain such as a:Union(Variable(a),Float) and the domains to which it can be coerced (such as Polynomial, Expression, ...) does already represent such a symbolic expressions fairly well. But 1) What is Symbolic Float? Can you give a description? And 2) How can I express the concept of "non-zero polynomial" in Axiom? I might use a domain that does not include zero for example a:Union(Variable(a),PositiveInteger) but there is no general domain of NonZero anything. Well, I don't like Expression Float. But I notice somebody takes it as a choice, so I put it there with "if you want". Ok, back to my own point. what's the justification of that the multiplication of two floats returns a polynomial float? Even the value is unknown, the type is certain, and float is closed under multiplication, so the return must be still a float, right? AFAIK, Axiom currently support only polynomials with coefficients of known values. Then the only zero-polynomial(Integer) is 0$Polynomial Integer, others are non-zero polynomials.

Re: justification --Bill Page, Tue, 08 Jul 2008 22:22:15 -0700 reply
The multiplication of a Float and some unknown symbolic value must produce a symbolic expression of some kind. If we know that the currently unknown symbolic value can only take values from Float, then we can deduce from knowledge of multiplication in Float that the value of the symbolic expression representing the multiplication of a Float with this unknown symbolic value must also only take values from Float.

But Axiom currently does not have any domain whose values are symbolic expressions which only evaluate to values in some specific domain. Polynomial is one of the existing domains in Axiom whose values are symbolic expressions (of a very specific type). Symbolic expression in the domain Expression are more general but still rather restricted in form. Finally there is InputForm which consists of fully unevaluated expressions of the most general form allowed in Axiom.

Perhaps what you have called "Symbolic Float" could be implemented as an extension of the domain I called "Indeterminant" above.

Re: nonzero polynomials --Bill Page, Tue, 08 Jul 2008 22:35:03 -0700 reply
yixin.cao wrote:
the only zero-polynomial(Integer) is 0\$Polynomial Integer, others are non-zero polynomials.

But a polynomial containing at least one monomial term is symbolic. Certain combinations of values substituted for the symbols may result in zero (such values are called is "solution").

yixin.cao wrote:
In the light of polynomial, (2d) is a non-zero polynomial, so that it's always safe to write (1/(2d))

If a value of 0 is subsituted for d in this "non-zero polynomial" then in what sense is 1/(2d) safe?

Re: nonzero polynomials --yixin.cao, Wed, 09 Jul 2008 07:19:05 -0700 reply
For the first question: I don't understand your point on the "one monomial term", polynomial is always symbolic (with the exception of constants). Even in the example of (d: Union(Variable d, Integer), d*2), if you treat (2d) together as the coefficient and the whole as a constant polynomial, then you already admit that (2d) is an integer, haaa..

For the second question: Yes, polynomial (x-1) might be evaluated to 0 (all of Integer,Float,Complex?), but this doesn't change the matter of (x-1) is not a zero-polynomial. Well, do you think (x**2-1)/(x-1) = (x+1) is legal and guaranteed in the domain of polynomial? But it's not in the domain of Float/Integer. You don't want to modify the rule of polynomial to accommodate this, right?

The polynomial 0, which may be considered to have no terms at all, is called the zero polynomial. (from http://en.wikipedia.org/wiki/Polynomial)

Re: justification --yixin.cao, Wed, 09 Jul 2008 07:32:17 -0700 reply
"But Axiom currently does not have any domain whose values are symbolic expressions which only evaluate to values in some specific domain" This statement is not the justification of picking one domain that is closest to the requirement and using it, but a justification of making one.

Domain "Indeterminant" is a good example for this, thanks.

Re: nonzero polynomials --Bill Page, Wed, 09 Jul 2008 14:19:02 -0700 reply
Yes,
fricas
x:Polynomial Float
Type: Void
fricas
p:=(x^2-1)/(x-1)
 (31)
Type: Fraction(Polynomial(Float))
fricas
eval(p,x=1)
 (32)
Type: Fraction(Polynomial(Float))

is certainly legal and safe in the domain of polynomial where the result is required to be a polynomial although it seems that Axiom is being careful to give the result type as Fraction Polynomial Float and not automatically Polynomial Float.

Do you agree that it is not safe if all we know about x is that it is a symbol which can be replaced with a Float?

In this case a domain like Indeterminant can deal with it.

fricas
)library INDET
Indeterminant is already explicitly exposed in frame initial Indeterminant will be automatically loaded when needed from /var/aw/var/LatexWiki/INDET.NRLIB/INDET w:Union(Integer,Indeterminant)
Type: Void
fricas
q:=(w^2-1)/(w-1)
 (33)
Type: Indeterminant
fricas
w:=1
 (34)
Type: Union(Integer,...)
fricas
eval(q)
>> Error detected within library code: division by zero

Reasonable result --yixin.cao, Wed, 09 Jul 2008 14:42:06 -0700 reply
This is the reasonable result most users can expect.

 Subject:   Be Bold !! ( 14 subscribers )