Revision history [back]

the problem are neither Python nor recursion but Sage expressions. If I replace those with lists and strings the computation time drops to 0:

def mydiff(s,x='x'):
    if not x in str(s):
        return 0
    if s == x:
        return 1
    elif s == ['log',x]:
        return ['pow',x,-1]
    elif s == ['sin',x]:
        return ['cos',x]
    elif s == ['cos',x]:
        return ['mul',-1,['sin',x]]
    elif s == ['tan',x]:
        return ['add',1,['pow',['tan',x],2]]
    elif s == ['arcsin',x]:
        return ['pow',['add',1,['mul',-1,['pow',x,2]]],-1/2]
    elif s == ['arctan',x]:
        return ['pow',['add',1,['pow',x,2]],-1]
    op = s[0]
    ops = s[1:]
    if op == 'pow' and ops[0]==x and ops[1] in Rationals():
        return ['mul',ops[1],['pow',ops[0],(ops[1]-1)]]
    elif op == 'add':
        return ['sum',map(mydiff,ops)]
    elif op == 'mul':
        if len(ops) == 2:
            if ops[0] in Rationals():
                return ['mul',ops[0],mydiff(ops[1])]
            else:
                f = ops[0]; g = ops[1]
                return ['add',['mul',g,mydiff(f)],['mul',f,mydiff(g)]]

Now:

var('k')
sage: %time mydiff(s)
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
['sum', [['mul', 1, ['mul', 1, ['pow', 'x', 0]]], ['mul', 2, ['mul', 2, ['pow', 'x', 1]]], ['mul', 3, ['mul', 3, ['pow', 'x', 2]]], ['mul', 4, ['mul', 4, ['pow', 'x', 3]]], ['mul', 5, ['mul', 5, ['pow', 'x', 4]]], ['mul', 6, ['mul', 6, ['pow', 'x', 5]]], ['mul', 7, ['mul', 7, ['pow', 'x', 6]]], ['mul', 8, ['mul', 8, ['pow', 'x', 7]]], ['mul', 9, ['mul', 9, ['pow', 'x', 8]]], ['mul', 10, ['mul', 10, ['pow', 'x', 9]]]]]

the problem are is neither Python Python, nor recursion recursion, but Sage expressions. If I replace those with lists and strings the computation time drops to 0:

def mydiff(s,x='x'):
    if not x in str(s):
        return 0
    if s == x:
        return 1
    elif s == ['log',x]:
        return ['pow',x,-1]
    elif s == ['sin',x]:
        return ['cos',x]
    elif s == ['cos',x]:
        return ['mul',-1,['sin',x]]
    elif s == ['tan',x]:
        return ['add',1,['pow',['tan',x],2]]
    elif s == ['arcsin',x]:
        return ['pow',['add',1,['mul',-1,['pow',x,2]]],-1/2]
    elif s == ['arctan',x]:
        return ['pow',['add',1,['pow',x,2]],-1]
    op = s[0]
    ops = s[1:]
    if op == 'pow' and ops[0]==x and ops[1] in Rationals():
        return ['mul',ops[1],['pow',ops[0],(ops[1]-1)]]
    elif op == 'add':
        return ['sum',map(mydiff,ops)]
    elif op == 'mul':
        if len(ops) == 2:
            if ops[0] in Rationals():
                return ['mul',ops[0],mydiff(ops[1])]
            else:
                f = ops[0]; g = ops[1]
                return ['add',['mul',g,mydiff(f)],['mul',f,mydiff(g)]]

Now:

var('k')
sage: %time mydiff(s)
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
['sum', [['mul', 1, ['mul', 1, ['pow', 'x', 0]]], ['mul', 2, ['mul', 2, ['pow', 'x', 1]]], ['mul', 3, ['mul', 3, ['pow', 'x', 2]]], ['mul', 4, ['mul', 4, ['pow', 'x', 3]]], ['mul', 5, ['mul', 5, ['pow', 'x', 4]]], ['mul', 6, ['mul', 6, ['pow', 'x', 5]]], ['mul', 7, ['mul', 7, ['pow', 'x', 6]]], ['mul', 8, ['mul', 8, ['pow', 'x', 7]]], ['mul', 9, ['mul', 9, ['pow', 'x', 8]]], ['mul', 10, ['mul', 10, ['pow', 'x', 9]]]]]

the problem is neither Python, nor recursion, but Sage expressions. If I replace those with lists and strings the computation time drops to 0:

def mydiff(s,x='x'):
    if not x in str(s):
        return 0
    if s == x:
        return 1
    elif s == ['log',x]:
        return ['pow',x,-1]
    elif s == ['sin',x]:
        return ['cos',x]
    elif s == ['cos',x]:
        return ['mul',-1,['sin',x]]
    elif s == ['tan',x]:
        return ['add',1,['pow',['tan',x],2]]
    elif s == ['arcsin',x]:
        return ['pow',['add',1,['mul',-1,['pow',x,2]]],-1/2]
    elif s == ['arctan',x]:
        return ['pow',['add',1,['pow',x,2]],-1]
    op = s[0]
    ops = s[1:]
    if op == 'pow' and ops[0]==x and ops[1] in Rationals():
        return ['mul',ops[1],['pow',ops[0],(ops[1]-1)]]
    elif op == 'add':
        return ['sum',map(mydiff,ops)]
    elif op == 'mul':
        if len(ops) == 2:
            if ops[0] in Rationals():
                return ['mul',ops[0],mydiff(ops[1])]
            else:
                f = ops[0]; g = ops[1]
                return ['add',['mul',g,mydiff(f)],['mul',f,mydiff(g)]]

Now:

sage: var('k')
sage: s = ['add']+[['mul',k,['pow','x',k]] for k in [1..10]]
sage: %time mydiff(s)
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
['sum', [['mul', 1, ['mul', 1, ['pow', 'x', 0]]], ['mul', 2, ['mul', 2, ['pow', 'x', 1]]], ['mul', 3, ['mul', 3, ['pow', 'x', 2]]], ['mul', 4, ['mul', 4, ['pow', 'x', 3]]], ['mul', 5, ['mul', 5, ['pow', 'x', 4]]], ['mul', 6, ['mul', 6, ['pow', 'x', 5]]], ['mul', 7, ['mul', 7, ['pow', 'x', 6]]], ['mul', 8, ['mul', 8, ['pow', 'x', 7]]], ['mul', 9, ['mul', 9, ['pow', 'x', 8]]], ['mul', 10, ['mul', 10, ['pow', 'x', 9]]]]]