Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: How do little quickest

• To: mathgroup at smc.vnet.net
• Subject: [mg93551] Re: How do little quickest
• From: Scott Hemphill <hemphill at hemphills.net>
• Date: Thu, 13 Nov 2008 21:10:17 -0500 (EST)
• References: <gf3mj0$en2$1@smc.vnet.net> <200811091026.FAA20573@smc.vnet.net> <200811100831.DAA26388@smc.vnet.net> <200811111245.HAA04175@smc.vnet.net> <200811121145.GAA23814@smc.vnet.net> <gfgqi1$dll$1@smc.vnet.net>
• Reply-to: hemphill at alumni.caltech.edu

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?  What operating system are you using, and what
version of Mathematica?  On my 64 bit machine I get:

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
-- 
Scott Hemphill	hemphill at alumni.caltech.edu
"This isn't flying.  This is falling, with style."  -- Buzz Lightyear

• Follow-Ups:
  • Re: Re: How do little quickest
    • From: Daniel Lichtblau <danl@wolfram.com>

• References:
  • Re: NIntegrate[UnitStep[...]PDF[...],{x,...}] hard to integrate
    • From: er <erwann.rogard@gmail.com>
  • How do little quickest ?
    • From: Artur <grafix@csl.pl>
  • Re: How do little quickest ?
    • From: Artur <grafix@csl.pl>
  • Re: Re: How do little quickest ?
    • From: Daniel Lichtblau <danl@wolfram.com>