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