be able to tell if two expressions are equal

[evykassirer]

This is blocked on our new parser because it has to do with tree equivalence #128

This would be helpful for:

• cancelling like terms: e.g. (x + 2)/((x + x) doesn't cancel right now
• anyone that wants to build learning tools on top of mathsteps that lets learners write in their open work that is checked along the way

There might be different solutions for different situations - sometimes we might want to know if two expressions are equal in any way, and sometimes we might want to decide they're "very close to equal" i.e. they're just the same terms in different orderings

One thing for "very close to equal" would probably be to make a standardized ordering of terms, so we could always sort the terms in that way and check if the expressions are the same.

I would love to hear more thoughts on this!

[evykassirer]

@tkosan :

I forked the YACAS CAS in 2008 to create MathPiper. YACAS's core CAS capabilities were incomplete, so I have MathPiper use the Reduce CAS for its heavy-duty conventional CAS needs. The expression equivalence functionality that was used for the above testing is buried deep within Reduce, and it is written in RLisp.

I like to think I know enough about how conventional CASs work to implement an expression comparison function from scratch, but it would take awhile. A quicker and better way to obtain this functionality for mathsteps is to use a conventional JavaScript CAS as an embedded CAS, like MathPiper does with Reduce. The Khan Academy KAS system should work, and so should Algebrite.

One way to use a conventional CAS to determine if two expressions are equivalent is to subtract one from the other. If the result is 0, then they are equivalent. For example, if (19/3 - 4y / 3) - ((-4*y + 19)/3) is evaluated in the Algebrite page above, it will return 0.

If you are interested in exploring the possibility of using a conventional JavaScript CAS to give mathsteps expression comparison (and maybe other CAS) capabilities, I would be happy to evaluate likely candidates for this purpose.

@kevinbarabash :

I like the KAS system b/c it's relatively simple to implement. It evaluates both expressions at a number of different values and compares them at a number of carefully chosen values. The nice thing about this approach is that it can compare expressions that the system isn't able to simplify yet. The downside though, is that the algorithm is exponential on the number of different variables in the expression, ouch!

[hmaurer]

I know nothing about CAS systems, but could we possibly use some form of pathfinding algorithm coupled with a heuristic? It seems to make sense to consider a graph of all mathematical expressions understood by the system, with edges for operations that do not change the value of expressions. Then the problem of checking whether two expressions are equal boils down to finding a path between them in the graph.

Clearly a system like KAS might be better suited to this problem; I am just wondering what other approaches exist. Especially if you consider things from an educational standpoint: if you try semi-random values for variables you can only claim that two expressions are equal within some degree of accuracy, and you have very little information about why they are equal. However, if you find a sequence of operations to get from one to the other you could actually show that to the user, should he want to. (e.g. "by those three steps you can get from your teacher's solution to the one you found!").

@tkosan would you have some insights on this?

[tkosan]

@hmaurer, the CAS community developed algorithms a long time ago for determining if two expressions are equivalent. A standard approach is to simplify both expressions to a canonical form, and then compare these forms syntactically.

If the ultimate goal of the mathsteps project is to simply model the ad hoc process that "school math" teaches for solving cherry-picked math problems, then determining if expressions are equivalent using semi-random values for variables is probably adequate. However, if the goal is to eventually support the teaching of K-16 mathematics systematically and at a deep level, I recommend using state of the art solutions to problems like this whenever feasible because the obsolete "school math" will eventually be replaced by modern ways to teach math such as Computer Based Math, which can only be done using state of the art techniques.

A question that is related to this issue is why did Khan Academy deprecate their 100% software-based exercise framework and switch to using humans to create exercises when logic-based AI software such as AGILMAT has existed for years that automatically generates math problems using scientific methods? @kevinbarabash, do you have any insight on this question?

[aelnaiem]

@tkosan What would using a state of the art system entail?

[tkosan]

@aelnaiem

What would using a state of the art system entail?

It would entail including a conventional CAS such as Algebrite in MathSteps as a library or at least including the part of a conventional CAS that is able to simplify expressions to a normal form which can be compared syntactically.

[aelnaiem]

Cool! That's pretty clear

[tkosan]

@aelnaiem I spent some time this weekend looking at JavaScript CASs, and so far I think Algebrite is the most promising candidate for possible inclusion in mathsteps. It can solve the "telling if two expressions are equal" problem that is discussed in this issue, and it would also be useful for testing various parts of mathsteps such as equation solving, simplification, factoring, and (in the future) differentiation and integration.

Having a conventional CAS in mathsteps would also provide the ability to enhance the user experience by always returning an answer even if the capability to return the steps for this answer is not implemented yet.

The size of the unminified version of Algebrite is around 650k. Some functionality could probably be removed from Algebrite to reduce its size if needed.