Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question

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}
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.

share|improve this answer

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}*)
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 at 12:19

Your Answer

 
discard

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.