1

I am in a course of numerical methods and I have a question:

If I have the harmonic sum:

$\sum_{i=1}^{n}\dfrac{1}{i}$ and I can approximate it by "rounding" it. This rounding can be defined as:

$S_n = fl(S_{n-1} +a_n)$ where the $a_n$ are the harmonic terms. My question is if there is way to know when the sum $S_n$ will stop growing and be constant, for $n$ big enough. I mean, given a certain presition $m$ of digits to approximate, how can I know the $n$ that will "stop" the sum.

wythagoras
  • 25,026
Adolf
  • 11
  • @JackD'Aurizio: You are correct in the reals. In computer floating point there is such a number. – Ross Millikan Sep 05 '15 at 14:34
  • @RossMillikan: ok, I probably misunderstood the question. So the point is to provide asymptotics for $H_n$? – Jack D'Aurizio Sep 05 '15 at 14:37
  • @JackD'Aurizio: just to find the $n$ so that $\frac 1n$ is so small compared to $H_n$ that it does not change the sum in floating point. Floating point has a resolution based on the number of bits assigned to the mantissa. For my old 32 bit single precision machines it was about $2^{-23}$, so if $\frac 1n \lt 2^{-23} \log n$ it will not change the sum, – Ross Millikan Sep 05 '15 at 14:59

2 Answers2

1

Your sum is $H_n$,the $n^{\rm {th}}$ harmonic number. We have $H_n \approx \log n + \gamma$, where $\gamma \approx 0.577$ You are being asked to estimate the $n$ where $\frac 1n \lt H_n \epsilon$, where $\epsilon$ is the smallest number that can be added to $1$ which gives a different result.

Ross Millikan
  • 374,822
  • So asymptotically the question is about when $n \log(n) > \frac{1}{\epsilon}$. To leading order this occurs when $n>-\frac{1}{\epsilon \log(\epsilon)}$. In double precision this will be somewhere between $n=10^{14}$ and $n=10^{15}$. – Ian Sep 05 '15 at 14:44
0

If you need to solve $$n \log(n) =\frac{1}{\epsilon}$$ the solution is given in terms of Lambert function $$n=\frac{\frac 1\epsilon}{ W\left(\frac{1}{\epsilon }\right)}$$ which can be approximated by $$n\sim\frac{\frac 1\epsilon}{\log\left(\frac 1\epsilon \right)-\log \left(\log \left(\frac{1}{\epsilon }\right)\right)}$$

For $\epsilon=2^{-23}$, the approximation would give $n=636784$ while the exact solution would be $n=628322$.

Claude Leibovici
  • 260,315