# Performance of compiled functions (Project Euler No14)

I was playing around with the project euler problem 14.

The solution I came up with is listed below as cf1. The solution works fine but I get the compiler warning:

Compile::cset: Variable max of type _Integer encountered in assignment of type _Real.


I don't get this message at all since the only assignment of max is max=l while Head@l == Integer. This error can be fixed by substituting with max=Round[l]. Any ideas?

cf1 = Compile[{}, Module[{l, max = 0, maxN = 0},
Do[
l = Length[NestWhileList[If[EvenQ[#], #~Quotient~2, 3 # + 1] &, n, # != 1 &]];
If[l > max, max = l; maxN = n];
, {n, 1, 10^4}];
{max, maxN}
]];
cf1[] // Timing

{6.349241, {262, 6171}}


I also found a solution with much better performance listed below as cf2. Is it just that NestWhileList doesn't compile very good or is there another reason why this solution is so much faster?

cf2 = Compile[{}, Module[{n1, l, max = 0, maxN = 0},
Do[
n1 = n;
l = 1;
While[n1 != 1, n1 = If[EvenQ[n1], n1~Quotient~2, 3 n1 + 1]; l++];
If[l > max, max = l; maxN = n];
, {n, 1, 10^4}];
{max, maxN}
]];
cf2[] // Timing

{0.374402, {262, 6171}}

• I have no familiarity with Compile but this was my solution which I thought was intuitive (warning: it's painfully slow): Clear[euler14]; euler14[n_?EvenQ] := n/2; euler14[n_?OddQ] := 3 n + 1; MaximalBy[{#, Length@NestWhileList[euler14, #, # != 1 &]} & /@ Range[1, 10^4], Last] // Timing (* {2.683217, {{6171, 262}}} *). I was surprised that the #'s of the NestWhileList and one used to map to the list of number (from 1 to 10^4) play nice with each other. Jul 30, 2014 at 5:39
• @seismatica Thanks for sharing! It's a really nice problem which can be approached form many different angles. Check out this fast, uncompiled solution based on recursion.(mathematica.stackexchange.com/a/33400/4539)
– paw
Jul 30, 2014 at 6:00
• Thank you! There's also another fast(er) solution (using recursion?) that I found from googling. MMA is my first programming language so I'm not used to recursive programming, and Do loops really make me go into a tailspin! Jul 30, 2014 at 6:04
• Related: (33396)
– user31159
Aug 23, 2016 at 20:56

You can fix the error by setting max = 0. (Note the .).

But this doesn't really Compile completely and you can check that by inspecting the 6th Part of the compiled function:

FreeQ[cf1[[6]], _Function, {0, Infinity}]

False


Whenever your compiled function has a Function definition in Part 6, your function did not compile properly. On the other hand, inspecting cf2 we see:

FreeQ[cf2[[6]], _Function, {0, Infinity}]


True

Also,

MatchQ[cf2[[6]], {{__Integer} ..}]


True

This tells us that not only did the function Compile correctly, there's no call to MainEvaluate, so the performance will be top notch as you noticed. Finally, you can get better performance if you have a C compiler by adding the Option: CompilationTarget -> "C"

cf3 = Compile[{},
Module[{n1, l, max = 0, maxN = 0},
Do[n1 = n; l = 1;
While[n1 != 1, n1 = If[EvenQ[n1], n1~Quotient~2, 3 n1 + 1]; l++];
If[l > max, max = l; maxN = n];, {n, 1, 10^4}]; {max, maxN}],
CompilationTarget -> "C"]


Timings

cf1[] // Timing
cf2[] // Timing
cf3[] // Timing

{1.578125, {262., 6171.}}
{0.093750, {262, 6171}}
{0.031250, {262, 6171}}