Algebra in C#

[cbmeeks]

I'm working on a project that deals with some algebra. Or, actually,
just math in general. It could eventually work it's way up to more
advanced math, analytics, etc.

Anyway, I'm looking for ideas on how to store the actual formulas
using classes.

For example:

class X
{
public Value;
}

class Y
{
public Value;
}

X x = new X();
X.Value = 10;

Y y = new Y();
Y.Value = 20;

Now, I want to store this formula:

x.Value + y.Value * 2

Which should give the value of 60.

Hope that makes sense. I thought about having a Formula class with a
List of classes and then build the formula when needed. Taking care
to add special classes like "multiply", etc but I don't think I like
that idea.

I also thought about storing a string somehow and then just parsing
the string and substitute keyword for classes.

Any suggestions?

Thanks

[Peter Duniho]

On Fri, 25 Apr 2008 10:55:53 -0700, cbmeeks <cb*****@gmail.comwrote:

I'm working on a project that deals with some algebra. Or, actually,
just math in general. It could eventually work it's way up to more
advanced math, analytics, etc.

Anyway, I'm looking for ideas on how to store the actual formulas
using classes.

Well, it would take a very deep knowledge of exactly how this is going to
be used to provide any really good, specific advice.

However, a reasonably common approach would be to treat your expressions
as a tree graph of operators and operands. An operator instance would
have one or more operands as children. An operand could be a single
value, or the root of a sub-tree that represents a more complex
expression. Both operators and operands would share a base class used as
the fundamental element in the tree; that base class would be simply
something that returns a value.

Operator precedence and explicit precedence (i.e. parentheses) would
control the layout of the graph. The result of any given graph would be
obtained by recursively evaluating the operands for each operator until
you wind back up at the top having evaluated the root operator.

For added difficulty points, allow your values to take on more than one
actual numeric type, handling type conversion as necessary as you process
the graph. :)

That said, I would guess that there's already some solutions out there.
If you're looking for anything really elaborate, you might find it makes
more sense to search for and use a pre-existing package. I don't know for
sure that any exist, but it seems likely. Google would be helpful there,
obviously. :)

Pete

[cbmeeks]

Thanks for replying.

Well, it would take a very deep knowledge of exactly how this is going to
be used to provide any really good, specific advice.

However, a reasonably common approach would be to treat your expressions
as a tree graph of operators and operands. An operator instance would
have one or more operands as children. An operand could be a single
value, or the root of a sub-tree that represents a more complex
expression. Both operators and operands would share a base class used as
the fundamental element in the tree; that base class would be simply
something that returns a value.

This sounds like the lines I was thinking of. I like the tree idea.
I will need to think of how to store a formula like:

M1 * 15 + (M2 / M3)

Where Mx = a class that returns a value.

I'm actually doing this in SQL and it works but it seems a little
kludgy. In SQL, I am storing each operator/operand as a row, then
assembling the row as a string and then parse the formula.

My long term goal is to allow a user to type the formula out in a text
box so I guess strings are still in my future.

Operator precedence and explicit precedence (i.e. parentheses) would
control the layout of the graph. The result of any given graph would be
obtained by recursively evaluating the operands for each operator until
you wind back up at the top having evaluated the root operator.

Right. This is what I am going to have to work on.

>
For added difficulty points, allow your values to take on more than one
actual numeric type, handling type conversion as necessary as you process
the graph. :)

That is interesting because I've only been working with doubles since
I thought that would allow more than enough precision for most
business related values. Is that wise?

>
That said, I would guess that there's already some solutions out there.
If you're looking for anything really elaborate, you might find it makes
more sense to search for and use a pre-existing package. I don't know for
sure that any exist, but it seems likely. Google would be helpful there,
obviously. :)

Pete

Yeah, but this is something I hope to offer as a service one day and I
enjoy the learning experience. :-)

Thanks Pete, you've been a lot of help.

-cecil

[=?Utf-8?B?UGV0ZXIgQnJvbWJlcmcgW0MjIE1WUF0=?=]

All mathematical "Formulas" in code eventually get reduced to math operations
on defined types and they return a result of a defined type (it could be a
complex number, matrix, doesn't matter). If you look at some of the
open-source math libraries, this is how they are structured. In other words,
you don't "store a formula", instead you have a method or methods with code
the *performs* the particular mathematical operation and returns it's result.
-- Peter
To be a success, arm yourself with the tools you need and learn how to use
them.

Site: http://www.eggheadcafe.com
http://petesbloggerama.blogspot.com
http://ittyurl.net
"cbmeeks" wrote:

I'm working on a project that deals with some algebra. Or, actually,
just math in general. It could eventually work it's way up to more
advanced math, analytics, etc.

Anyway, I'm looking for ideas on how to store the actual formulas
using classes.

For example:

class X
{
public Value;
}

class Y
{
public Value;
}

X x = new X();
X.Value = 10;

Y y = new Y();
Y.Value = 20;

Now, I want to store this formula:

x.Value + y.Value * 2

Which should give the value of 60.

Hope that makes sense. I thought about having a Formula class with a
List of classes and then build the formula when needed. Taking care
to add special classes like "multiply", etc but I don't think I like
that idea.

I also thought about storing a string somehow and then just parsing
the string and substitute keyword for classes.

Any suggestions?

Thanks

[cbmeeks]

All mathematical "Formulas" in code eventually get reduced to math operations

on defined types and they return a result of a defined type (it could be a
complex number, matrix, doesn't matter). If you look at some of the
open-source math libraries, this is how they are structured. In other words,
you don't "store a formula", instead you have a method or methods with code
the *performs* the particular mathematical operation and returns it's result.
-- Peter

AH. That makes sense. Right now, I have some methods like that.

For example, I can do something like:

Metric m = new Metric();
m.Sum();
m.Avg();
m.PowSum();
m.MultiplySumBy(15);
etc...

That's working pretty well. So it's easy to do:

double r = m.Sum() + 15;

I will keep chugging along until I find a way to represent these chain
of actions :-)

[Ian Semmel]

I think you basicaly need a stack which pushes values and operators,
taking into account operator precedence.

I would find some open source compiler and see how they do it.

"cbmeeks" <cb*****@gmail.comwrote in message
news:94**********************************@b64g2000 hsa.googlegroups.com:

I'm working on a project that deals with some algebra. Or, actually,
just math in general. It could eventually work it's way up to more
advanced math, analytics, etc.

Anyway, I'm looking for ideas on how to store the actual formulas
using classes.

For example:

class X
{
public Value;
}

class Y
{
public Value;
}

X x = new X();
X.Value = 10;

Y y = new Y();
Y.Value = 20;

Now, I want to store this formula:

x.Value + y.Value * 2

Which should give the value of 60.

Hope that makes sense. I thought about having a Formula class with a
List of classes and then build the formula when needed. Taking care
to add special classes like "multiply", etc but I don't think I like
that idea.

I also thought about storing a string somehow and then just parsing
the string and substitute keyword for classes.

Any suggestions?

Thanks

[Peter Duniho]

On Fri, 25 Apr 2008 13:23:35 -0700, Ian Semmel <an****@rocketcomp.com.au>
wrote:

I think you basicaly need a stack which pushes values and operators,
taking into account operator precedence.

I would find some open source compiler and see how they do it.

For what it's worth, if you're going to follow this approach ("you" being
the OP, that is :) ), you might look at the FORTH language, and possibly
even try to find some source code for a FORTH interpreter.

One of the interesting things about FORTH is that it uses "reverse Polish
notation" for expressions. This is a little hard to read sometimes, but
it's actually very natural for a machine-based implementation that uses a
stack. If it's appropriate for your problem to represent your expressions
in RPN, a stack-based idea could work very well.

If not, then it gets a little tricky to convert a conventional
mathematical expression into a stack-based solution. Or looked at another
way, the tree representation I described earlier is actually a reasonably
natural way to use a stack (you wind up using recursion, which is
implicitly stack-based, to resolve the expression).

Pete

[Peter Duniho]

On Fri, 25 Apr 2008 11:53:57 -0700, cbmeeks <cb*****@gmail.comwrote:

This sounds like the lines I was thinking of. I like the tree idea.
I will need to think of how to store a formula like:

M1 * 15 + (M2 / M3)

Where Mx = a class that returns a value.

Sure. And each part is essentially an "Mx" also. That is, the class
representing the * operator is "a class that returns a value" and which
has two operands. Your tree is made up of these classes. Some will
simply be values, some will be operators that take one or more inputs.

The above formula would look like, in a tree, something like this (the
parentheses in that example are redundant, assuming normal operator
precedence):

PlusOp +---- MultiplyOp +---- M1
| |
| +---- 15
|
+---- DivideOp +---- M2
|
+---- M3

The + operator, having the lowest precedent and there being no parentheses
to override the precedence, is the root of the tree. It has as its
operands the two sub-expressions involving the * and / operators,
respectively.

The children of each node are operands. In two cases (the immediate
children of PlusOp), the operands are themselves operators with their own
children. At the leaf nodes of the tree, you have simple value instances.

I'm actually doing this in SQL and it works but it seems a little
kludgy. In SQL, I am storing each operator/operand as a row, then
assembling the row as a string and then parse the formula.

My long term goal is to allow a user to type the formula out in a text
box so I guess strings are still in my future.

The hardest part will be parsing the expression. However, that's a
relatively well-understood computer science problem. You should have
little trouble finding existing references on how to do it.

[...]

>For added difficulty points, allow your values to take on more than one
actual numeric type, handling type conversion as necessary as you
process
the graph. :)

That is interesting because I've only been working with doubles since
I thought that would allow more than enough precision for most
business related values. Is that wise?

Define "business related values". For many business applications, the
"decimal" type is actually more appropriate. Floating point ("double" or
"float") is susceptible to rounding errors. In financial applications,
this is often impermissible. The "decimal" type can suffer rounding
errors (try dividing one dollar into 3 equal parts :) ) as well depending
on how they are used, but the rules for dealing with rounding are usually
better-defined in that context.

That said, it may well be feasible to select a single numeric type,
whether "double" or "decimal", as your "lingua franca" for all of the
numeric expressions, rather than supporting mixed types.

Pete

[Gilles Kohl [MVP]]

On Fri, 25 Apr 2008 11:03:04 -0700, "Peter Duniho"
<Np*********@nnowslpianmk.comwrote:

[...]

>That said, I would guess that there's already some solutions out there.
If you're looking for anything really elaborate, you might find it makes
more sense to search for and use a pre-existing package. I don't know for
sure that any exist, but it seems likely. Google would be helpful there,
obviously. :)

Indeed - one of them confirms a hunch I had: that the solution to the
"representation" and "evaluation" parts of the problem (although not
the parsing) is already built into C# 3.0 in the form of expression
trees. Here's a very nice article that also provides the parsing, by
converting to a postfix representation (as you suggested) before
assembling the tree.

http://www.jot.fm/issues/issue_2008_...mn4/index.html

Regards,
Gilles.

[Ian Semmel]

"Peter Duniho" <Np*********@nnowslpianmk.comwrote in message
news:op***************@petes-computer.local:

On Fri, 25 Apr 2008 13:23:35 -0700, Ian Semmel
<an****@rocketcomp.com.au>
wrote:

I think you basicaly need a stack which pushes values and operators,
taking into account operator precedence.

I would find some open source compiler and see how they do it.

For what it's worth, if you're going to follow this approach ("you"
being
the OP, that is :) ), you might look at the FORTH language, and possibly
even try to find some source code for a FORTH interpreter.

One of the interesting things about FORTH is that it uses "reverse
Polish
notation" for expressions. This is a little hard to read sometimes, but
it's actually very natural for a machine-based implementation that uses
a
stack. If it's appropriate for your problem to represent your
expressions
in RPN, a stack-based idea could work very well.

If not, then it gets a little tricky to convert a conventional
mathematical expression into a stack-based solution. Or looked at
another
way, the tree representation I described earlier is actually a
reasonably
natural way to use a stack (you wind up using recursion, which is
implicitly stack-based, to resolve the expression).

Pete

Possibly the easiest compiler to understand is the RATFOR compiler
invented by Kernighan and Plauger back in the 1970's which was described
in their book "Software Tools". It was a bit of a best-seller, and
basically led to "C" and Pascal (although both these were based on
algol).

Source code is available at :

http://sepwww.stanford.edu/software/ratfor.html

http://www.dgate.org/ratfor/

You have to know "C" to understand it, but it shows how everything is
parsed and tokenized.

[cbmeeks]

Thanks for all of the suggestions guys!! I am going to look into the
RPN....that is very interesting!

Define "business related values". For many business applications, the
"decimal" type is actually more appropriate. Floating point ("double" or
"float") is susceptible to rounding errors. In financial applications,
this is often impermissible. The "decimal" type can suffer rounding
errors (try dividing one dollar into 3 equal parts :) ) as well depending
on how they are used, but the rules for dealing with rounding are usually
better-defined in that context.

AHH!!! Yeah, I had forgotten about that. hmmm...all of the Math
routines I use use double as input. Wouldn't
You guys have been great. Wish me luck!

[=?ISO-8859-1?Q?Arne_Vajh=F8j?=]

Ian Semmel wrote:

Possibly the easiest compiler to understand is the RATFOR compiler
invented by Kernighan and Plauger back in the 1970's which was described
in their book "Software Tools". It was a bit of a best-seller, and
basically led to "C" and Pascal (although both these were based on algol).

I belive that Kernighan invented C before RATFOR. And that Wirth
created Pascal before both of them.

Arne