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$
3
  • $\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$ Nov 29, 2018 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, 2018 at 23:22
  • $\begingroup$ Okay. I edited my post. Please have a look. $\endgroup$ Nov 30, 2018 at 8:07

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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