3
$\begingroup$

This code is about PE496

In[21]:= ParallelSum[n*Count[Divisors[n^2], a_ /; n < a < 2 n], {n, 1, 10^5}] // AbsoluteTiming
Out[21]= {5.987342,10724527832}

I need the sum from n=1 to n=10^9, but this code is too slow to get the result. I have tried to use Compile, but it works very little.

enter image description here

How can I speed up it? Thanks a lot.

Edit

Thanks for Pickett's help, I really learned a lot about how to use Compile from your answer. But some error occurs on my computer, like this enter image description here What's wrong? My computer's memory is 2G, and the mathematica version is 10.0.1.

$\endgroup$
2
  • 2
    $\begingroup$ oeis.org/A005279 $\endgroup$ – Dr. belisarius Jan 8 '15 at 13:48
  • 1
    $\begingroup$ Regarding your error message in your edit, I can't reproduce it for n=10^5, but I can get it for n=10^10 and greater. $\endgroup$ – dr.blochwave Jan 9 '15 at 12:20
5
$\begingroup$

belisarius left a hint in a comment on how to solve this problem more efficiently, but I'm going to take it at face value and try to optimize your code.

The pattern matcher is slow, so you don't want to use the pattern matcher in any kind of loop generally. On my computer your code takes 3.87 seconds to execute, whereas

ParallelSum[
  n Length@Select[Divisors[n^2], n < # < 2 n &],
  {n, 1, 10^5}
  ] // AbsoluteTiming

takes only 2.55 seconds to execute. You did this when you compiled your function, you should always do this whether you plan to compile it or not.

Secondly, compilation doesn't help as much as you'd expect because Divisors is not compilable. This doesn't mean that it's not fast, because it's probably already written in C. But if you compile the function in its entirety you get a MainEvaluate call which slows it down. You can see whether you have any MainEvaluate calls by using

Needs["CompiledFunctionTools`"]
CompilePrint[compiledFunction]

For this reason the code

compiled0 = Compile[{{n, _Integer}},
   n Length@Select[Divisors[n^2], n < # < 2 n &]
   ];
ParallelSum[
  compiled0[n],
  {n, 1, 10^5}
  ] // AbsoluteTiming

takes 2.36 seconds to evaluate whereas

compiled = Compile[{{list, _Integer, 1}, {n, _Integer}},
   n Length@Select[list, n < # < 2 n &]
   ];
ParallelSum[
  compiled[Divisors[n^2], n],
  {n, 1, 10^5}
  ] // AbsoluteTiming

takes just 1.18 seconds to evaluate. The effect of adding runtime attributes and changing the compilation target to C is negligible, I get 1.10. But overall this is a pretty good improvement, with 1.10 instead of 3.87.

$\endgroup$
3
  • 2
    $\begingroup$ +1 for both a great solution and the insight into what goes on with Compile and the MainEvaluate call. This clears up lots of mysteries I've encountered over the years. Thx! $\endgroup$ – Jagra Jan 8 '15 at 16:58
  • 1
    $\begingroup$ Thanks for your help, but there is some error on my computer. I have edited it to the question. $\endgroup$ – wuyingddg Jan 9 '15 at 4:50
  • $\begingroup$ @wuyingddg I asked about it in the chat. For others the limit is much higher, for example $10^10$, but no one seems to know why it occurs unfortunately. I will update if I find a solution. $\endgroup$ – C. E. Jan 9 '15 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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