Re: Can it be done - easily?
- To: mathgroup at smc.vnet.net
- Subject: [mg13258] Re: Can it be done - easily?
- From: Paul Abbott <paul at physics.uwa.edu.au>
- Date: Fri, 17 Jul 1998 03:17:51 -0400
- Organization: University of Western Australia
- References: <6od25q$hn9@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Barry Culhane wrote:
> Myself and two workmates are software developers. One guy wanted a
> formula to calculate a result for the following equation...
> Z = sum of X/Y where X is a fixed number, and Y ranges from A-B in
> fixed steps...
> i.e... X=10000 ; Y=100,200,300...1000
> i.e... Z= 10000/100 + 10000/200 + ... 10000/1000 = 292.896
>
> He and I tried to figure out a simple formula to calculate it, but
> couldn't. The third guy said it was *not* *possible* to derive a
> formula - we think he's wrong, but can't prove it.
He's wrong -- sort of. There is a formula, but it is not that simple:
In[1]:= f[x_,a_,b_,d_] = x Sum[1/(a + i*d), {i, 0, (b-a)/d}]
Out[1]=
b a
x (PolyGamma[0, 1 + -] - PolyGamma[0, -])
d d
-----------------------------------------
d
For your parameter values, x=10000, a=100, b=1000, d=100, the exact sum
is
In[2]:= f[10000,100,1000,100]
Out[2]=
36905
-----
126
with numerical value,
In[3]:= N[%]
Out[3]= 292.897
> MathCad can solve
> it in the blink of an eye, even if the value of Y ranges from 1 to 1e6
> in steps of 1 !!!
But Mathematica can give you the exact formula for any X and Y! Also,
using NSum (numerical summation) instead of Sum, we find
In[4]:= Nf[x_,a_,b_,d_] := x NSum[1/(a + i*d), {i, 0, (b-a)/d}]
In[5]:= Nf[x,1,10^6,1]//Timing
Out[5]= {0.14 Second,14.3927 x}
which is the correct result for any value of x.
> Can anyone come up with a simple formula to give a reasonably accurate
> result? It is too slow to actually divide X by Y for each value of Y
> as there may be 1000 or even 100,000 values of Y.
Obviously, X is a constant that can should be factored out of the
computation (as is done above). For appropriate parameter ranges, NSum
uses the Euler-Maclaurin formula which greatly speeds up the
computation.
There is a simple asymptotic formula which you can use: For large n, the
harmonic series
Sum[1/i, {i, 1, n}]
is well approximated by
1 1 1 1 1 5
(EulerGamma - Log[-]) + --- - ----- + ------ + O[-]
n 2 n 2 4 n
12 n 120 n
where EulerGamma is 0.577215664901532860606512090... Inserting n = 10^6
into this truncated asymptotic series, one gets 14.3927 which agrees
with the above computation using NSum.
Cheers,
Paul
____________________________________________________________________
Paul Abbott Phone: +61-8-9380-2734
Department of Physics Fax: +61-8-9380-1014
The University of Western Australia Nedlands WA 6907
mailto:paul at physics.uwa.edu.au AUSTRALIA
http://www.pd.uwa.edu.au/~paul
God IS a weakly left-handed dice player
____________________________________________________________________