Extreme Slowdown with Fold

Question

I am doing a finite difference model, and need to create a list recursively. For a small list, Fold is extremely fast, but when the list becomes large enough, Fold becomes extremely slow. Here is the code:

step[x_] := If[Mod[x, 1] <= .2, -100., 0.]
min=-10;
max=10;
dx = .01;
num = IntegerPart[(max - min)/dx];

potentialEnergy=Array[step,num,{min,max-dx}];
epotential=(2-dx^2*(-45-potentialEnergy[[2;;-2]]));

Fold[Join[#1, {Times[#2, #1[[-1]]] - #1[[-2]]}] &, {0, .01}, epotential];

When I run the above code for differing dx, I obtain the following run times: \begin{array}{c|c} dx & \text{AbsoluteTiming} \\ \hline \text{.1} & .0004 \\ \hline \text{.01} & .003 \\ \hline \text{.001} & .479 \\ \hline \end{array} To put this in context with the following code

fillArray = Join[{0, .1}, ConstantArray[0., num - 2]];
ePotential = (2 - dx^2*(-45 - potentialEnergy));

Do[fillArray[[j + 2]] = ePotential[[j + 1]]*fillArray[[j + 1]]
- fillArray[[j]], {j, 1, num - 2}]

I obtain this table of run times: \begin{array}{c|c} dx & \text{AbsoluteTiming} \\ \hline \text{.1} & .001 \\ \hline \text{.01} & .010 \\ \hline \text{.001} & .110 \\ \hline \end{array}

This second table of run times does not have the huge jump between dx=.01 and dx=.001 like the first table. Thus, my question is, why is there such a large jump and how can it be avoided?

Answer 1

On my PC, the code in the question executes in about 1.3 seconds for dx = .001, measured using AbsoluteTiming. Consider as an alternative,

Join[{0}, Cases[FoldList[{#1[[-1]], Times[#2, #1[[-1]]] - #1[[-2]]} &, 
    {0, .01}, epotential], {_, z_} -> z]];

which executes in about 0.07 seconds. Results are identical.

Addendum

Slightly faster is another alternative.

Join[{0}, FoldList[{#1[[-1]], Times[#2, #1[[-1]]] - #1[[-2]]} &, 
    {0, .01}, epotential] // Transpose // Last];