Thread Subject: How to take 200th order derivative, and then evaluate it numerically?

Hi all,

We need to take the 200th order derivative of a complicated formula,
and then evaluate it numerically.

What's the best way to handle this?

More specifically, we figured that it's impossible to do this via
finite difference, i.e. do everything completely in the numerical
domain, because the noise will be huge and error will dominate.

So a plan was to first obtain the 200th order derivative thru symbolic
calculation in Maple, Matlab, Mathematica, and then copy the huge
result and somehow make it into a form that is numerically evaluable
either in Matlab or C++. Then evaluate that huge expression
numerically. Still, that sounds daunting, the symbolic result of 200th
order derivative will be huge and we are not sure if Maple or
Mathematica can handle it.

Another possibility is to do some sort of Automatic Differentiation.
But we are new to AD. Is it possible that with the help from an AD
package, we just need to give inputs of the parameter values, and the
package will crank out the numerical result of the 200th order
derivative with almost no error?

We see that lots of free packages are in C/C++ or Fortune, which are
not convenient for fast prototyping(we are at evaluating stage, if
this idea doesn't work, we don't want to spend too much time on it).
So are there free AD packages that can go with Matlab or Mathematica
or Maple that can take 200th order differentiation and are convenient
for prototyping? Which one is the best AD package that we could try
on? If it doesn't work, then we would discard this crazy idea of
taking 200th order derivative completely.

Please shed some lights on us!

Thanks a lot!

I don't know if this would complete in a reasonable amount of time on a
complicated example, but I tried in the Symbolic Math Toolbox:
syms x
y = exp(2*x);
z = diff(y,200)
In less than a second I got the answer:
z =
1606938044258990275541962092341162602522202993782792835301376*exp(2*x)

The Symbolic Math Toolbox is not free, but if you have access to it, why
not give it a try on a more complicated example?

Alan Weiss
MATLAB mathematical toolbox documentation

excellentfeng@gmail.com wrote:
> Hi all,
>
> We need to take the 200th order derivative of a complicated formula,
> and then evaluate it numerically.
>
> What's the best way to handle this?
>
> More specifically, we figured that it's impossible to do this via
> finite difference, i.e. do everything completely in the numerical
> domain, because the noise will be huge and error will dominate.
>
> So a plan was to first obtain the 200th order derivative thru symbolic
> calculation in Maple, Matlab, Mathematica, and then copy the huge
> result and somehow make it into a form that is numerically evaluable
> either in Matlab or C++. Then evaluate that huge expression
> numerically. Still, that sounds daunting, the symbolic result of 200th
> order derivative will be huge and we are not sure if Maple or
> Mathematica can handle it.
>
> Another possibility is to do some sort of Automatic Differentiation.
> But we are new to AD. Is it possible that with the help from an AD
> package, we just need to give inputs of the parameter values, and the
> package will crank out the numerical result of the 200th order
> derivative with almost no error?
>
> We see that lots of free packages are in C/C++ or Fortune, which are
> not convenient for fast prototyping(we are at evaluating stage, if
> this idea doesn't work, we don't want to spend too much time on it).
> So are there free AD packages that can go with Matlab or Mathematica
> or Maple that can take 200th order differentiation and are convenient
> for prototyping? Which one is the best AD package that we could try
> on? If it doesn't work, then we would discard this crazy idea of
> taking 200th order derivative completely.
>
> Please shed some lights on us!
>
> Thanks a lot!

On Wed, 18 Mar 2009 09:42:07 -0700 (PDT), excellentfeng@gmail.com
wrote:

>Hi all,
>
>We need to take the 200th order derivative of a complicated formula,
>and then evaluate it numerically.
>
>What's the best way to handle this?
 
Firs, you should think 10 times whether you need this. Seems to be a
nonsense for me.

A.L.

excellentfeng@gmail.com wrote in message <f6ebcf2b-4782-4984-aebc-7cdb5b28ccee@p2g2000prf.googlegroups.com>...
> Hi all,
>
> We need to take the 200th order derivative of a complicated formula,
> and then evaluate it numerically.
>
> What's the best way to handle this?

help rand

Or, perhaps even more accurate is this:

help zeros

<excellentfeng@gmail.com> wrote in message
news:f6ebcf2b-4782-4984-aebc-7cdb5b28ccee@p2g2000prf.googlegroups.com...
> Hi all,
>
> We need to take the 200th order derivative of a complicated formula,
> and then evaluate it numerically.

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?

*snip*

--
Steve Lord
slord@mathworks.com

On Mar 18, 9:42=A0am, excellentf...@gmail.com wrote:
> Hi all,
>
> We need to take the 200th order derivative of a complicated formula,
> and then evaluate it numerically.
>
> What's the best way to handle this?
>
> More specifically, we figured that it's impossible to do this via
> finite difference, i.e. do everything completely in the numerical
> domain, because the noise will be huge and error will dominate.
>
> So a plan was to first obtain the 200th order derivative thru symbolic
> calculation in Maple, Matlab, Mathematica, and then copy the huge
> result and somehow make it into a form that is numerically evaluable
> either in Matlab or C++. Then evaluate that huge expression
> numerically. Still, that sounds daunting, the symbolic result of 200th
> order derivative will be huge and we are not sure if Maple or
> Mathematica can handle it.
>
> Another possibility is to do some sort of Automatic Differentiation.
> But we are new to AD. Is it possible that with the help from an AD
> package, we just need to give inputs of the parameter values, and the
> package will crank out the numerical result of the 200th order
> derivative with almost no error?
>
> We see that lots of free packages are in C/C++ or Fortune, which are
> not convenient for fast prototyping(we are at evaluating stage, if
> this idea doesn't work, we don't want to spend too much time on it).
> So are there free AD packages that can go with Matlab or Mathematica
> or Maple that can take 200th order differentiation and are convenient
> for prototyping? Which one is the best AD package that we could try
> on? If it doesn't work, then we would discard this crazy idea of
> taking 200th order derivative completely.
>
> Please shed some lights on us!
>
> Thanks a lot!

The first question is what the heck are you doing?

If you have a formula, you can use a CAS like Mathematica and ask it
for the 200th derivative and see if it converges on returning a
formula. of course, that in itself might be suspect. If you are
strictly using numerical methods - toss this statement out the window
and re-evaluate what you are asking for because on the surface it
sounds nonsensical.

~A

excellentfeng@gmail.com wrote:
> Hi all,
>
> We need to take the 200th order derivative of a complicated formula,
> and then evaluate it numerically.
>
> What's the best way to handle this?
>
> More specifically, we figured that it's impossible to do this via
> finite difference, i.e. do everything completely in the numerical
> domain, because the noise will be huge and error will dominate.
>
> So a plan was to first obtain the 200th order derivative thru symbolic
> calculation in Maple, Matlab, Mathematica, and then copy the huge
> result and somehow make it into a form that is numerically evaluable
> either in Matlab or C++. Then evaluate that huge expression
> numerically. Still, that sounds daunting, the symbolic result of 200th
> order derivative will be huge and we are not sure if Maple or
> Mathematica can handle it.
>
> Another possibility is to do some sort of Automatic Differentiation.
> But we are new to AD. Is it possible that with the help from an AD
> package, we just need to give inputs of the parameter values, and the
> package will crank out the numerical result of the 200th order
> derivative with almost no error?
>
> We see that lots of free packages are in C/C++ or Fortune, which are
> not convenient for fast prototyping(we are at evaluating stage, if
> this idea doesn't work, we don't want to spend too much time on it).
> So are there free AD packages that can go with Matlab or Mathematica
> or Maple that can take 200th order differentiation and are convenient
> for prototyping? Which one is the best AD package that we could try
> on? If it doesn't work, then we would discard this crazy idea of
> taking 200th order derivative completely.
>
> Please shed some lights on us!
>
> Thanks a lot!

The first question is what everyone is asking:

Is this trip necessary?

The next questions are based on an affirmative answer to the first:

Do any useful transforms Tf (T: Fourier, Laplace,... [there must
be others with useful expressions for T(derivative)]) exist?

If so, look at T(f^(200)). Once you have T(f), this
should be the trivial step.

What about the inverse transform of T(f^(200))? How ugly is it?

Just my two bits' worth.

Dale

On Mar 18, 9:42=A0am, excellentf...@gmail.com wrote:
> Hi all,
>
> We need to take the 200th order derivative of a complicated formula,
> and then evaluate it numerically.
>
> What's the best way to handle this?
>
> More specifically, we figured that it's impossible to do this via
> finite difference, i.e. do everything completely in the numerical
> domain, because the noise will be huge and error will dominate.
>
> So a plan was to first obtain the 200th order derivative thru symbolic
> calculation in Maple, Matlab, Mathematica, and then copy the huge
> result and somehow make it into a form that is numerically evaluable
> either in Matlab or C++. Then evaluate that huge expression
> numerically. Still, that sounds daunting, the symbolic result of 200th
> order derivative will be huge and we are not sure if Maple or
> Mathematica can handle it.
>
> Another possibility is to do some sort of Automatic Differentiation.
> But we are new to AD. Is it possible that with the help from an AD
> package, we just need to give inputs of the parameter values, and the
> package will crank out the numerical result of the 200th order
> derivative with almost no error?
>
> We see that lots of free packages are in C/C++ or Fortune, which are
> not convenient for fast prototyping(we are at evaluating stage, if
> this idea doesn't work, we don't want to spend too much time on it).
> So are there free AD packages that can go with Matlab or Mathematica
> or Maple that can take 200th order differentiation and are convenient
> for prototyping? Which one is the best AD package that we could try
> on? If it doesn't work, then we would discard this crazy idea of
> taking 200th order derivative completely.
>
> Please shed some lights on us!
>
> Thanks a lot!
How did you even get the coefficients for a 200th order polynomial?

I agree with the others that say this is non sense. Any number, that
is not extreme close to 1 taken to the 200 power, will either cause a
numeric overflow or be rounded down to 0 unless you have a very high
precision calculator.

However, if the equation is a 200th order polynomial then one can
compute the coefficients for any of the derivative functions easily
enough in C or Fortran. Then the equation can be evaluated using
Horner's method. No matlab, mathematica or maple required. I have
done this before with 5 to 7th order polynomials. It would be easy
enough to expand the arrays to do this with 200th order polynomials.

Peter Nachtwey

excellentfeng@gmail.com wrote:
...
> ...If it doesn't work, then we would discard this crazy idea of
> taking 200th order derivative completely.

Sounds like a plan...

--

In article <f6ebcf2b-4782-4984-aebc-7cdb5b28ccee@p2g2000prf.googlegroups.com>,
 excellentfeng@gmail.com writes:
>Hi all,
>
>We need to take the 200th order derivative of a complicated formula,
>and then evaluate it numerically.
>
>What's the best way to handle this?
>
>More specifically, we figured that it's impossible to do this via
>finite difference, i.e. do everything completely in the numerical
>domain, because the noise will be huge and error will dominate.

correct. maybe you use 1000 digits precision??

>
>So a plan was to first obtain the 200th order derivative thru symbolic
>calculation in Maple, Matlab, Mathematica, and then copy the huge
>result and somehow make it into a form that is numerically evaluable
>either in Matlab or C++. Then evaluate that huge expression
>numerically. Still, that sounds daunting, the symbolic result of 200th
>order derivative will be huge and we are not sure if Maple or
>Mathematica can handle it.

depends

>
>Another possibility is to do some sort of Automatic Differentiation.
>But we are new to AD. Is it possible that with the help from an AD
>package, we just need to give inputs of the parameter values, and the
>package will crank out the numerical result of the 200th order
>derivative with almost no error?

no no. AD is very good for the first derivative, has already problems with hessians,
but for higher order I never saw it. (the computational graph of a comp graph of
a comp graph ... )


>
>We see that lots of free packages are in C/C++ or Fortune, which are
>not convenient for fast prototyping(we are at evaluating stage, if
>this idea doesn't work, we don't want to spend too much time on it).
>So are there free AD packages that can go with Matlab or Mathematica
>or Maple that can take 200th order differentiation and are convenient
>for prototyping? Which one is the best AD package that we could try
>on? If it doesn't work, then we would discard this crazy idea of
>taking 200th order derivative completely.
>
>Please shed some lights on us!
>
>Thanks a lot!

 maybe your teacher wanted to shock you somehow ,
 but there are some chances you didn't consider:

 if it is a rational function , perform the decomposition into partial
 fractions, then the formal derivative is obvious, and possibly combine
 back.

 nice exercise :

 the 200-th derivative of arctan(x)

 if it is a function with known or easy power series expansion,
 differentiate this one

 the same for a fourier expansion: attention: think about the convergence
 criteria

 what is that good for?
 maybe you must evaluate the remainder term of a 100-node gauss-quadrature??
 (bad joke)

hth
peter

<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

<excellentfeng@gmail.com> wrote in message
news:f6ebcf2b-4782-4984-aebc-7cdb5b28ccee@p2g2000prf.googlegroups.com...
> Hi all,
>
> We need to take the 200th order derivative of a complicated formula,
> and then evaluate it numerically.
>

First things first: Fire the person who came up with the number 200... it
should have been 199.

excellentfeng@gmail.com writes:

> Hi all,
>
> We need to take the 200th order derivative of a complicated formula,
> and then evaluate it numerically.
>
> What's the best way to handle this?
>
> More specifically, we figured that it's impossible to do this via
> finite difference, i.e. do everything completely in the numerical
> domain, because the noise will be huge and error will dominate.
>
> So a plan was to first obtain the 200th order derivative thru symbolic
> calculation in Maple, Matlab, Mathematica, and then copy the huge
> result and somehow make it into a form that is numerically evaluable
> either in Matlab or C++. Then evaluate that huge expression
> numerically. Still, that sounds daunting, the symbolic result of 200th
> order derivative will be huge and we are not sure if Maple or
> Mathematica can handle it.
>
> Another possibility is to do some sort of Automatic Differentiation.
> But we are new to AD. Is it possible that with the help from an AD
> package, we just need to give inputs of the parameter values, and the
> package will crank out the numerical result of the 200th order
> derivative with almost no error?
>
> We see that lots of free packages are in C/C++ or Fortune, which are
> not convenient for fast prototyping(we are at evaluating stage, if
> this idea doesn't work, we don't want to spend too much time on it).
> So are there free AD packages that can go with Matlab or Mathematica
> or Maple that can take 200th order differentiation and are convenient
> for prototyping? Which one is the best AD package that we could try
> on? If it doesn't work, then we would discard this crazy idea of
> taking 200th order derivative completely.
>
> Please shed some lights on us!
>
> Thanks a lot!

Perhaps what you might try is computing a Taylor series up to order x^200.
There still might be some numerical difficulties, but it might not be so bad.
 For example, in Maple:

  f:= x^3*sin(x)/(x - cos(x));
  Digits:= 20;
  200! * coeff( series(f, x=0.3, 201), x-0.3, 200);

    -.90246797086526191165e446
--
Robert Israel israel@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

Robert Israel wrote:
...
> Perhaps what you might try is computing a Taylor series up to order x^200.
> There still might be some numerical difficulties, ... [snip for effect]

Think??? :)

> For example, in Maple:
>
> f:= x^3*sin(x)/(x - cos(x));
> Digits:= 20;
> 200! * coeff( series(f, x=0.3, 201), x-0.3, 200);
>
> -.90246797086526191165e446

Hmmmm....any idea how many of those digits are actually meaningful in
front of that 10**446 exponent???

--

{Some of the original newsgroups removed from the list: sorry, my news server has a
crossposting limit of 4 newsgroups!}


excellentfeng@gmail.com wrote:

> We need to take the 200th order derivative of a complicated formula,
> and then evaluate it numerically.

> So a plan was to first obtain the 200th order derivative thru symbolic
> calculation in Maple, Matlab, Mathematica, and then copy the huge
> result and somehow make it into a form that is numerically evaluable
> either in Matlab or C++. Then evaluate that huge expression
> numerically. Still, that sounds daunting, the symbolic result of 200th
> order derivative will be huge and we are not sure if Maple or
> Mathematica can handle it.

With any modern version of maple, you can calculate the derivative
and then in Maple, (e.g.)

f := exp(x^3) - exp(x^(-3));
CodeGeneration[Matlab](unapply(diff(f,x$200),x),optimize,digits=16,output="f200.m",resultname=f200);

This will directly write a file named f200.m containing a procedure named f200 that does the
differentiation in Matlab.

Caution: the number of digits used on some of the constants may greatly exceed the 16
listed in the digits= parameter. This should lead you to question the accuracy of the output.
Another problem is that differentiating 200 times is likely to lead to a factor of 200!
(or so, perhaps even 205!) as one of the constants -- and that value exceeds the maximum
Matlab real number. Unfortunately, slipping a simplify(factor()) around the diff() does not
remove the 10^308 constant from the output... it just makes the final statement calculating the
return value into a huge unreadable statement.

In article <gprk0t$g8$1@aioe.org>, dpb <none@non.net> wrote:

> Robert Israel wrote:
> ...
> > Perhaps what you might try is computing a Taylor series up to order x^200.
> > There still might be some numerical difficulties, ... [snip for effect]
>
> Think??? :)
>
> > For example, in Maple:
> >
> > f:= x^3*sin(x)/(x - cos(x));
> > Digits:= 20;
> > 200! * coeff( series(f, x=0.3, 201), x-0.3, 200);
> >
> > -.90246797086526191165e446
>
> Hmmmm....any idea how many of those digits are actually meaningful in
> front of that 10**446 exponent???

I don't get ANY. Using Mathematica, and the commands

f[x_] = x^3 * Sin[x]/(x - Cos[x]);
a = 3/10;
q = 200! * Coefficient[Series[f[x + a], {x, N[a, 2000], 201}], x^200]

(i.e., using 2000-digit precision), I get as output

8.79706766309285531402058935431446364695557682377643868580539624307543\
3813635170485359021030321735306371237255460885001870669592062272255754\
6811798739911826558405041319246793190060013582632484660798804338639829\
3677497582276781551805425896909210803391220133566681155945000972282627\
0692882515065842765398727066878423388527454848431676355424447555976171\
7362630436351635192836439246091937861477700209751375257425678609745663\
1485232770451072262442515742371840311536121150067032833905408799375142\
8105502883510239941596597308186610428729501136776398590701695574041338\
6975242778619445713968545975844143146964882124308981769154558016449941\
1567681808863587798175197072693803457483601743383577315698634205703705\
3868859280352521965983155519440299399272535965564387743166865563501490\
1480369166792083169418839803175212971169119214904804916044561800575025\
0771513386032793328831890682203270760620393851840263530296059615280085\
7033088303440083093200749796467206434398433793567452930766246051370380\
3698107871076710080131452293836149387506048965829763565001806694499146\
1810219474350028345839056832965424219228595190047972663418201733913850\
8246700095809447655044553220714537798969707319935194914526012068081080\
6210154194150405075121029247671378458058680688604742558715468066043142\
2741282672261152073353657296454567641371140261797813339278678807753088\
0168735036976654246639887730891366191064192337684932419310928233540923\
9981278936062880224390643444860496474151019886455346989575020619857174\
9695402221976286543825694523159480697218429325203913636735567724996871\
2453332488236538342660984769811105037613490027917909424973805659192699\
3628345493851270616604909474801236609765889934117075983314385416221233\
9858564165392993939159640504400071083456475018607584848375789700395435\
3978324345557471056134749552317765853161430754113665525334594231640545\
9493374689336586922233202178132503930023983656978124892451476942480899\
7644028138163525412702361745808942154119575168496464593462586541700193\
5315806189348358721672465614921305949*10^548

(that has 1996 digits, I believe). Which isn't very far from what
Mathematica returns with 20-digit precision,

8.797067663092855*10^548

The exact answer is a rational function of cos(3/10) and sin(3/10).
The easiest way to find the coefficients might be to set up a
recurrence formula for them. Ugly. But don't ask Mathematica to
return the exact answer; it will take forever, for a simple demo
example.

As for the OP, I would suggest doing this with 16 digits, then 32, then
64, ... and compare the answers. Crude, but it usually works.

--
Ron Bruck

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

><excellentfeng@gmail.com> wrote in message
>news:f6ebcf2b-4782-4984-aebc-7cdb5b28ccee@p2g2000prf.googlegroups.com...
>> Hi all,

>> We need to take the 200th order derivative of a complicated formula,
>> and then evaluate it numerically.

>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?

I can see a possible reason, although done should try
to find another way. If a Laplace transform, or a
bilateral Laplace transform, can be computed by some
procedure, but the computation cannot be extended in
the complex plane, the function can be approximated by
using high-order derivatives, and 200 might even be
considered low for this problem.

--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558

Robert Israel wrote:
> For example, in Maple:
>
> f:= x^3*sin(x)/(x - cos(x));
> Digits:= 20;
> 200! * coeff( series(f, x=0.3, 201), x-0.3, 200);
>
> -.90246797086526191165e446

dpb <none@non.net> wrote:
> Hmmmm....any idea how many of those digits are actually meaningful in
> front of that 10**446 exponent???

In article <180320091613300494%bruck@math.usc.edu>,
Ronald Bruck <bruck@math.usc.edu> wrote:
>
>I don't get ANY. Using Mathematica, and the commands
>
>f[x_] = x^3 * Sin[x]/(x - Cos[x]);
>a = 3/10;
>q = 200! * Coefficient[Series[f[x + a], {x, N[a, 2000], 201}], x^200]
>
>(i.e., using 2000-digit precision), I get as output
>
>8.79706766309285531[...]721672465614921305949*10^548
>
>(that has 1996 digits, I believe). Which isn't very far from what
>Mathematica returns with 20-digit precision,
>
>8.797067663092855*10^548

I think the Mathematica code should be something like
 q = 200! *Coefficient[Series[f[x], {x, N[a,2000], 201}], (x-N[a,2000])^200 ]
which returns
    -9.024679708652619116077333659727619804699158461886[...]*10^445
in agreement with Maple.

dave

In article <gprf24$76p$1@news.math.niu.edu>, Dave Rusin
<rusin@vesuvius.math.niu.edu> wrote:

> 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).

Dave,

Intriguing. Care to elaborate?

Bob

On Mar 19, 12:42=A0am, excellentf...@gmail.com wrote:
> Hi all,
>
> We need to take the 200th order derivative of a complicated formula,
> and then evaluate it numerically.
>
> What's the best way to handle this?
>
> More specifically, we figured that it's impossible to do this via
> finite difference, i.e. do everything completely in the numerical
> domain, because the noise will be huge and error will dominate.
>
> So a plan was to first obtain the 200th order derivative thru symbolic
> calculation in Maple, Matlab, Mathematica, and then copy the huge
> result and somehow make it into a form that is numerically evaluable
> either in Matlab or C++. Then evaluate that huge expression
> numerically. Still, that sounds daunting, the symbolic result of 200th
> order derivative will be huge and we are not sure if Maple or
> Mathematica can handle it.
>
> Another possibility is to do some sort of Automatic Differentiation.
> But we are new to AD. Is it possible that with the help from an AD
> package, we just need to give inputs of the parameter values, and the
> package will crank out the numerical result of the 200th order
> derivative with almost no error?
>
> We see that lots of free packages are in C/C++ or Fortune, which are
> not convenient for fast prototyping(we are at evaluating stage, if
> this idea doesn't work, we don't want to spend too much time on it).
> So are there free AD packages that can go with Matlab or Mathematica
> or Maple that can take 200th order differentiation and are convenient
> for prototyping? Which one is the best AD package that we could try
> on? If it doesn't work, then we would discard this crazy idea of
> taking 200th order derivative completely.
>
> Please shed some lights on us!
>
> Thanks a lot!

hello check this site you will find some idea http://www.mlibaba.com

Bob Delaney <delaneyrm@earthlink.net> wrote in message <190320090430067217%delaneyrm@earthlink.net>...
> In article <gprf24$76p$1@news.math.niu.edu>, Dave Rusin
> <rusin@vesuvius.math.niu.edu> wrote:
>
> > 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).
>
> Dave,
>
> Intriguing. Care to elaborate?
>
> Bob

It seems this is a less than useful algorithm.
Those binomial coefficients get very large, very
quickly. While it is true that you do not need
to compute the entire binomial coefficient,
just the coefficient mod N, it is still not terribly
useful, because after you obtain those coefficients
modulo N, you would need to factor each of
those residues too.

It acts like a sieve. Not a terribly efficient one either,
in that factoring a 1000 bit number simply requires
you to factor many other assorted integers, all of
the same magnitude.

Here are the first few binomial coefficients in
that list.

>> BC = @(k) nchoosek(vpi(2)^(k+1),vpi(2)^k);
>> BC(1)
ans =
   6

>> BC(2)
ans =
   70

>> BC(3)
ans =
   12870

>> BC(4)
ans =
   601080390

>> BC(5)
ans =
   1832624140942590534

>> BC(6)
ans =
   23951146041928082866135587776380551750

>> BC(7)
ans =
5768658823449206338089748357862286887740211701975162032608436567264518750790

>> BC(8)
ans =
472553303154964924989004370051186389478210715642481882577328859153566070336566100844650299634054239969857431328433974960326174706663509667348266572071494

Now, can I factor 187 = 11*17?

>> mod(BC(1),187)
ans =
   6
>> mod(BC(2),187)
ans =
   70
>> mod(BC(3),187)
ans =
   154
>> mod(BC(4),187)
ans =
   119

See that the factors of 187 appear among the factors
of these numbers.

>> factor(mod(BC(1),187))
ans =
   2 3
>> factor(mod(BC(2),187))
ans =
   2 5 7
>> factor(mod(BC(3),187))
ans =
    2 7 11
>> factor(mod(BC(4),187))
ans =
    7 17

Yes, there are some other assorted junk, non-factors
in those numbers. The binomial coefficient is simply
an easy way to write a huge product of a massive
set of numbers. It may even fail sometimes too, on
numbers with a pair of prime factors of similar size,
both with the same number of bits.

I'll argue that this algorithm is not unlike my scheme
to go to the moon without a rocket. I'll simply build
a big set of stairs, with really large steps, and walk
there. Anybody want to go to Mars? (Don't ask for a
stairway to heaven.)

John

On Mar 18, 10:18=A0am, amzoti <amz...@gmail.com> wrote:
> On Mar 18, 9:42=A0am, excellentf...@gmail.com wrote:
>
>
>
> > Hi all,
>
> > We need to take the 200th order derivative of a complicated formula,
> > and then evaluate it numerically.
>
> > What's the best way to handle this?
>
> > More specifically, we figured that it's impossible to do this via
> > finite difference, i.e. do everything completely in the numerical
> > domain, because the noise will be huge and error will dominate.
>
> > So a plan was to first obtain the 200th order derivative thru symbolic
> > calculation in Maple, Matlab, Mathematica, and then copy the huge
> > result and somehow make it into a form that is numerically evaluable
> > either in Matlab or C++. Then evaluate that huge expression
> > numerically. Still, that sounds daunting, the symbolic result of 200th
> > order derivative will be huge and we are not sure if Maple or
> > Mathematica can handle it.
>
> > Another possibility is to do some sort of Automatic Differentiation.
> > But we are new to AD. Is it possible that with the help from an AD
> > package, we just need to give inputs of the parameter values, and the
> > package will crank out the numerical result of the 200th order
> > derivative with almost no error?
>
> > We see that lots of free packages are in C/C++ or Fortune, which are
> > not convenient for fast prototyping(we are at evaluating stage, if
> > this idea doesn't work, we don't want to spend too much time on it).
> > So are there free AD packages that can go with Matlab or Mathematica
> > or Maple that can take 200th order differentiation and are convenient
> > for prototyping? Which one is the best AD package that we could try
> > on? If it doesn't work, then we would discard this crazy idea of
> > taking 200th order derivative completely.
>
> > Please shed some lights on us!
>
> > Thanks a lot!
>
> The first question is what the heck are you doing?
>
> If you have a formula, you can use a CAS like Mathematica and ask it
> for the 200th derivative and see if it converges on returning a
> formula. of course, that in itself might be suspect. If you are
> strictly using numerical methods - toss this statement out the window
> and re-evaluate what you are asking for because on the surface it
> sounds nonsensical.
>
> ~A

Yeah, I am sure after long time running, Mathematica will return a
huge result, but then how do I plugin numerical parameter values to
get numerical results? We can judge from the end numerical results
whether it is good or bad idea to go this route...

On Mar 18, 11:12=A0am, pnachtwey <pnacht...@gmail.com> wrote:
> On Mar 18, 9:42=A0am, excellentf...@gmail.com wrote:
>
> > Hi all,
>
> > We need to take the 200th order derivative of a complicated formula,
> > and then evaluate it numerically.
>
> > What's the best way to handle this?
>
> > More specifically, we figured that it's impossible to do this via
> > finite difference, i.e. do everything completely in the numerical
> > domain, because the noise will be huge and error will dominate.
>
> > So a plan was to first obtain the 200th order derivative thru symbolic
> > calculation in Maple, Matlab, Mathematica, and then copy the huge
> > result and somehow make it into a form that is numerically evaluable
> > either in Matlab or C++. Then evaluate that huge expression
> > numerically. Still, that sounds daunting, the symbolic result of 200th
> > order derivative will be huge and we are not sure if Maple or
> > Mathematica can handle it.
>
> > Another possibility is to do some sort of Automatic Differentiation.
> > But we are new to AD. Is it possible that with the help from an AD
> > package, we just need to give inputs of the parameter values, and the
> > package will crank out the numerical result of the 200th order
> > derivative with almost no error?
>
> > We see that lots of free packages are in C/C++ or Fortune, which are
> > not convenient for fast prototyping(we are at evaluating stage, if
> > this idea doesn't work, we don't want to spend too much time on it).
> > So are there free AD packages that can go with Matlab or Mathematica
> > or Maple that can take 200th order differentiation and are convenient
> > for prototyping? Which one is the best AD package that we could try
> > on? If it doesn't work, then we would discard this crazy idea of
> > taking 200th order derivative completely.
>
> > Please shed some lights on us!
>
> > Thanks a lot!
>
> How did you even get the coefficients for a 200th order polynomial?
>
> I agree with the others that say this is non sense. Any number, that
> is not extreme close to 1 taken to the 200 power, will either cause a
> numeric overflow or be rounded down to 0 unless you have a very high
> precision calculator.
>
> However, if the equation is a 200th order polynomial then one can
> compute the coefficients for any of the derivative functions easily
> enough in C or Fortran. =A0Then the equation can be evaluated using
> Horner's method. =A0No matlab, mathematica or maple required. =A0I have
> done this before with 5 to 7th order polynomials. It would be easy
> enough to expand the arrays to do this with 200th order polynomials.
>
> Peter Nachtwey

Hi Peter,

Yes, essentially we are finding the 200th coefficient of the Taylor
expansion of a very complicated analytical expression.

Let's say it's given by f(x),

and f(x) is very complicated.

We need the 200th coefficient...

Any thoughts?

> >More specifically, we figured that it's impossible to do this via
> >finite difference, i.e. do everything completely in the numerical
> >domain, because the noise will be huge and error will dominate.
>
> correct. maybe you use 1000 digits precision??
>
>

Thanks Peter. But we had bad impression about forward difference, so
not sure if 1000 digits precision will save it?


>
> no no. AD is very good for the first derivative, has already problems wit=
h hessians,
> but for higher order I never saw it. (the computational graph of a comp g=
raph of
> a comp graph ... )


Maybe we keep doing the first derivative for 200 times? Supposedly it
has no error?

>
>
>
>
> =A0maybe your teacher wanted to shock you somehow ,
> =A0but there are some chances you didn't consider:
>
> =A0if it is a rational function , perform the decomposition into partial
> =A0fractions, then the formal derivative is obvious, and possibly combine
> =A0back.
>
> =A0nice exercise :
>
> =A0the 200-th derivative of arctan(x)
>
> =A0if it is a function with known or easy power series expansion,
> =A0differentiate this one
>
> =A0the same for a fourier expansion: attention: think about the convergen=
ce
> =A0criteria
>
> =A0what is that good for?
> =A0maybe you must evaluate the remainder term of a 100-node gauss-quadrat=
ure??
> =A0(bad joke)
>

Yeah, Peter. As you can see from other posts, we are trying to get the
200th coefficient of the Taylor expansion of a generating function.

Any more thoughts?

On Mar 18, 12:13=A0pm, Robert Israel
<isr...@math.MyUniversitysInitials.ca> wrote:
> excellentf...@gmail.com writes:
> > Hi all,
>
> > We need to take the 200th order derivative of a complicated formula,
> > and then evaluate it numerically.
>
> > What's the best way to handle this?
>
> > More specifically, we figured that it's impossible to do this via
> > finite difference, i.e. do everything completely in the numerical
> > domain, because the noise will be huge and error will dominate.
>
> > So a plan was to first obtain the 200th order derivative thru symbolic
> > calculation in Maple, Matlab, Mathematica, and then copy the huge
> > result and somehow make it into a form that is numerically evaluable
> > either in Matlab or C++. Then evaluate that huge expression
> > numerically. Still, that sounds daunting, the symbolic result of 200th
> > order derivative will be huge and we are not sure if Maple or
> > Mathematica can handle it.
>
> > Another possibility is to do some sort of Automatic Differentiation.
> > But we are new to AD. Is it possible that with the help from an AD
> > package, we just need to give inputs of the parameter values, and the
> > package will crank out the numerical result of the 200th order
> > derivative with almost no error?
>
> > We see that lots of free packages are in C/C++ or Fortune, which are
> > not convenient for fast prototyping(we are at evaluating stage, if
> > this idea doesn't work, we don't want to spend too much time on it).
> > So are there free AD packages that can go with Matlab or Mathematica
> > or Maple that can take 200th order differentiation and are convenient
> > for prototyping? Which one is the best AD package that we could try
> > on? If it doesn't work, then we would discard this crazy idea of
> > taking 200th order derivative completely.
>
> > Please shed some lights on us!
>
> > Thanks a lot!
>
> Perhaps what you might try is computing a Taylor series up to order x^200=
. =A0
> There still might be some numerical difficulties, but it might not be so =
bad.
> =A0For example, in Maple:
>
> =A0 f:=3D x^3*sin(x)/(x - cos(x));
> =A0 Digits:=3D 20;
> =A0 200! * coeff( series(f, x=3D0.3, 201), x-0.3, 200);
>
> =A0 =A0 -.90246797086526191165e446
> --
> Robert Israel =A0 =A0 =A0 =A0 =A0 =A0 =A0isr...@math.MyUniversitysInitial=
s.ca
> Department of Mathematics =A0 =A0 =A0 =A0http://www.math.ubc.ca/~israel
> University of British Columbia =A0 =A0 =A0 =A0 =A0 =A0Vancouver, BC, Cana=
da

Thanks Robert.

Our analytical expression is very complicated, with subcomponents that
are specified by other dynamic systems.

Not sure how we can wrap the whole thing up in Maple as a function?

On Mar 18, 5:01=A0pm, hru...@odds.stat.purdue.edu (Herman Rubin) wrote:
> In article <gpr9nj$rk...@fred.mathworks.com>,
>
> Steven Lord <sl...@mathworks.com> wrote:
> ><excellentf...@gmail.com> wrote in message
> >news:f6ebcf2b-4782-4984-aebc-7cdb5b28ccee@p2g2000prf.googlegroups.com...
> >> Hi all,
> >> We need to take the 200th order derivative of a complicated formula,
> >> and then evaluate it numerically.
> >My first question: =A0why? =A0I can see why you might want to take the 1=
st
> >derivative, or the 2nd derivative, or maybe even the 3rd or 4th derivati=
ve
> >of a function. =A0The 200th? =A0How are you planning to use the value yo=
u
> >receive from this procedure?
>
> I can see a possible reason, although done should try
> to find another way. =A0If a Laplace transform, or a
> bilateral Laplace transform, can be computed by some
> procedure, but the computation cannot be extended in
> the complex plane, the function can be approximated by
> using high-order derivatives, and 200 might even be
> considered low for this problem.
>
> --
> This address is for information only. =A0I do not claim that these views
> are those of the Statistics Department or of Purdue University.
> Herman Rubin, Department of Statistics, Purdue University
> hru...@stat.purdue.edu =A0 =A0 =A0 =A0 Phone: (765)494-6054 =A0 FAX: (765=
)494-0558

Thanks Herman.

Yeah we are looking for the 200th coefficient in the generating
function...

Any more thoughts?

On 19 mar, 15:44, excellentf...@gmail.com wrote:
> On Mar 18, 5:01=A0pm, hru...@odds.stat.purdue.edu (Herman Rubin) wrote:
>
>
>
>
>
> > In article <gpr9nj$rk...@fred.mathworks.com>,
>
> > Steven Lord <sl...@mathworks.com> wrote:
> > ><excellentf...@gmail.com> wrote in message
> > >news:f6ebcf2b-4782-4984-aebc-7cdb5b28ccee@p2g2000prf.googlegroups.com.=
..
> > >> Hi all,
> > >> We need to take the 200th order derivative of a complicated formula,
> > >> and then evaluate it numerically.
> > >My first question: =A0why? =A0I can see why you might want to take the=
 1st
> > >derivative, or the 2nd derivative, or maybe even the 3rd or 4th deriva=
tive
> > >of a function. =A0The 200th? =A0How are you planning to use the value =
you
> > >receive from this procedure?
>
> > I can see a possible reason, although done should try
> > to find another way. =A0If a Laplace transform, or a
> > bilateral Laplace transform, can be computed by some
> > procedure, but the computation cannot be extended in
> > the complex plane, the function can be approximated by
> > using high-order derivatives, and 200 might even be
> > considered low for this problem.
>
> > --
> > This address is for information only. =A0I do not claim that these view=
s
> > are those of the Statistics Department or of Purdue University.
> > Herman Rubin, Department of Statistics, Purdue University
> > hru...@stat.purdue.edu =A0 =A0 =A0 =A0 Phone: (765)494-6054 =A0 FAX: (7=
65)494-0558
>
> Thanks Herman.
>
> Yeah we are looking for the 200th coefficient in the generating
> function...
>
> Any more thoughts?- Masquer le texte des messages pr=E9c=E9dents -
>
> - Afficher le texte des messages pr=E9c=E9dents -

Bonjour,

That reminds me about Dirichelet functions , chiefly
functions well approximated by sums of exponentials.

Of course if f(x) smooth all needed, very well approximated
by sum(a[i]*exp( b[i]*x ) then (d/dx)^j o f(x) is directly
obtained,

Alain

On 2009-03-19 11:43:38 -0300, excellentfeng@gmail.com said:

> On Mar 18, 12:13

On Mar 19, 7:27=A0am, excellentf...@gmail.com wrote:
> On Mar 18, 11:12=A0am, pnachtwey <pnacht...@gmail.com> wrote:
>
>
>
> > On Mar 18, 9:42=A0am, excellentf...@gmail.com wrote:
>
> > > Hi all,
>
> > > We need to take the 200th order derivative of a complicated formula,
> > > and then evaluate it numerically.
>
> > > What's the best way to handle this?
>
> > > More specifically, we figured that it's impossible to do this via
> > > finite difference, i.e. do everything completely in the numerical
> > > domain, because the noise will be huge and error will dominate.
>
> > > So a plan was to first obtain the 200th order derivative thru symboli=
c
> > > calculation in Maple, Matlab, Mathematica, and then copy the huge
> > > result and somehow make it into a form that is numerically evaluable
> > > either in Matlab or C++. Then evaluate that huge expression
> > > numerically. Still, that sounds daunting, the symbolic result of 200t=
h
> > > order derivative will be huge and we are not sure if Maple or
> > > Mathematica can handle it.
>
> > > Another possibility is to do some sort of Automatic Differentiation.
> > > But we are new to AD. Is it possible that with the help from an AD
> > > package, we just need to give inputs of the parameter values, and the
> > > package will crank out the numerical result of the 200th order
> > > derivative with almost no error?
>
> > > We see that lots of free packages are in C/C++ or Fortune, which are
> > > not convenient for fast prototyping(we are at evaluating stage, if
> > > this idea doesn't work, we don't want to spend too much time on it).
> > > So are there free AD packages that can go with Matlab or Mathematica
> > > or Maple that can take 200th order differentiation and are convenient
> > > for prototyping? Which one is the best AD package that we could try
> > > on? If it doesn't work, then we would discard this crazy idea of
> > > taking 200th order derivative completely.
>
> > > Please shed some lights on us!
>
> > > Thanks a lot!
>
> > How did you even get the coefficients for a 200th order polynomial?
>
> > I agree with the others that say this is non sense. Any number, that
> > is not extreme close to 1 taken to the 200 power, will either cause a
> > numeric overflow or be rounded down to 0 unless you have a very high
> > precision calculator.
>
> > However, if the equation is a 200th order polynomial then one can
> > compute the coefficients for any of the derivative functions easily
> > enough in C or Fortran. =A0Then the equation can be evaluated using
> > Horner's method. =A0No matlab, mathematica or maple required. =A0I have
> > done this before with 5 to 7th order polynomials. It would be easy
> > enough to expand the arrays to do this with 200th order polynomials.
>
> > Peter Nachtwey
>
> Hi Peter,
>
> Yes, essentially we are finding the 200th coefficient of the Taylor
> expansion of a very complicated analytical expression.
>
> Let's say it's given by f(x),
>
> and f(x) is very complicated.
>
> We need the 200th coefficient...
>
> Any thoughts?
Only the obvious which is what we did. Suppose you make a 200 x 200
array for you polynomial and put the coefficients in the first row or
column like this

Y(x)=3Dc0+c1*x+c2*x^2 ..
each column is reduced by one order.

x x' x" x'''

c0 1*c1 1*2*c2 1*2*3*c3
c1 2*c2 2*3*c3 2*3*4*c4
c2 3*c3 3*4*c4 3*4*5*c5
c3 4*c4 4*5*c5 4*5*6*c6
c4 5*c5 5*6*c6 5*6*7*c7
c5 6*c6 6*7*c7 6*7*8*c8

Hopefully the row will not get messed up so bad you can't see what I
am doing.
Do you see the pattern?
Is it time for a duh moment? This is shear brute force.
This can be done in two for loops easily.
By the time you get to the 199 column you will have just a constant.
Of course you could just assume all the coefficients, c0..cn, are 1
and work out the multipliers only once head of time. We do this in
real time systems but with lower order. Then we use Horner's method
to evaluate the array at any x for any derivative. We hard code all
of this.
y(x) =3D ((...+c3*x+c2)*x+c1)*x+c0
One can easily make a general function out of this where one specifies
x and the derivative. Put this data in an array where the column is
the derivative number and the rows are the powers of x. A good
optimizing C compiler makes light work out of this at run time. You
may wish to try switching rows and columns to see which optimization
is best.

Peter Nachtwey

In article <190320090430067217%delaneyrm@earthlink.net>,
Bob Delaney <delaneyrm@earthlink.net> wrote:
>In article <gprf24$76p$1@news.math.niu.edu>, Dave Rusin
><rusin@vesuvius.math.niu.edu> wrote:
>
>> 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).

>Intriguing. Care to elaborate?

This a_k is divisible by every (k+1)-bit prime (and no larger prime, and
few smaller primes), so we successively compute gcd(N, a_k) (k=1,2,...)
until we get something nontrivial. That will give a factor of N ; done!

(Almost. It's a _nontrivial_ factor of N unless every prime divisor of N
is of exactly the same length in bits; in that case we can play a similar
game with the other Taylor coefficients that I mentioned, bisecting the
intervals where the primes are known to lie until an interval is small
enough to contain some but not all the prime divisors. So it might take
2000 gcd computations instead of 1000 to find a proper factor. Big deal.
But the main issue that we have to have a fast way to compute central
binomial coefficients mod N, with the a_k 's being the main example.)

Well, you tell me: if N = 2^987 + 21, what's a_300 mod N ?
(This N is a 298-digit composite number, so your answer fits in a few lines.)

Unlike the OP's problem, in my case these coefficients a_k are "known" exactly.
If I had a lot of numbers to factor, I could even pre-compute them once and
then just reduce mod N each time I want to use them in this way. But from
Stirling's approximation, we estimate a_k is about 4^(2^k)/(2^(k/2))
which is to say not thousands of bits but say 2^1000 bits! So it is critical
for this program that we find a way to compute a_k mod N without finding
a_k itself first. Note that the slightly larger number 4^(2^k) can be
computed mod N with k successive squarings, so it's not magnitude alone
that makes the job difficult.

What's weird is that in principle I HAVE all these numbers a_k mod N :
using Newton's method to compute 1/sqrt(1-4t) as a solution to
1/X^2 - (1-4t) = 0, we compute polynomials p_k with
   p_0 = 1
   p_{k+1} = (1/2) * p_k * (3 - (p_k)^2*(1-4*t) ) mod N
and then the first 2^k coefficients of p_k agree with those of the
taylor series of 1/sqrt(1-4t) , and in particular a_k is just the
coefficient of x^(2^k) in p_{k+1} . Check it out with your favorite CAS!
(You can even choose to truncate each p_k after t^(2^k) .) It takes only
O(k) ring operations in the ring (Z/NZ)[t] -- polynomial time factorization!

BUT I don't know a way to pick out one coefficient of one of these
polynomials without multiplying out everything term by term, and of
course I can't do that with 2^1000 terms. The number of ring operations
in Z/NZ itself is exponential in k so it's not really polynomial time.
(I guess the terminology here is that these are "SLP" polynomials --
"Straight Line Program" or something -- meaning that their _values_
can be computed very easily; the question then becomes whether the one
coefficient can be recovered with the same kind of speed with which
values are computed. I don't know a way to do this.)

Anyway, fast integer factorization is a hot topic, and as you can see
I can reduce it to the question of computing a high-order derivative
of an easily-computed function, so this is why I followed this thread
with interest!

dave

On Mar 18, 1:01=A0pm, dpb <n...@non.net> wrote:
> Robert Israelwrote:
>
> ...
>
> > Perhaps what you might try is computing a Taylor series up to order x^2=
00. =A0
> > There still might be some numerical difficulties, ... [snip for effect]
>
> Think??? =A0:)
>
> > =A0For example, in Maple:
>
> > =A0 f:=3D x^3*sin(x)/(x - cos(x));
> > =A0 Digits:=3D 20;
> > =A0 200! * coeff( series(f, x=3D0.3, 201), x-0.3, 200);
>
> > =A0 =A0 -.90246797086526191165e446
>
> Hmmmm....any idea how many of those digits are actually meaningful in
> front of that 10**446 exponent???
>
> --

Nearly all of them, actually.
I should have put on my complex analyst's hat, and realized that the
result would be very strongly dominated by the contribution from the
closest pole p of f, which is at the zero of the denominator near
0.73908513321516064165. The residue of f at p being r =3D p^3*sin(p)/
(1+sin(p)) =3D 0.16249441728752941464, the contribution of this pole to
f^(200)(0.3) is r*(-1)^200*200!/(0.3-p)^201 =3D -.
90246797086526190972*e446.

--
Robert Israel israel@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

Dave Rusin wrote:
...
> I think the Mathematica code should be something like
> q = 200! *Coefficient[Series[f[x], {x, N[a,2000], 201}], (x-N[a,2000])^200 ]
> which returns
> -9.024679708652619116077333659727619804699158461886[...]*10^445
> in agreement with Maple.

Color me surprised...obviously my little experience w/ either is showing.

--

<excellentfeng@gmail.com> wrote in message
news:4a295f65-2621-43dc-874f-bc14d414805f@d2g2000pra.googlegroups.com...


"Yeah, I am sure after long time running, Mathematica will return a
huge result, but then how do I plugin numerical parameter values to
get numerical results? We can judge from the end numerical results
whether it is good or bad idea to go this route..."

In Mathematica, you plug in numerical values into an expression by using
ReplalceAll command

http://reference.wolfram.com/mathematica/ref/ReplaceAll.html

--Nasser

excellentfeng@gmail.com wrote:

>> no no. AD is very good for the first derivative, has already problems with hessians,
>> but for higher order I never saw it. (the computational graph of a comp graph of
>> a comp graph ... )
>
>
> Maybe we keep doing the first derivative for 200 times? Supposedly it
> has no error?

 There is no numerical computation that has (in general) no error.
Besides, you can't simply repeat AD for higher derivatives, since it
does not emit a formula.

 But I don't see why higher derivatives should be a problem in the
univariate (one-dimensional) case. (Hessians are a different story, but
hey, that's multivariate.) Obviously, if your expression contains
individual functions for which the 200th derivative is hard to compute,
that won't help either. But if you are only using rational expressions,
trig functions, exponentials etc., it may work.

> Yeah, Peter. As you can see from other posts, we are trying to get the
> 200th coefficient of the Taylor expansion of a generating function.

 Sounds like a bad idea to me anyway. Maybe there is some kind of
recursion relation between the coefficients that could be employed?


Christopher