Re: Re: How do little quickest

*To*: mathgroup at smc.vnet.net*Subject*: [mg93557] Re: [mg93551] Re: How do little quickest*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Fri, 14 Nov 2008 06:35:14 -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> <200811140210.VAA16526@smc.vnet.net>

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

**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>

**Re: How do little quickest***From:*Scott Hemphill <hemphill@hemphills.net>