2
$\begingroup$

I have looked up some articles about the compiling recursive functions. I know usually there is no general solution to these kinds of questions. And my case is a little bit different (or more complicated) so I decide to simplify it and ask here:

The original recursive function in my case has been simplified as below:

Clear[f]
x = 0.1; f[0] = 1.; f[1] = 2.;
f[n_] := f[n] = 20*x*f[n - 1] + n*f[n - 2];

And my desired output result was calculated by:

Table[f[n] 2 n x, {n, 0, 10}]
(* Output: {0., 0.4, 2.4, 10.8, 48., 210., 936., 4242., 19680., 93366., 453480.} *)

To transform it into a compiled version, what I did is that I first wrote a compiled fc function as shown below: (Note: it's not the best way to use Do but that's all I can think of ):

fc = Compile[{{x, _Real}}, Module[{t}, t = {1., 2};
   t = Join[t, Table[0., {10}]];
   Do[t[[n + 2]] = (20*x*t[[n + 1]] + (n + 1)*t[[n]]), {n, 10}]; Most@t]
  ]

It works okay for using fc as a compiled replacement by f:

Table[f[n], {n, 0, 10}]
(*{1, 2, 6., 18., 60., 210., 780., 3030., 12300., 51870., 226740.}*)

fc[0.1] 
(*{1., 2., 6., 18., 60., 210., 780., 3030., 12300., 51870.,226740.}*)

However, my questions are:

1- I don't know how to take the 2*n*x part into the final computation to get my desired result.

2- fc only works fine when x is one-dimensional value. But my project requires larger data-set to handle with and that's why I am trying to use Compile. So how to adjust it to work on a real number list, for example, when x = {0.1,0.2,0.3...}?

$\endgroup$
  • $\begingroup$ What do you mean by " I don't know how to take the 2*n*x part into the final computation to get my desired result." What is your desired result? $\endgroup$ – Henrik Schumacher Nov 29 '18 at 21:59
  • $\begingroup$ My final computation would include 2*n*x, so in the uncompiled version, it was calculated by Table[f[n] 2*n*x, {n, 0, 10}], I do not know how to transform this. $\endgroup$ – leon365 Nov 29 '18 at 23:22
  • $\begingroup$ Okay. I edited my post. Please have a look. $\endgroup$ – Henrik Schumacher Nov 30 '18 at 8:07
3
$\begingroup$

So how to adjust it to work on a real number list, for example, when x = {0.1,0.2,0.3...}?

If x is a list of reals, then just compile fc with the addictional option RuntimeAttributes-> {Listable} and call fc[x]. Parallelization -> True will also enable parallelization (does only work if RuntimeAttributes-> {Listable} is also set).

fc2 = Compile[{{x, _Real}, {iter, _Integer}},
   Module[{t},
    t = {1., 2.};
    t = Join[t, Table[0., {iter}]];
    Do[
     t[[n + 2]] = (20. x t[[n + 1]] + (n + 1) t[[n]]),
     {n, iter}
     ];
    Most[t] Range[0, iter] (2. x)
    ],
   CompilationTarget -> "C",
   RuntimeAttributes -> {Listable},
   Parallelization -> True,
   RuntimeOptions -> "Speed"
   ];

A quick test (also with the vectorized version of your old memoization approach):

x = Subdivide[0., 10., 1000000];
ClearAll[f];
f[0] = 1. + 0. x; f[1] = 2. + 0. x;
f[n_] := f[n] = 20. x f[n - 1] + n f[n - 2];
aa = Transpose[Table[f[n] 2 n x, {n, 0, 50}]]; // AbsoluteTiming // First
bb = fc2[x, 50]; // AbsoluteTiming // First
aa == bb

1.59957

0.352834

True

$\endgroup$

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.