Path: news.mathworks.com!newsfeed-00.mathworks.com!nlpi057.nbdc.sbc.com!prodigy.net!news.glorb.com!news2.glorb.com!news.cse.ohio-state.edu!usenet01.sei.cmu.edu!elk.ncren.net!news.niu.edu!news!rusin
From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: comp.soft-sys.math.maple,sci.math,sci.op-research,sci.math.num-analysis,comp.soft-sys.matlab
Subject: Re: How to take 200th order derivative, and then evaluate it numerically?
Date: 18 Mar 2009 18:37:56 GMT
Organization: Northern Illinois Univ., Dept. of Mathematical Sciences
Lines: 66
Message-ID: <gprf24$76p$1@news.math.niu.edu>
References: <f6ebcf2b-4782-4984-aebc-7cdb5b28ccee@p2g2000prf.googlegroups.com> <gpr9nj$rkp$1@fred.mathworks.com>
NNTP-Posting-Host: vesuvius.math.niu.edu
X-Trace: news.math.niu.edu 1237401476 7385 131.156.3.93 (18 Mar 2009 18:37:56 GMT)
X-Complaints-To: news@math.niu.edu
NNTP-Posting-Date: 18 Mar 2009 18:37:56 GMT
Xref: news.mathworks.com comp.soft-sys.math.maple:24553 sci.math:1160956 sci.op-research:29215 sci.math.num-analysis:107036 comp.soft-sys.matlab:525954


<excellentfeng@gmail.com> wrote
> We need to take the 200th order derivative of a complicated formula,
> and then evaluate it numerically.

I suppose the formula represents an analytic function. If so, you're really
just asking for just one term in the Taylor series  f(z) = sum  a_n  z^n . 
So your question is how to evaluate just one term in the series (perhaps
emphasizing that you don't need the lower-order terms first; you can liken 
this to the "spigot" algorithms for the bits of  pi ).

If you compute a line integral of  f(z)/z^201  around the origin, all the
summands  a_n z^n  contribute zero except the one with  n=200. Divide by
2 pi,  multiply by 200! (it's roughly 2^1245) and you have your derivative.
So if you can compute values of  f  with thousand-bit precision, then you
can compute this line integral numerically and you have your derivative.


In article <gpr9nj$rkp$1@fred.mathworks.com>,
Steven Lord <slord@mathworks.com> wrote:

>My first question:  why?  I can see why you might want to take the 1st 
>derivative, or the 2nd derivative, or maybe even the 3rd or 4th derivative 
>of a function.  The 200th?  How are you planning to use the value you 
>receive from this procedure?

Oh, I can jump in here: there are certainly questions that can be
phrased as requiring a number which is computable (e.g. via generating
functions) as the 200th derivative of a function. So I would be
very interested in hearing other answers to this question. 

Here's an example: in order to factor an thousand-bit integer  N,
it would be more or less sufficient to compute the thousand binomial 
coefficients  a_k = binomial(2^{k+1}, 2^k)  modulo  N  (for k=1, 2, ..., 1000).
So the question "how hard is it to factor  N ?" changes to
"how hard is it to compute  a_k mod N ?"  The ideal state would be 
to know how to do that computation in an amount of time which is
a polynomial in  k, but as far as I know, no one knows how to do that;
I don't know how to compute the thousand bits of  a_500  before the
universe dies a cold death. (I don't know why it should be so hard; 
these  a_k  are just a little smaller than  4^(2^k), and the numbers
4^(2^k) mod N  themselves can be computed in  O(k)  steps.)

But consider this: these  a_k  are among the coefficients in the
Taylor series of  f(z) = 1/sqrt(1-4z). So, just as the OP, I find
myself wishing I could compute high-order derivatives  f^(m)(0)  
of my function. (The OP's "m" is 200; mine is, say, m=2^500 !)

And indeed I gave a recipe above for computing these Taylor coefficients.
There is no real difficulty for me to compute values of  f(z)/z^(2^k),
either: the denominator is computed with  k  squarings, and the numerator
can be computed with  k  iterations of  Newton's method, giving approximations
of  f(z)  which are off by at most  O(z^(-2^k)). 

But I have problems that the OP doesn't have, because of how long it takes
to compute an "operation", even a simple sum, when I am dealing with
enormously long strings of digits (bits), and also because of the number 
of evaluations of  f  which I would need to make in order to compute the
line integral numerically. It seems like a waste because the value I'm 
trying to compute is an integer, and I only need its value mod  N ,
(i.e. 1000 bits of data) but I don't know how to get around these problems.

So my question is similar to the OP's question: if I have a quick and
accurate way to compute values of  f,  is there a quick and accurate
way to compute any one term of its Taylor series?

dave