# Fast way to compute a truncated series using Fold

I'm looking at an efficient and fast way to compute the results of a finite summation

$$\sum_{i=0}^Mf_ig_i\,.$$

I noticed that simply applying

Expand/@Sum[f[i]Expand/@g[i],{i,0,M}]


is not very efficient time-wise. The function f is generated recursively for any integer argument. I already use memoization when computing the functions recursively. They look like this

g[0] = 1;
g[n_] := g[n] = Expand@Sum[2^s, {s, 0, n - 1}];


Where do you think is the most consuming part?

f[0] = 1;
f[1] = Sum[Gamma[n] \[Alpha]^n, {n, 1, M}] + O[\[Alpha]]^(M + 1);
f[n_] := f[n] = (f[n - 1] + O[\[Alpha]]^M) (f[1] + O[\[Alpha]]^M)

• The evaluation of the functions f and g? Is there a way to save the value is an efficient way? A noticed that writing the values into a list (creating "fList" and "gList") using Table is also very timeconsuming.
• Using the function Sum? Would using Fold and pure functions be more efficient? (I tried but I didn't manage to write this sum using pure functions into the Fold function....)
• Regarding the first point, do you know about memoization? If your functions are recursive, this is likely to help greatly. – jjc385 Jun 14 '17 at 9:45
• @jjc385 Oupsy, I forgot to mention that I already used memoization in the recursive computation. Thanks for noticing, I will edit the question. – Anne O'Nyme Jun 14 '17 at 9:47
• Could you provide a minimal working example? It's hard (for me, at least) to say much without one. – jjc385 Jun 14 '17 at 10:06
• @jjc385 I made it more detailed? Does it seem to be more clear now? – Anne O'Nyme Jun 14 '17 at 10:14
• I think problem might be in definition of f[1]. If you define it before defining numerical value of M, then Mathematica will evaluate Sum from RHS of f[1] definition to a general DifferenceRoot expression, which will be evaluated in each non-memoized call to f function, making them terribly slow. If you define f[1] after defining M, then f[1] will be ordinary SeriesData expression and evaluation will be much faster. It would be best to avoid global variable in function definition and use m as second argument of f. – jkuczm Jun 14 '17 at 14:26

## 1 Answer

The definition of f[1] uses Set instead of SetDelayed, which means that f[1] evaluates using whatever the current value of M is. If M is not defined, you will get a DifferenceRoot object:

Clear[M]
f[1] = Sum[Gamma[n] α^n, {n, 1, M}] + O[α]^(M + 1)

(*
α^(1 + M) SeriesData[α, 0, {}, 0, 0, 1] +
DifferenceRoot[
Function[{\[FormalY], \[FormalN]}, {\[FormalN] α \[FormalY][\
\[FormalN]] + (-1 - \[FormalN] α) \[FormalY][
1 + \[FormalN]] + \[FormalY][2 + \[FormalN]] == 0, \[FormalY][1] ==
0, \[FormalY][2] == α}]][1 + M]
*)


Having f[1] defined as a DifferenceRoot object will slow things down.

Now, if you want to evaluate the sum for different values of M, you will want to clear the memoized values. I think the easiest way to do this is to use the InternalInheritedBlock the function, so that all memoized values are automatically erased when the Block finishes. You will also want to Block M to the desired value first. First, here is your definition of g and a revised definition of f:

g[0] = 1;
g[n_] := g[n] = Expand@Sum[2^s,{s,0,n-1}];

f[0] = 1;
f[1] := Sum[Gamma[n] α^n, {n,1,M}] + O[α]^(M+1);
f[n_] := f[n] = (f[n-1]+O[α]^M) (f[1]+O[α]^M)


Then, your desired computation:

res[m_] := InternalInheritedBlock[{M = m, f, g},
Sum[g[i] f[i], {i, M}]
]


Test:

res[5] //TeXForm


$\alpha +4 \alpha ^2+15 \alpha ^3+57 \alpha ^4+226 \alpha ^5+O\left(\alpha ^6\right)$

res[100]; //AbsoluteTiming


{0.025141, Null}