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

θ[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:

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?


2 Answers 2


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}

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


But its not faster than using memorization

AbsoluteTiming[Table[compθ2[n, .2, 1]/n, {n, 1, 1000}];]
  • $\begingroup$ Interesting, on your computer the compiled code is about 2.8x slower than the uncompiled code, on my machine it's 7.6x slower. $\endgroup$
    – shrx
    Jul 18, 2014 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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