How to speed up recursive compiled functions?

Question

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?

Answer 1

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.

Answer 2

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}*)