Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

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.

share|improve this answer

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}];]
share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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