why is symbolic comparison so slow?

edit

This is more like a comment to Mike's answer, but it's rather long and I don't see how to add code to comments, so I'll put it here.

A workaround to check if an expression is trivially equal to another is to use match().

sage: tan(x).match(tan(x)) is not None
True
sage: tan(x).match(log(x)) is not None
False

This is very fast:

sage: sage: %timeit bool(sin(x) == sin(x))
625 loops, best of 3: 19.8 µs per loop
sage: sage: %timeit bool(sin(x) == log(x))
5 loops, best of 3: 639 ms per loop
sage: sage: %timeit bool(sin(x).match(log(x)) is not None)
625 loops, best of 3: 8.3 µs per loop
sage: sage: %timeit bool(sin(x).match(sin(x)) is not None)
625 loops, best of 3: 10.9 µs per loop

Here is the mydiff() function using this hack (and removing the reduce() call for sums):

from operator import add, mul, pow
def mydiff2(s,x=x):
    if not s.has(x):
        return 0
    op = s.operator()
    ops = s.operands()
    if s.match(x) is not None:
        return 1
    elif op is log and ops[0].match(x) is not None:
        return 1/x
    elif op is sin and ops[0].match(x) is not None:
        return cos(x)
    elif op is cos and ops[0].match(x) is not None:
        return -sin(x)
    elif op is tan and ops[0].match(x) is not None:
        return 1+tan(x)**2
    elif op is arcsin and ops[0].match(x) is not None:
        return 1/sqrt(1-x**2)
    elif op is arctan and ops[0].match(x) is not None:
        return 1/(1+x**2)
    elif op is pow and (ops[0].match(x) is not None) and ops[1]._is_numeric():
        return ops[1]*ops[0]**(ops[1]-1)
    elif op is add:
        return sum(map(mydiff2, ops))
    elif op is mul:
        f = ops[0]; g = reduce(mul,ops[1:])
        return g*mydiff2(f) + f*mydiff2(g)

Now I get:

sage: var('k')
k
sage: inp = sum(k*x^k,k,0,10)
sage: inp
10*x^10 + 9*x^9 + 8*x^8 + 7*x^7 + 6*x^6 + 5*x^5 + 4*x^4 + 3*x^3 + 2*x^2 + x
sage: load ../symbolic_eq2.py
sage: %time res2 = mydiff2(inp)
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
sage: res2
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

Note that speeding up symbolic comparison is #6799 on trac.

One obvious thing is that the wall time is considerably longer than the cpu-time. That can mean your process didn't get 100% of the CPU time or that Sage called out to a different process (maxima?) to get some results. Indeed, if you run:

import cProfile
S=sum(k*x^k,k,0,10)
cProfile.run("mydiff(S)")

you'll find 4995 calls to

maxima.py:722(_eval_line)

indicating that there were 4995 calls to another process. There are also various calls to various "simplify" routines, so either in construction or in comparison of symbolic expressions, Sage did feel the need to simplify things.

In short: If you want to do pattern matching on symbolic expressions, do not use "==". It is apparently already reserved for a fairly expensive equality test.

I am surprised that this program still triggers calls out to maxima. I don't think it's "reduce", since that only receives 18 calls and takes negligible time in the profile. All the other operations, including "==" should really map to straight pynac operations.

technically, apart from mhamptons comment, there are two problems: (I've just briefly looked at the code and maybe I didn't understand it)

1. your code is recursive and that is not a good idea for python.
2. you rip apart the expression and before each recursion and then you partially rebuild it with reduce. this creates a bunch of calculations for a new expression which you don't need if your differentiator would take a list of operands and a operation directly.

Because pure python is slow. No offense but why would you want to do this? Symbolic calculations are usually done with pynac (C++ wrapped into Sage) or Maxima (40 year old optimized Lisp wrapped into Sage). If you want something about symbolic differentiation improved you should contribute to those projects.

What do you need that isn't already there? For your example on my computer:

var('x,k')
time diff(sum(k*x^k,k,0,10),x)

gives

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
Time: CPU 0.02 s, Wall: 0.04 s