Re: Re: Re: Mathematica slows down

*To*: mathgroup at smc.vnet.net*Subject*: [mg53013] Re: Re: [mg52964] Re: [mg52956] Mathematica slows down*From*: Bob Hanlon <hanlonr at cox.net>*Date*: Mon, 20 Dec 2004 06:34:27 -0500 (EST)*Reply-to*: hanlonr at cox.net*Sender*: owner-wri-mathgroup at wolfram.com

Dr. Bob, Presumably it has to do with whether intermediate results are effectively cached. Note that the order in which calls to Prime are made matters m=10000; r=Range[m]; rr=Reverse[r]; Timing[p=Prime[r];] {0.03 Second,Null} Timing[pr=Prime[rr];] {1.33 Second,Null} p == Reverse[pr] True Consequently, additional inefficiencies in the original algorithm are probably due to the sequencing of the calls to Prime. Here is the original algorithm (except Print) NumP=15000; Timing[For[k=1,k<NumP,k++, Gap[1]=Prime[k+1]-Prime[k]; Gap[2]=Prime[k+2]-2Prime[k+1]+Prime[k]; Gap[3]=Prime[k+3]-3Prime[k+2]+3Prime[k+1]-Prime[k]; Gap[4]=Prime[k+4]-4Prime[k+3]+6Prime[k+2]-4Prime[k+1]+Prime[k]; If[Mod[k,15000]==0,Print[k]]]] {41.13 Second,Null} Just restructuring the order of the calls to Prime--even without eliminating any redundant calls--makes a significant difference Timing[For[k=1,k<NumP,k++, Gap[1]=-Prime[k+1]+Prime[k+1]; Gap[2]=Prime[k]-2Prime[k+1]+Prime[k+2]; Gap[3]=-Prime[k]+3Prime[k+1]-3Prime[k+2]+Prime[k+3]; Gap[4]=Prime[k]-4Prime[k+1]+6Prime[k+2]-4Prime[k+3]+Prime[k+4]; If[Mod[k,15000]==0,Print[k]]]] {17.68 Second,Null} Bob Hanlon > > From: DrBob <drbob at bigfoot.com> To: mathgroup at smc.vnet.net > Date: 2004/12/18 Sat PM 12:14:01 EST > To: hanlonr at cox.net, mathgroup at smc.vnet.net > Subject: [mg53013] Re: [mg52964] Re: [mg52956] Mathematica slows down > > Bob, I'm puzzled. > > NumP = 15000; > Timing[ > Table[pk[n] = Prime[n], {n, NumP}]; > For[k = 1, k ? NumP, k++, Gap[1] = pk[k + 1] - pk[k]; > Gap[2] = pk[k + 2] - 2pk[k + 1] + pk[k]; > Gap[3] = pk[k + 3] - 3pk[k + 2] + 3pk[k + 1] - pk[k]; > Gap[4] = pk[k + 4] - 4pk[k + 3] + 6pk[k + 2] - 4pk[k + 1] + pk[k]; > If[Mod[k, 1000] == 0, Print[k]]] > ] > > (prints omitted) > {0.671 Second, Null} > > Timing[k = 1; primes = Table[Prime[k + i], {i, 0, 4}]; > While[k ? NumP, gaps = {{-1, 1, 0, 0, 0}, {1, -2, 1, 0, 0}, {-1, 3, -3, > 1, 0}, {1, -4, 6, -4, 1}}.primes; > If[Mod[k, 1000] == 0, Print[gaps]]; > primes = Rest[Append[primes, Prime[k + 5]]]; k++]] > > (prints omitted) > {0.156 Second, Null} > > I'm puzzled that we get these huge speed-ups from eliminating redundant calls to Prime. The original code called it 14 times for each k, while these two solutions call Prime only once for each -- without significantly reducing other operation counts, or so it appears. Yet your code is 30 times faster and mine is 100 times faster (with the same number of calls to Prime). I'd expect us to get at most a 14-to-one speed increase, or thereabouts. > > Bobby > > On Sat, 18 Dec 2004 03:59:37 -0500 (EST), Bob Hanlon <hanlonr at cox.net> wrote: > > > I don't know what changes; however, you can speed it up by avoiding > > repeated calls of Prime for the same values > > > > NumP=15000; > > > > Table[pk[n]=Prime[n],{n,NumP}]; > > > > For[k=1,k<NumP,k++, > > Gap[1]=pk[k+1]-pk[k]; > > Gap[2]=pk[k+2]-2pk[k+1]+pk[k]; > > Gap[3]=pk[k+3]-3pk[k+2]+3pk[k+1]-pk[k]; > > Gap[4]=pk[k+4]-4pk[k+3]+6pk[k+2]-4pk[k+1]+pk[k]; > > If[Mod[k,1000]==0,Print[k]]] > > > > > > Bob Hanlon > > > >> > >> From: George Szpiro <george at netvision.net.il> To: mathgroup at smc.vnet.net > > To: mathgroup at smc.vnet.net > >> Date: 2004/12/17 Fri AM 05:20:43 EST > >> To: mathgroup at smc.vnet.net > >> Subject: [mg53013] [mg52964] [mg52956] Mathematica slows down > >> > >> Hello, > >> > >> the following program runs ok for the first 6,000 iterations, then slows > >> down considerably, and then seems to speed up again after 10,000. Does > >> anyone know what is going on? > >> > >> Thanks, > >> George > >> > >> > >> NumP=15000; > >> > >> For[k=1,k<NumP,k++, > >> > >> Gap[1]=Prime[k+1]-Prime[k]; > >> Gap[2]=Prime[k+2]-2Prime[k+1]+Prime[k]; > >> Gap[3]=Prime[k+3]-3Prime[k+2]+3Prime[k+1]-Prime[k]; > >> Gap[4]=Prime[k+4]-4Prime[k+3]+6Prime[k+2] -4Prime[k+1]+Prime[k]; > >> > >> If[Mod[k,1000]==0, Print[ k]] > >> > >> > >> ] > >> > >> > >> > > > > > > > > > > > > -- > DrBob at bigfoot.com > www.eclecticdreams.net > >