alt Hacker News> For small n we can directly implement the definition. For large n, the direct approach would be slow and would accumulate floating point error.
is there a reason the direct definition would be slow, if we cache the prior harmonic number to calculate the next?
Replies
coherentpony • today at 3:30 PM
It’s a natural observation, but it doesn’t address the floating point problem. I think the author should have said “fast or would accumulate floating point error” instead of “fast and would accumulate floating point error”.
You could compute in the reverse direction, starting from 1/n instead of starting from 1, this would produce a stable floating point sum but this method is slow.
Edit: Of course, for very large n, 1/n becomes unrepresentable in floating point.
➕ show 1 reply
I think it's fair to say that summing the series directly would be slow, even if it's not slow when you already happen to have summed the previous n-1 terms.
Not least because for modestly-sized target sums the number of terms you need to sum is more than is actually feasible. For instance, if you're interested in approximating a sum of 100 then you need something on the order of exp(100) or about 10^43 terms. You can't just say "well, it's not slow to add up 10^43 numbers, because it's quick if you've already done the first 10^43-1 of them".