faster diffs()

[GoogleCodeExporter]

It would be nice if diffs() had a flag to return a generator instead of a
list. Maybe for n=None?

multiplicity() could use it more effectively, as it doesn't know how many
derivatives it needs to evaluate.

But multiplicity() is not very useful, so this is low priority.

Original issue reported on code.google.com by Vinzent.Steinberg@gmail.com on 17 Nov 2008 at 5:35

[GoogleCodeExporter]

It wouldn't help that much; the information from the first n derivatives can't 
be
reused for computing the n+1'th derivative. The only thing that could be delayed
would be forward difference transform.

Original comment by fredrik....@gmail.com on 17 Nov 2008 at 5:46

[GoogleCodeExporter]

It can store the old information in a list. The point is that you don't know 
*before*
how large n is, it depends on the values of the derivatives.

Original comment by Vinzent.Steinberg@gmail.com on 17 Nov 2008 at 6:25

[GoogleCodeExporter]

But then, you may as well call diff() repeatedly. As I said, diffs is only 
faster if
you do know the number of terms in advance.

Original comment by fredrik....@gmail.com on 17 Nov 2008 at 6:35

[GoogleCodeExporter]

Sorry, I misunderstood you.

Original comment by Vinzent.Steinberg@gmail.com on 17 Nov 2008 at 6:38

• Changed state: Invalid

[GoogleCodeExporter]

One can compute faster a sequence of derivatives in the case of the quad method 
by
caching the values computed on the integration circle.
See attached file.

Original comment by mario.pe...@gmail.com on 17 Nov 2008 at 7:10

Attachments:

• diff2.py

[GoogleCodeExporter]

The speedup is not that big, so given the added complexity, I don't think it's 
worth it.

Original comment by fredrik....@gmail.com on 17 Nov 2008 at 8:03

[GoogleCodeExporter]

For functions which are very slow to compute, the speed-up tends to the number 
of
derivatives.
Putting in the attached file the function

NN = 100
def f(x):
    s = 0
    for i in range(NN):
        s += atan(x)
    return s

on my laptop the speedup with 9 derivatives is
NN    
1    2.5x
10   6x
100  8.5x

Original comment by mario.pe...@gmail.com on 17 Nov 2008 at 9:26

[GoogleCodeExporter]

The speedup is worth it in my opinion.

Original comment by Vinzent.Steinberg@gmail.com on 18 Nov 2008 at 2:33

• Changed title: faster diffs()
• Changed state: Started

[GoogleCodeExporter]

How about implementing this with a generic caching decorator? It would be 
useful at
other times, for example to evaluate a sequence of integrals with a fixed weight
function.

Original comment by fredrik....@gmail.com on 18 Nov 2008 at 5:39

[GoogleCodeExporter]

Actually, a reasonable way to implement diffs (as well as taylor) as a generator
would be to compute the derivatives in batches 1, 2, 4, 8, 16, 32, ... unless an
upper limit is specified. Then at worst twice as many function evaluations as 
needed
will be performed, and at most 2x the necessary precision will be used.

Original comment by fredrik....@gmail.com on 19 Nov 2008 at 11:13