# How to speed up recursive compiled functions?

I'm trying to speed up the recursive function that calculates Rotation numbers:

ClearAll[θ]
θ[n_, Ω_, k_] := θ[n, Ω, k] = θ[n - 1, Ω, k] + Ω -
k/(2 π) Sin[2 π θ[n - 1, Ω, k]]
θ[0, Ω_, k_] := 0


Notice that I'm using memoization. Here's the timing of the uncompiled function:

AbsoluteTiming[Table[θ[n, .2, 1]/n, {n, 1, 1000}];]

{0.016223, Null}


Now I tried compiling the recursive function:

ClearAll[compθ]
compθ =
Compile[{{n, _Integer}, {Ω, _Real}, {k, _Real}},
If[n == 0, 0,
compθ[n - 1, Ω, k] + Ω - k/(2 π)Sin[2 π compθ[n - 1, Ω, k]]],
{{compθ[_, _, _], _Real}},
CompilationOptions -> {"InlineCompiledFunctions" -> True,
"ExpressionOptimization" -> True}, RuntimeOptions -> {"Speed"}]


The timing of the compiled function is worse:

AbsoluteTiming[Table[compθ[n, .2, 1]/n, {n, 1, 1000}];]

{0.342844, Null}


Of course the timing could be improved if I could somehow use memoization with the compiled function, but I couldn't find any example that shows how to do it. Is it possible? I also noticed with CompilePrint that the compiled function calls MainEvaluate, which is probably slowing the computation, but this comment suggests that this may be unavoidable. Is this true?

If you're looking for a faster way to calculate rotation numbers rather than optimizing your original function using memorization, try this:

AbsoluteTiming[ans1 = Table[θ[n, .2, 1]/n, {n, 1, 100000}];]

θ2 = Compile[{n, Ω, k}, Rest@NestList[# + Ω - k/(2 π) Sin[2 π #] &, 0, n]/Range@n];
ans2 = θ2[100000, 0.2, 1]; // AbsoluteTiming

And @@ (ans2 - ans1 // Chop // PossibleZeroQ)

{0.414000, Null}
{0.043000, Null}
True


Notice that different computing method has caused slightly different result but I think it doesn't hurt.

As to your original method, AFAIK, there's no way to compile the structure f[n_] := f[n] = …. The only thing I can think of to optimize it is to compile the compilable part only:

f = Compile[{p, Ω, k}, p + Ω - k/(2 π) Sin[2 π p]];
θ3[n_, Ω_, k_] := θ3[n, Ω, k] = f[θ3[n - 1, Ω, k], Ω, k]
θ3[0, Ω_, k_] := 0


but this only speeds up the calculation for a specific set of parameters only once.

Faster to use cycle in compiled functions

compθ2=Compile[{{n,_Integer},{Ω,_Real},{k,_Real}},
Module[{i=0,next=0.},
For[i=1,i<=n,i++,
next=next+Ω-k/(2*Pi)*Sin[2*Pi*next];
];
next
],
CompilationOptions->{"InlineCompiledFunctions"->True,"ExpressionOptimization"->True},RuntimeOptions->{"Speed"}]


But its not faster than using memorization

AbsoluteTiming[Table[compθ2[n, .2, 1]/n, {n, 1, 1000}];]
(*{0.075004,Null}*)
AbsoluteTiming[Table[θ[n,.2,1]/n,{n,1,1000}];]
(*{0.027002,Null}*)

• Interesting, on your computer the compiled code is about 2.8x slower than the uncompiled code, on my machine it's 7.6x slower. – shrx Jul 18 '14 at 12:19