Speeding Up Recursive Evaluation

Question

I have a recursive function for which I need the values for n=1 through about n=100,000,000 (or more). The function looks as follows, with output of the form ({x,y},a), and f, g, and h some functions.

coordinates[n_]:=coordinates[n]={{coordinates[n-1][[1]][[1]] +f[n, coordinates[n-1][[2]]], coordinates[n-1][[1]][[2]]+g[n, coordinates[n-1][[2]]]}, coordinates[n-1][[2]]+h[n]}

I then compute:

Table[coordinates[n][[All,1]], {n, 100,000,000}.

I can get up to a few million with about 4 hours of calculation time, but 100,000,000 causes my computer to crash and restart, stating "kernel panic" (I am not very familiar with programming unfortunately). Any advice about how to make such a table more easily calculated would be much appreciated!

Answer 1

It looks like your recursion only depends on the previous value, but you are still trying to build up an awfully big table, which is possibly crushing your kernel. Use writing to the disk (hopefully an SSD) to capture the data. Simplified problem that hopefully captures the flow:

Simple recursion using memoization

fn[x_] := fn[x] = 1 + fn[x - 1];
fn[0] = 1;

Do it via memoization and capturing results in a table.

memBefore = MemoryInUse[];
res = Table[fn[i], {i, 10000}];
memAfter = MemoryInUse[];
memAfter - memBefore
(*  1813536 *)

Fast, but a memory hog for both the table and memoization.

Now don't memoize, and write each value to the hard drive that then creating a table. It slows the loop, but you'll not soak up any active memory.

memBefore = MemoryInUse[];
last = 1; Do[(current = 1 + last; current >>> "temp.csv"; last = current), {i, 10000}]
memAfter = MemoryInUse[];
memAfter - memBefore
(*  6264  *)