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 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}}
share|improve this question
1  
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. –  seismatica Jul 30 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 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! –  seismatica Jul 30 at 6:04

1 Answer 1

up vote 6 down vote accepted

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

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.