## Re: calculating harmonic numbers

Expand Messages
• Hello, Here are results from an athlon 2k In[39]:= Table[Timing[N[HarmonicNumber[10^k],10]],{k,0,7}] Out[39]= {{0. Second,1.000000000},{0.
Message 1 of 2 , Feb 18, 2005
Hello,

Here are results from an athlon 2k

In[39]:=
Table[Timing[N[HarmonicNumber[10^k],10]],{k,0,7}]
Out[39]=
{{0. Second,1.000000000},{0. Second,2.928968254},{0. Second,
5.187377518},{0. Second,7.485470861},{0.01 Second,
9.787606036},{1.522 Second,12.09014613},{48.71 Second,
14.39272672},{1059.24 Second,16.69531137}}
In[40]:=
Table[Timing[N[HarmonicNumber[10^k],10]],{k,10,10}]
Out[40]=
{{0. Second,23.60306659}}

OK, so it's multiples of 10

In[46]:=
Table[Timing[N[HarmonicNumber[10^k],10]],{k,20,100,10}]
Out[46]=
{{0. Second,46.62891752},{0. Second,69.65476845},{0. Second,
92.68061938},{0. Second,115.7064703},{0. Second,138.7323212},{0.
Second,
161.7581722},{0. Second,184.7840231},{0. Second,207.8098740},{0.
Second,
230.8357250}}

Doesn't seem to be slowing down

In[47]:=
Table[Timing[N[HarmonicNumber[10^k],10]],{k,120,1120,100}]
Out[47]=
{{0. Second,276.8874268},{0. Second,507.1459361},{0. Second,
737.4044454},{0. Second,967.6629547},{0. Second,1197.921464},{0.
Second,
1428.179973},{0. Second,1658.438483},{0. Second,1888.696992},{0.
Second,
2118.955501},{0. Second,2349.214011},{0. Second,2579.472520}}

Anyone know what Mathematica is actually doing here?

Thanks again,

-Dick Boland

P.S. - I just heard from someone off list that this likely an
approximation technique using the psi function. I'd be interested in
any known bounds on the accuracy.

>
> Hello,
>
> Mathematica's built in HarmonicNumber[n] gets predictably slower as
n
> increases, but when n=10^10, the answer is returned quickly. Does
> anyone know if this is due to an algorithmic advantage specifically
> for n=10^10 and if so, what's the algorithm and what other n values
> allow for faster calculation?
>
> Thanks,
>
> Dick Boland
Your message has been successfully submitted and would be delivered to recipients shortly.