0
$\begingroup$

Using

f[n_] := Sum[1/(Sqrt[k] + Sqrt[k + 1]), {k, 1, n}]

to analyze the well-know series...

I noticed a sudden performance drop (on my outdated PC hardware ) around n=14.

f[14] // FullSimplify

Is there away to overcome this? Memoization comes to mind.

What would be a method to monitor performance of such a function?

Not sure how to go ahead with this.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Is this a toy problem to ask about timing performance, since Mathematica can perform the sum analytically? Sum[1/(Sqrt[k] + Sqrt[k + 1]), {k, 1, n}] to give -1 + Sqrt[1 + n] Additionally, are you sure you're timing the summation itself and not FullSimplify? The timing results up to n=40 seem reasonable to me. $\endgroup$
    – George Varnavides
    Jan 17 at 15:08
  • $\begingroup$ With f[n_] := f[n] = Sum[1/(Sqrt[k] + Sqrt[k + 1]), {k, 1, n}]; f[40]; // RepeatedTiming I get 4 10^-7 sec what seems rather fast. $\endgroup$
    – Daniel Huber
    Jan 17 at 15:40
  • $\begingroup$ @GeorgeVarnavides is right: the slowness comes from FullSimplify, not from Sum. You can use RootReduce instead of FullSimplify: the former is more precisely targeted to the task. $\endgroup$
    – Roman
    Jan 17 at 16:02
  • $\begingroup$ Remove["Global`*"] then try Total[Table[1/(Sqrt[k] + Sqrt[k + 1]), {k, n}]] or do the Sum with Method->"Procedural" ignoring the FullSimplify - you will find that in both cases f[14] is initially very fast, but the second time you run it is much slower. Not sure why but possibly caused by some kind of caching in mathematica's automatic simplification. $\endgroup$
    – flinty
    Jan 17 at 16:05

1 Answer 1

Reset to default
3
$\begingroup$

Assuming this is a toy problem: a fast way would be to memoize and root-reduce at every step,

Clear[f];
f[0] = 0;
f[n_Integer?Positive] := f[n] =
  RootReduce[f[n - 1] + 1/(Sqrt[n] + Sqrt[n + 1])]

f[100] // AbsoluteTiming
(*    {0.514451, -1 + Sqrt[101]}    *)
Improve this answer
$\endgroup$
3
  • $\begingroup$ Generate a sequence seq = f /@ Range[6] then looking at its form use Sqrt[FindSequenceFunction[(seq + 1)^2, n]] - 1 Or, since you have the recursion, you can use RSolve, i.e., Clear[f]; f[n] /. RSolve[{f[n] == f[n - 1] + 1/(Sqrt[n] + Sqrt[n + 1]), f[0] == 0}, f[n], n][[1]] $\endgroup$
    – Bob Hanlon
    Jan 17 at 16:36
  • 1
    $\begingroup$ @BobHanlon of course; but I was assuming that this is a toy problem. $\endgroup$
    – Roman
    Jan 17 at 17:12
  • $\begingroup$ Most of my problems are ( thank G. ) "toy" problems. $\endgroup$
    – nilo de roock
    Jan 18 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.