I am writing a simple numeric constraint system in Lisp.
Given an equation in some form such as:
Z = X + Y
my representation of it is
(Z (+ X Y))
which I use further with appropriate getter and setter functions for
X, Y and Z.
I would also like to generate the equation in terms of the other
variables, ie. I would like to generate:
(Y (- Z X)) and
(X (- Z Y))
for use in constraint propagation.
It is easy enough for simple cases, though how would I obtain from:
(Z (+ (* 3 X) (* 4 Y))) ie. Z = 3X + 4Y
the relationships:
(X (/ (- Z (* 4 Y)) 3)) and
(Y (/ (- Z (* 3 X)) 4))
Again, I am concerned (for the moment) with constraints that are
linear or at least separable (such as Z = P*Q*R).
I would appreciate any ideas on how to implement this elegantly.
Thanks,
--Nicky
·····@rnd.stern.nyu.edu
In article <·····@rnd.GBA.NYU.EDU> ········@rnd.stern.nyu.edu (Nicky Ranganathan) writes:
>It is easy enough for simple cases, though how would I obtain from:
>
> (Z (+ (* 3 X) (* 4 Y))) ie. Z = 3X + 4Y
>the relationships:
> (X (/ (- Z (* 4 Y)) 3)) and
> (Y (/ (- Z (* 3 X)) 4))
You would have to use recursion, to approach your goal step by step.
(Z (+ (* 3 X) (* 4 Y)))
((* 3 X) (- Z (* 4 Y))) ;; (X (+ Y Z)) -> (Y (- X Z))
(X (/ (- Z (* 4 Y)) 3)) ;; ((* X Y) Z) -> (Y (/ Z X))
As for an elegant way to implement the individual transformations, this is
a good application for a pattern matching system. A good AI text (such as
Peter Norvig's "Paradigms of AI Programming: Case Studies in Common Lisp")
should have examples of such techniques.
--
Barry Margolin
System Manager, Thinking Machines Corp.
······@think.com {uunet,harvard}!think!barmar
If you are dealing only with linear equations you are better off choosing
a canonical representation that is not biased towards what variables are to
be input and what are to be output. Thus for additive linear equations,
rewrite them in the following forms:
additive: a x + b y + ... = 0
multiplicative: x^a * y^b * ... = 1
E.g, assuming you have a fixed number of variables, your accessors are
just vector accesses into the coefficient or exponent vectors once you
have chosen a canonical ordering for the variables.
If you are not already familiar with equational or logic based programming
languages, you may want to read up on them since there are similar
issues involved in abstracting control away from the logic (equations).
For example, see the languages OBJ3 and PROLOG.
If you are serious about solving systems of algebraic equations you should
read up on the Grobner basis algorithm. There is a '93 text in the Springer
Grad. Texts in Math series, by Becker et. al. that is a good starting
point (this requires knowledge of basic undergraduate algebra).
Most of the major computer algebra systems have Grobner implementations,
e.g. Macsyma, Maple, Mathematica, in my order of preference.
You will never come close to the power of the algebraic geometry based
Grobner based techniques by using AI based heuristics for solving equations.
Even so, there are "AI" based approaches to solving transcendental
equations which you might find interesting by Bundy et.al.