Revision history [back]

The previous answers are incorrect in their assessment of the problem -- the slowdown is indeed coming from trying to decide whether "x == tan(x)" is True or False. In particular, the slowdown comes a lot from our overhead in talking to Maxima. Sage performs the following things when trying to test whether an equation is zero or not.

1. Check to see if both sides are constants. If they are, compare the constants.

2. Ask GiNaC / Pynac to see if the expressions are structurally equal (i.e., they have are the same expression trees.) If they are, then we can immediately say things are equal.

3. Check to make sure that there are no assumptions on any of the variables. If there are, then we have to immediately send things to Maxima.

4. If there are no assumptions, then we can try evaluating at a number of points to try to verify that they are provably different using interval arithmetic. This is done in the test_relation method of Expression objects.

5. If that doesn't work, we send it to Maxima. Since the Maxima output gives False if they are not equal as well as if it can't prove they are equal, we can only rely on a True answer from Maxima. Thus, a number of simplifications are done to try to "prove" equality. This is all done in sage.symbolic.relation.test_relation_maxima

6. If all of the above things don't work, then we have to return False.

There are a number of areas for improvement:

1. Most importantly there are quite a few cases in which the test_relation method fails. For example, there some code to check to see if using CIF for the values isn't working and if so switch over to RIF. However, that code is broken. Fixing that would allow something like

   sage: eq = x == tan(x)
   sage: eq.test_relation()
   False
   

   instead of giving NotImplemented like it does now.

2. We can add a syntactically_equal method which just exposes, GiNaC's relational_to_bool test. If we just do that and modify mydiff appropriately, then we get

   sage: k = var('k')
   sage: s = sum(k*x^k,k,0,10)
   sage: %time mydiff(s, x)
   CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
   Wall time: 0.02 s
   100*x^9 + 81*x^8 + 64*x^7 + 49*x^6 + 36*x^5 + 25*x^4 + 16*x^3 + 9*x^2 + 4*x + 1
   

I will make tickets for these and add the links to them here.

The previous answers (with the exception of Nils Bruin's) are incorrect in their assessment of the problem -- the slowdown is indeed coming from trying to decide whether "x == tan(x)" is True or False. In particular, the slowdown comes a lot from our overhead in talking to Maxima. Sage performs the following things when trying to test whether an equation is zero or not.

1. Check to see if both sides are constants. If they are, compare the constants.

2. Ask GiNaC / Pynac to see if the expressions are structurally equal (i.e., they have are the same expression trees.) If they are, then we can immediately say things are equal.

3. Check to make sure that there are no assumptions on any of the variables. If there are, then we have to immediately send things to Maxima.

4. If there are no assumptions, then we can try evaluating at a number of points to try to verify that they are provably different using interval arithmetic. This is done in the test_relation method of Expression objects.

5. If that doesn't work, we send it to Maxima. Since the Maxima output gives False if they are not equal as well as if it can't prove they are equal, we can only rely on a True answer from Maxima. Thus, a number of simplifications are done to try to "prove" equality. This is all done in sage.symbolic.relation.test_relation_maxima

6. If all of the above things don't work, then we have to return False.

There are a number of areas for improvement:

1. Most importantly there are quite a few cases in which the test_relation method fails. For example, there some code to check to see if using CIF for the values isn't working and if so switch over to RIF. However, that code is broken. Fixing that would allow something like

   sage: eq = x == tan(x)
   sage: eq.test_relation()
   False
   

   instead of giving NotImplemented like it does now.

2. We can add a syntactically_equal method which just exposes, GiNaC's relational_to_bool test. If we just do that and modify mydiff appropriately, then we get

   sage: k = var('k')
   sage: s = sum(k*x^k,k,0,10)
   sage: %time mydiff(s, x)
   CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
   Wall time: 0.02 s
   100*x^9 + 81*x^8 + 64*x^7 + 49*x^6 + 36*x^5 + 25*x^4 + 16*x^3 + 9*x^2 + 4*x + 1
   

I will make tickets for these and add the links to them here.