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>