WOLFRAM

Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2008

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: How do little quickest

Scott Hemphill wrote:
> Daniel Lichtblau <danl at wolfram.com> writes:
> 
> [snip]
> 
>> I missed a few optimizations, both in speed and memory.
>>
>> For speed, it turns out that NextPrime computations were the bottleneck. 
>> A bit surprising, since that's not in an inner loop, but there it is. 
>> Easy to repair though, because we get those just by searching the sieve 
>> for the next position that still has a zero.
>>
>> For memory I did two things. One is to combine everything into one 
>> Compile. This is because Compile has, in effect, call-by-value 
>> semantics. Thus the second invocation would start by making a copy of 
>> the large sieve, in effect doubling memory use. The second change was to 
>> not use list operations that involve Take/Drop. This unfortunately makes 
>> things a bit slower than otherwise, but also avoids making copies of 
>> large arrays.
>>
>> Running on a 64 bit machine, I can now handle at least n=29.
> 
> How much VM do you have? 

8 Gig, on that particular machine.


> What operating system are you using, and what
> version of Mathematica?  On my 64 bit machine I get:

Linux (some Gnome version). Mathematica version not-yet-released.

> In[1]:= $Version
> 
> Out[1]= 5.1 for Linux (October 25, 2004)
> 
> In[2]:= minprods2 = Compile[{{n,_Integer}}, Module[
>            {fx, len=2^(n-1), pr=3, start=2, logpr,
>              n2, parts, min=100.},
>            fx = Table[0.,{len}];
>            While[start<=len,
>              logpr = Log[N[pr]];
>              Do [fx[[j]] += logpr, {j,start,len,pr}];
>              While[start<=len && fx[[start]]!=0., start++];
>              pr = 2*start-1;
>              ];
>            Round[2*Exp[Table[
>              n2 = 2^(j-1);
>              min = 100.;
>              Do[min = Min[min,fx[[k]]+fx[[2*n2-k+1]]], {k,n2}];
>              min
>              , {j,n-1}]]]
>            ]]
> 
> In[3]:= Timing[minprods2[29]]
> 
> No more memory available.
> Mathematica kernel has shut down.
> Try quitting other applications and then retry.
> 
> Scott

I don't think Mathematica really was improved for 64 bit machines until 
around version 5.2. Expanded memory for 64 bit addressing spaces remains 
something of a work in progress for the Mathematica kernel (and progress 
is being made).

I should note that my code handles n=30, but punks out beyond that. That 
full sieving approach is really a memory hog. I have some ideas for how 
to improve and might try to code them, time permitting.

Daniel
  • Prev by Date: Re: Re: Model the surface of an ellipsoid
  • Next by Date: Re: Re: Unacceptable bug in Mathematica
  • Previous by thread: Re: How do little quickest
  • Next by thread: Re: How do little quickest ?